AGC029 参加記

12/15に行われたAGC029に参加しました。コンテスト中はAB2完、解説でCDを通しました。

A - Irreversible operation

オセロの石が一列に並んでいて、左から黒白の順に並んでいる組があれば両方を裏返すという操作が最大で何回できるかという問題でした。

石は最大で個あるので、愚直にやるとおそらくTLEします（これに気づいたのは愚直解を書いたあとなのですが・・・）。そこで、黒白の順の組を両方裏返すことを、両者を入れ替える操作とみなすことにします。すると、全ての操作が終了したあとは白石が全て左に寄り、黒石が全て右に寄った状態になります。よって、盤面を右側から見ていき、白が出たらflagを立て、その後は黒が出るたびに今までに見た黒の数に応じて操作回数を足していくとよいです。

コード例

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    bool flag = false;
    long long ans = 0, cnt = 0;
    for(long long i = s.size() - 1 ; i >= 0 ; --i){
        if(s[i] == 'W'){
            flag = true;
        }
        if(s[i] == 'B'){
            ++cnt;
            if(flag){
                ans += (long long)s.size() - i - cnt;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

B - Powers of two

個の正整数からつを選んで、和が (は非負整数)で表せる数となるようにします。それぞれの正整数は回のみ使用可能とします。このとき正整数の組は最大で何組できるかという問題でした。

これは、大きい数から順に貪欲に組を決めていくとうまくいきます。ペアになる可能性のある数はで表される数を中心に対称の位置に存在するため、大きい数側から順に決めればペアにならずに余る数を最小化できます。あとは、各数の個数に注意しながら二分探索でペアを決めていけばよいです（私は知らなかったのですがC++ならstd::multisetを使うと実装が楽になるそうです）

コード例

#include<bits/stdc++.h>
using namespace std;

const long long LLINF = (long long)1e18 + 10;

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    map<long long, int> mp;
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i];
        ++mp[a[i]];
    }
    a.push_back(LLINF);
    sort(a.begin(), a.end());
    vector<long long> v;
    long long now = 1LL << 32;
    while(now > 1){
        v.push_back(now);
        now >>= 1;
    }
    int ans = 0;
    for(int i = n - 1 ; i >= 0 ; --i){
        for(int j = 0 ; j < v.size() ; ++j){
            bool flag = false;
            if(*lower_bound(a.begin(), a.end(), v[j] - a[i]) == v[j] - a[i]){
                if(v[j] - a[i] == a[i]){
                    if(mp[a[i]] >= 2){
                        ++ans;
                        mp[a[i]] -= 2;
                        flag = true;
                    }
                }else{
                    if(mp[a[i]] >= 1 && mp[v[j] - a[i]] >= 1){
                        ++ans;
                        --mp[a[i]];
                        --mp[v[j] - a[i]];
                        flag = true;
                    }
                }
            }
            if(flag){
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

C - Lexicographic constraints

個の文字列があり、各文字列の長さが与えられます。を満たす各について、辞書順で比較したときにを満たしているとする。このとき現れる文字の種類の数の最小値はいくらかという問題でした。

まず最小やら最大やらと言えば二分探索ということで、種類数を二分探索で求めます。問題は、種類でできるかという判定の仕方です。これは、文字列を進法の数として見て、前から順番に条件を満たすように決めていけばよいです。実装は、で番目の文字でない文字が現れる位置をmapで保持しておけばよいです。計算量は、繰り上がりが起こるときに繰り上げる桁数に対応する時間がかかります。しかし、大規模な繰り上がりが起こる周期は長いためならし計算量はそこまで膨大にならず間に合います。

コード例

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> a;

// mid進法で+1する関数 可能ならばtrueを返し、不可能ならばfalseを返す
bool add(map<int, long long> &mp, long long mid, int d){
    mp.erase(mp.upper_bound(d), mp.end()); // 字数を減らす

    // mp[d]を生成すると同時にd文字目を足せるかどうか判定
    if(mp[d] < mid - 1){
        ++mp[d];
        return true;
    }

    // 後ろから順番に見る
    auto it1 = mp.end();
    --it1;
    while(it1 != mp.begin()){
        auto it2 = it1--; /* it2は今いる桁 it1はそれより上の桁で
                             0でないものが入っているところ、あるいは一番上の桁 */

        // 見ているところに足せればそれでok
        if((*it2).second < mid - 1){
            ++mp[(*it2).first];
            return true;

        /* 見ているところと1個前の差が1より大きければ、
           見ているところの1つ上の桁を1として繰り上がりが終了 */
        }else if((*it1).first + 1 < (*it2).first){
            ++mp[(*it2).first - 1];
            mp.erase(it2);
            return true;

        /* どちらにも当てはまらなければ
           見ているところの桁を0とし、繰り上がりを続ける */
        }else{
            mp.erase(it2);
        }
    }

    // 一番上の桁まで来たら、その桁を足せるか判定
    if((*mp.begin()).second < mid - 1){
        ++(*mp.begin()).second;
        return true;
    }
    return false;
}

bool check(long long mid){
    map<int, long long> mp; // 0番目の文字以外が入るところを記録しておく
    mp[1] = 0; // 一番上の桁を番兵にしておく
    REP(i, 1, n){
        /* 字数が増えるときは0番目の文字を増える分だけ付け足せばよい
        字数が等しいあるいは減るときにmid進法内で辞書順を保てるか判定 */
        if(a[i - 1] >= a[i]){

            // 1種類のときは辞書順を保てない
            if(mid <= 1 || !add(mp, mid, a[i])){
                return false;
            }
        }
    }
    return true;
}

// 何種類文字があれば条件を満たせるか二分探索
long long meguruSearch(long long ok, long long ng){
    while(abs(ok - ng) > 1){
        long long mid = (ok + ng) / 2;
        if(check(mid)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    return ok;
}

int main(){
    cin >> n;
    a.resize(n);
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i];
    }
    long long ans = meguruSearch(1e15, 0);
    cout << ans << endl;
    return 0;
}

D - Grid game

行列のボードがあります。個の障害物が地点にあります。最初、このボードの地点にコマがあります。高橋君と青木君が順番に以下のような行動を取ります。高橋君は地点のコマを地点に動かすか、コマを動かさないという行動のいずれかを取ります。青木君は地点のコマを地点に動かすか、コマを動かさないという行動のいずれかを取ります。なお、移動先に障害物がある場合はコマを移動できません。2回連続でコマが動かされなければそこで終了です。高橋君は行動回数を最大化するように、青木君は行動回数を最小化するように行動するとき、高橋君は最大で何回行動することができるでしょうかという問題でした。

以下、軸正方向を下、軸正方向を右とします。高橋君は意図的に止まることができないことがすぐに分かります。よって、高橋君は可能な限り下に進み続けます。青木君は、できるだけコマを障害物に寄せていきます。これを愚直に実装すればよいです。各行において駒の位置としてありうるもののうち一番右の座標を保持します。各行の一番左の障害物の位置を記録しておけば、青木君がそこで止められるかどうかがわかります。
コード例

#include<bits/stdc++.h>
using namespace std;

const int IINF = 1e9 + 10;

int main(){
    int h, w, n;
    cin >> h >> w >> n;
    vector<int> v(h, IINF); // 各行一番左の障害物 なければinf
    for(int i = 0 ; i < h ; ++i){
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        v[x] = min(v[x], y);
    }
    int right = 0, ans = h;
    for(int i = 0 ; i < h - 1 ; ++i){
        // 行ける範囲に障害物があればそこでストップ
        if(v[i + 1] <= right){
            ans = i + 1;
            break;

        // 一番右の隣に障害物がなければ青木君の行動範囲拡大
        }else if(right + 1 < v[i + 1]){
            ++right;
        }
    }
    cout << ans << endl;
    return 0;
}

感想

今回解いた問題は、Bを除いて考察難易度は配点ほど高くなかったように思えます。ただ、Cのmapの操作やDの障害物の位置の記録など、実装が難しく感じました。必要なものだけを保持しておくという考えは今後も使えそうな知見です。実装力を向上させて解ける問題の幅を広げていきたいです。また、配点に惑わされずにできそうな問題を見極めることの重要さも知ることができ、個人的にはとてもいい回になりました。