AtCoder Grand Contest 031

結果

　A,B問題を解いて634位。パフォーマンスは1708でレート変化は1796→1787(-9)だった。C問題を通せるようになるにはもう少し成長が必要そう。

A問題

　3分4秒でAC。ある文字が回出てきたらそれらのうちどれかから１回取るか全く取らないかで通りありえるんだなというのがすぐ見通せてそんなに時間はかからなかった。とりあえず200早解きができれば大失敗ということはないかなと少し安心した。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    string S;
    constexpr ll MOD = 1e9 + 7;
    cin >> N >> S;
    vector<ll> num(26, 1);
    for (char c : S) {
        num[c - 'a']++;
    }
    ll ans = 1;
    for (ll i = 0; i < 26; i++) {
        (ans *= num[i]) %= MOD;
    }

    cout << (ans + MOD - 1) % MOD << endl;
}

B問題

コンテスト中の思考

　問題文を読んで、700点問題だし簡単ではないんだろうけどたっぷり時間があれば解けそうという印象を持つ。

　まず最初は同じ色が連続していればそこはまとめて1個にしてしまっても同じということを考える。配列の長さが変わると厄介なのでこれが便利な性質かどうかは微妙そう。終わりの状態から逆の操作を考えれば見通しよくなったりしないかと試してみたがあまり上手くいかない。

　ここでちゃんと入力例2,3についてどの5通りがあるのか列挙してみる。やっていると、ある色で挟まれている区間が重なっていないならそれらは独立に色を変えるか変えないかの2通りが選べそうだと気づく。問題なのは重なっていたり、入れ子になっている場合で、これを処理できればなんとかなりそう。

　結局ある色2個のペアについて操作を行う/行わないの2通りを考えていけば良さそう。いかにもDPっぽいと思い、左端から考えていくと、操作を行う場合は右端の次から独立にまた考え始めれば良く、操作を行わない場合は左端の次からまた考え始めれば良いとなって、あれこんなに簡単なのかと怪しみながら実装へ移った。ちゃんと定式化すると

として、番目と同じ色ものが次にあるのは番目だった場合

となるということ。第一項が操作を行う場合で、第二項が行わない場合。これ以降同じ色がなかった場合は操作を行えない第二項だけで計算する。

　こういう先の値を今の値の計算に使うという気持ちだったので実装はメモ化再帰に。同じ色が連続した場合とかで何度かバグらせつつなんとかAC。returnのところでメモに代入し忘れていて1TLE出したのはもったいなかった。

反省

　そこそこ速く処理できたと思ったわりに約50分かかっているのでもう少し速く解ければ。入力例を手で解きにいくのが遅すぎるので、一番最初にやってしまうくらいで良いと思う。

　解説を読むと少し方針が違っていた。色が切り替わる境界はもともとの配列と同じ色じゃないといけないというのはさっぱり気づいていなかった。forループのDPとメモ化再帰は見る順番が逆になるイメージで、どちらかというとメモ化再帰的な見方の方が感覚に合うんだけど「DPに帰着できました解けます」みたいな安心感はないかもしれないなぁと思ったりもする。どっちもできるようになるべきだが。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = 1e9 + 7;
vector<ll> pos[200001];
ll N;
vector<ll> C;
vector<ll> memo;

ll solve(ll left) {
    if (left >= N) {
        return 1;
    }

    if (memo[left] != -1) {
        return memo[left];
    }

    ll next = *upper_bound(pos[C[left]].begin(), pos[C[left]].end(), left);

    ll ans;

    if (next == left + 1) {
        ans = solve(next);
    } else if (next >= N) {
        ans = solve(left + 1);
    } else {
        ans = (solve(next) + solve(left + 1)) % MOD;
    }

    return memo[left] = ans;
}

