AtCoder Beginner Contest 170（ABC170）

atcoder.jp

F通したかったね

Bondo416さんのAtCoder Beginner Contest 170での成績：1055位
パフォーマンス：1507相当
レーティング：1279→1304 (+25) :)#AtCoder #ABC170 https://t.co/NPdf9iox13

— ボンド@競プロ (@bond_cmprog) June 14, 2020

A - Five Variables

となるを出力
提出コード

void solve(){
    int ans = 0;
    for(int i=1;i<=5;i++){
        int x;
        cin >> x;
        if(x == 0) ans = i;
    }
    cout << ans << endl;
}

B - Crane and Turtle

なので鶴の数と亀の数を全探索し条件を満たすかどうか調べればいい
提出コード

void solve(){
    int X, Y;
    cin >> X >> Y;
    for(int i=0;i<=X;i++){
        int y = X - i;
        if(i * 2 + 4 * y == Y){
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

C - Forbidden List

全探索を考える
pをmapやboolの配列で持っておきの範囲で全探索をし、絶対値が一番小さいものを出力する
提出コード

void solve(){
    int X, N;
    cin >> X >> N;
    vector<int> p(N);
    map<int, int> mp;
    REP(i,N){
        cin >> p[i];
        mp[p[i]]++;
    }
    int ans = 0;
    int sa = INF;
    for(int i=-200;i<=200;i++){
        if(mp[i] > 0) continue;
        if(chmin(sa, abs(i - X))){
            ans = i;
        }
    }
    cout << ans << endl;
}

D - Not Divisible

本番はで通した（C++を落とせるケースあるのかな）
愚直にの約数列挙を行い、それが各で割り切れるかどうかを調べる
想定解はエラトステネスの篩っぽくやるもの
の倍数をそれぞれに加算していく
加算する際には、すでにカウントされているものがあればそこで打ち切る
そうすると、計算量が篩部分と調和級数部分になり十分に間に合う
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> cnt(1010101);
    REP(i,N) cin >> A[i];
    REP(i,N){
        if(cnt[A[i]] > 0){
            cnt[A[i]]++;
            continue;
        }
        for(int k=A[i];k<1010101;k+=A[i]) cnt[k]++;
    }
    int ans = 0;
    REP(i,N) if(cnt[A[i]] == 1) ans++;
    cout << ans << endl;
}

提出コード(愚直)

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> mp(2020202);
    REP(i,N){
        cin >> A[i];
        mp[A[i]]++;
    }
    int ans = 0;
    REP(k,N){
        mp[A[k]]--;
        bool ok = true;
        for(ll i=1; i*i <= A[k]; i++){
            if(A[k] % i == 0){
                if(mp[i] > 0){
                    ok = false;
                }
                if(i != A[i] / i) if(mp[A[k]/i] > 0){
                    ok = false;
                }
            }
            if(!ok) break;
        }
        if(ok){
            // cout << k << endl;
            ans++;
        }
        mp[A[k]]++;
    }
    cout << ans << endl;
}

E - Smart Infants

まず各幼稚園ごとのレートの管理と、各幼稚園のmaxの集合を管理したい
各幼稚園ごとのレートの管理はmapを使えばいい
また、各幼稚園のmaxの集合にはセグ木を使うことで区間minのクエリに答えることができる
転園があるごとに転園前の幼稚園と転園後の幼稚園でレートのmaxが変更されればmapとセグ木の値を更新してあげればいい
提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N), B(N), C(Q), D(Q);
    vector<map<int, int>> mp(202020);

    SegTree<long long> seg(202020, [](long long a, long long b) {
            return min(a, b);
        },
        2*INF);
    seg.build();
    REP(i, N){
        cin >> A[i] >> B[i];
        A[i], B[i]--;
        mp[B[i]][A[i]]++;
        int val = seg.get(B[i], B[i]+1);
        if((val == 2*INF) || val < A[i]) seg.update(B[i], A[i]);
    }
    REP(i, Q){
        cin >> C[i] >> D[i];
        C[i]--, D[i]--;

        int pre = B[C[i]];
        mp[pre][A[C[i]]]--;
        if(mp[pre][A[C[i]]] == 0) mp[pre].erase(A[C[i]]);
        if(mp[pre].size() > 0){
            int ma = (mp[pre].rbegin() -> first);
            if(pre == 2*INF || ma < A[C[i]]){
                seg.update(pre, ma);
            }
        }
        else seg.update(pre, 2*INF);
        
        mp[D[i]][A[C[i]]]++;
        int ma = (mp[D[i]].rbegin() -> first);
        int val = seg.get(D[i], D[i]+1);
        if(val == 2*INF || ma > val){
            seg.update(D[i], ma);
        }
        cout << seg.get(0, 202020) << endl;
        B[C[i]] = D[i];
    }
}

F - Pond Skater

アルメリアさんの記事がわかりやすい
betrue12.hateblo.jp 愚直に各マスから4方向にだけ移動する場合をBFSなどでやるとになる
アルメリアさんの記事でも解説されている通り、無駄になってしまう経路が存在する
具体的には、(h, w) から (nh, nw)への経路を考えたときにとなるときには枝刈りをする
そうすると、各マスへ入ってくる遷移は各方向あたり高々1回となり計算量がに落ちBFSで解くことが出来る
処理自体は簡単だけど、思いつくのかなり難しい

提出コード

void solve(){
    int H, W, K;
    cin >> H >> W >> K;
    int sh, sw, gh, gw;
    cin >> sh >> sw >> gh >> gw;
    --sh, --sw, --gh, --gw;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];

    queue<pair<int, int>> q;
    q.emplace(sh, sw);
    vector<vector<int>> dist(H, vector<int>(W, INF));
    dist[sh][sw] = 0;
    while(!q.empty()){
        auto [h, w] = q.front(); q.pop();
        REP(i,4){
            for(int k=1;k<=K;k++){
                int nh = h + k * dx[i], nw = w + k * dy[i];
                if(nh < 0 || nh >= H || nw < 0 || nw >= W) break;
                if(fi[nh][nw] == '@') break;
                if(dist[nh][nw] <= dist[h][w]) break;
                if(dist[nh][nw] > dist[h][w] + 1){
                    dist[nh][nw] = dist[h][w] + 1;
                    q.emplace(nh, nw);
                }
            }
        }
    }

    if(dist[gh][gw] == INF) dist[gh][gw] = -1;
    cout << dist[gh][gw] << endl;
}