Codeforces Round #365 (Div. 2)

A. Mishka and Game

問題文

codeforces.com

解法

シミュレーションするだけ

感想

やるだけ

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const double PI  = 3.1415926535897932384626433832795028841971;
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n, x, y;

int main(){
	cin >> n;
	rep(i,n){
		int a, b;
		cin >> a >> b;
		if(a > b) x++;
		if(b > a) y++;
	}
	if(x > y){
		cout << "Mishka" << endl;
	} else if(y > x){
		cout << "Chris" << endl;
	} else{
		cout << "Friendship is magic!^^" << endl;
	}
}

B. Mishka and trip

問題文

codeforces.com

解法

ciの総和(sum)を求めておくと、各首都について、その首都から出ている辺のコストがO(1)でも求まるので解ける

感想

やるだけ

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const double PI  = 3.1415926535897932384626433832795028841971;
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n, k;
ll sum,ans;
ll c[100000];
bool saw[100000];

int main(){
    cin >> n >> k;
    rep(i,n) scanf("%I64d",c+i);
    rep(i,n) sum += c[i];
    rep(i,k){
        int t;
        scanf("%d",&t);
        t--;
        saw[t] = true;
        sum -= c[t];
        ans += c[t]*sum;
    }
    rep(i,n){
        if(saw[i]){
            continue;
        }
        if(i > 0 && saw[i-1] == false) ans += c[i]*c[i-1];
        if(i == 0 && saw[n-1] == false) ans += c[0]*c[n-1];
    }
    cout << ans << endl;
}

C. Chris and Road

問題文

codeforces.com

解法

まず、バスが来る前に突っ切れる場合と突っ切ってもバスが既に通過していてぶつからないという場合を除いておく。
そうでないときはバスの一番下の頂点と一番上の頂点に挟まれた右側の頂点にのみ注目すればよい。
後は下から順に注目している頂点を見ていって、その点がx=0に来た時にMishkaがどこまで進むことができるか求めていけばよい。

感想

幾何でつらそうに見えるけど実際はそうでもなくて、だけど何回か場合分け部分でWAしたので反省。

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const double PI  = 3.1415926535897932384626433832795028841971;
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
ll w, v, u;
ll x[10000], y[10000];

int main(){
    cin >> n;
    cin >> w >> v >> u;
    rep(i,n){
        scanf("%I64d%I64d",x+i,y+i); 
    }
    bool check = false;
    rep(i,n){
        if(x[i] > 0) check = true;
    }
    if(!check){
        printf("%.9f\n",w/(double)u);
        return 0;
    }
    rep(i,n){
        if(x[i]*u-y[i]*v < 0) check = false;
    }
    if(check){
        printf("%.9f\n",w/(double)u);
        return 0;
    }
    int to = 0, bo = 0;
    for(int i = 1; i < n; i++){
        if(y[i] > y[to]) to = i;
        if(y[i] < y[bo]) bo = i;
    }
    double ans = 0.0;
    double pos = 0.0;
    for(int i = bo;;i++){
        if(i == n) i = 0;
        ans = max(((double)y[i]-pos)/u+ans,x[i]/(double)v);
        pos = y[i];
        if(i == to) break;
    }
    ans += (w-y[to])/(double)u;
    printf("%.9f\n",ans);
}

D. Mishka and Interesting sum

問題文

codeforces.com

解法

ある区間において偶数回現れた数のxorは、(ある区間において一度以上現れた数のxor)^(ある区間において奇数回現れた数のxor)で求まる。
ある区間において奇数回現れた数のxorは、その区間の数を全てxorすればよいので、累積和で前もって求めておくことでO(1)で求まる。
ある区間において一度以上現れた数のxorは、BITを使うと求まる。具体的には既に出現している数がもう一度現れたら、前に出現していたところのノードを0にすればよい。しかし、このBITを用いて解を求めるには区間が今見ているところで終わっている必要があるため、クエリをソートして、BITを更新しながらクエリに答える必要がある。

感想

自力では解けなかったのでeditorialなどを見て通した。
最初のほうのアイディアはあったけれど、ある区間において一度以上現れた数のxorの求め方がわからず練習不足を痛感した。

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const double PI  = 3.1415926535897932384626433832795028841971;
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Q{
    int l, r, id;
};

int n;
int a[1000000], sum[1000001];
int aa[1000000], b[1000000];
Q q[1000000];
int ans[1000000];
int pos[1000001];
int fen[1000001];
int m;
map<int,int> num;

bool comp(Q x, Q y){
    if(x.r < y.r) return true;
    else return false;
}

int Sum(int x){
    int ret = 0;
    while(x > 0){
        ret = ret^fen[x];
        x -= x&(-x);
    }
    return ret;
}

void Add(int x, int y){
    while(x <= n){
        fen[x] = fen[x]^y;
        x += x&(-x);
    }
}