int main() {
    cin >> N;
    C.resize(N);
    memo.resize(N, -1);
    for (ll i = 0; i < N; i++) {
        cin >> C[i];
        pos[C[i]].push_back(i);
    }
    for (ll i = 1; i <= 200000; i++) {
        pos[i].push_back(N);
    }

    cout << solve(0) << endl;
}

C問題

　2時間弱をこの問題に費やしたわけだけどさっぱり解法は見えず。各操作がどこか1つビットが立っている整数とXORを取る操作になるので桁ごとに考えていくのかなという感じで考えていたがダメ。で全探索したところとも2進数表記でちょうど1桁だけ異なれば大丈夫そうと思ってやってたけど、立っているビットの数の偶奇が問題なのはわからなかった。

　この性質に気づくために何が必要だったかというと、やはりもっと具体例を触ってみるべきだった気がする。とかそういうのでもっと操作してみるべきだったか。あとは再帰で書けそうという雰囲気は少しでも嗅ぎ取りたかったか。冪乗系の問題を困難は分割せよ的な方針で解けるようになるとAGCには強くなれそう。

　答えを見る場合、この問題についてはまず解説PDFよりも解説放送を先に見た方がイメージが作りやすかった。そのあと具体的に実装するときに解説PDFを読みなりなんなりしたほうが良さそう。自分はmerom686氏のコンテスト中の提出を参考に実装してAC。思考の道筋をコメントに書いていかないと全然理解できなかった。いやぁこれを本番中に通せるのは天才が過ぎる。すごいなぁ。

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

ll popcount(ll x) {
    ll result = 0;
    for (ll i = 0; i < 64; i++) {
        if (x & (1LL << i)) {
            result++;
        }
    }
    return result;
}

//sとtは下位nビットの中で立っているbitの数の偶奇が異なることを前提
vector<ll> solve(ll s, ll t, ll n) {
    if (n == 1) {
        return { s, t };
    }

    vector<ll> result;

    //最上位ビットを考える
    ll l = (1LL << (n - 1));
    if ((s & l) == (t & l)) {
        //最上位ビットが同じ
        //例)
        //s:1000
        //t:1010
        //このときn-1ビット以下でs→tを考えると,sの次には
        //n-1ビット以下のどこか1箇所がsと異なる
        //ものcが得られる(s→c→...→t)
        //ここでそのcのnビット目を反転したものをc'として
        //sのnビット目を反転したs'との比較を考えると
        //やはりn-1ビット以下のどこか1箇所が異なるので
        //s'→c'という遷移が構築可能である
        //全体として
        //s→s'→...→c'→c→...→t
        //という遷移を考えれば良い
        
        //まずs→tを構築
        auto v1 = solve(s, t, n - 1);
        
        //2番目のものの最上位ビット反転へのパスを構築(c = v1[1])
        auto v2 = solve(s ^ l, v1[1] ^ l, n - 1);
        
        //初手はs
        result.push_back(s);
        
        //s'→c'
        result.insert(result.end(), v2.begin(), v2.end());
        
        //c→t
        result.insert(result.end(), v1.begin() + 1, v1.end());
    } else {
        //最上位ビットが異なる
        //例)
        //s:1000
        //t:0110
        //このとき間に挟むのは最下位ビットを反転した
        //c :1001
        //とこれの最上位ビットを反転したものを
        //c':0001
        //としてs→c→c'→tという遷移を考えれば良い
        ll c = s ^ 1;
        auto v1 = solve(s, c, n - 1);
        auto v2 = solve(c ^ l, t, n - 1);
        result.insert(result.end(), v1.begin(), v1.end());
        result.insert(result.end(), v2.begin(), v2.end());
    }
    return result;
}

int main() {
    ll N, A, B;
    cin >> N >> A >> B;

    if (popcount(A) % 2 == popcount(B) % 2) {
        cout << "NO" << endl;
        return 0;
    }

    cout << "YES" << endl;
    auto ans = solve(A, B, N);
    for (ll i = 0; i < ans.size(); i++) {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}