int main(){
    scanf("%d",&n);
    rep(i,n){
        scanf("%d",a+i);
        aa[i] = a[i];
        sum[i+1] = sum[i]^a[i];
    }
    sort(aa,aa+n);
    int checker = 0;
    rep(i,n){
        if(num.count(aa[i]) != 0) continue;
        num[aa[i]] = checker;
        checker++;
    }
    rep(i,n){
        b[i] = num[a[i]];
    }
    scanf("%d",&m);
    rep(i,m){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
        q[i].l--; q[i].r--;
    }
    sort(q,q+m,comp);
    rep(i,n+1) pos[i] = -1;
    int now = -1;
    rep(i,m){
        while(q[i].r > now){
            now++;
            if(pos[b[now]] != -1) Add(pos[b[now]],a[now]);
            Add(now+1,a[now]);
            pos[b[now]] = now+1;
        }
        int cnt = sum[q[i].r+1]^sum[q[i].l];
        cnt ^= Sum(q[i].r+1)^Sum(q[i].l);
        ans[q[i].id] = cnt;
    }
    rep(i,m) printf("%d\n",ans[i]);
}

E. Mishka and Divisors

問題文

codeforces.com

解法

dp[n][kの約数へのインデックスの集合]というdpをして、経路復元をすればよい。
mapを使うとTLEしたり、kの約数の個数を適当に見積もるとMLEしたりするので色々とつらい。

感想

mapで解こうとして、解けず、pekempeyさんのブログを参考にして通した。
unordered_mapを使うと解けそうだったんだが、WAしてしまい、ハッシュの衝突だーと思って諦めてしまった。(しかし、そのケースでWAした原因がハッシュの衝突ではないと後でわかった)
けど、この問題制約きつすぎない?って思う。

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const double PI  = 3.1415926535897932384626433832795028841971;
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;

int n;
ll x;
ll p[1000];
vector<ll> prime;
int small[1000001], large[1000001];
P dp[1001][7000];
P rev[1001][7000];

ll gcd(ll r, ll l){
    while(l){
        r %= l;
        swap(r,l);
    }
    return r;
}

int main(){
    cin >> n >> x;
    if(x == 1){
        cout << 1 << endl;
        int out = 0;
        ll sum = (1LL<<60);
        for(int i = 1; i <= n; i++){
            ll tmp;
            scanf("%I64d",&tmp);
            if(sum > tmp){
                sum = tmp;
                out = i;
            }
        }
        cout << out << endl;
        return 0;
    }
    for(ll i = 1; i*i <= x; i++){
        if(x%i == 0){
            prime.push_back(i);
            if(i*i != x){
                prime.push_back(x/i);
            }
        }
    }
    sort(prime.begin(),prime.end());
    rep(i,prime.size()){
        if(prime[i] > 1000000 || prime[i]*prime[i]>x){
            large[x/prime[i]] = i;
        } else{
            small[prime[i]] = i;
        }
    }
    rep(i,10000) dp[0][i] = P(-1,-1);
    dp[0][large[1]] = P(0,0);
    for(int i = 1; i <= n; i++){
        scanf("%I64d",p+i-1);
        rep(j,prime.size()) dp[i][j] = dp[i-1][j];
        rep(j,prime.size()) rev[i][j] = rev[i-1][j];
        ll gp = gcd(p[i-1],x);
        if(gp == 1) continue;
        rep(j,prime.size()){
            ll num = prime[j];
            int t;
            if(num > 1000000 || num*num>x){
                t = large[x/num];
            } else {
                t = small[num];
            }
            if(dp[i-1][t].first == -1) continue;
            ll g = gcd(p[i-1],num);
            if(g == 1) continue;
            int to;
            if(num/g > 1000000 || (num/g)*(num/g)>x){
                to = large[x/(num/g)];
            } else {
                to = small[num/g];
            }
            if(dp[i][to] == P(-1,-1) || dp[i][to] > P(dp[i-1][t].first+1,dp[i-1][t].second+p[i-1])){
                dp[i][to] = P(dp[i-1][t].first+1,dp[i-1][t].second+p[i-1]);
                rev[i][to] = P(i,num);
            }
        }
    }
    if(dp[n][0] == P(-1,-1)){
        cout << "-1" << endl;
        return 0;
    }
    ll num = 1;
    int para = n;
    vector<ll> out;
    while(true){
        if(num == x) break;
        int t;
        if(num > 1000000 || num*num > x){
            t = large[x/num];
        } else {
            t = small[num];
        }
        out.push_back(rev[para][t].first);
        num = rev[para][t].second;
        para = rev[para][t].first-1;
    }
    cout << out.size() << endl;
    rep(i,out.size()){
        if(i != 0) printf(" ");
        printf("%I64d",out[i]);
    }
    printf("\n");
}