練習メモ2-6

はい。
CodeForces Intel Code Challenge Final Round
D: Dense Subsequence
aだけで全区間埋められるか
→　a以下全部＋bで全区間埋められるか（bはできるだけ少なく）
→　b以下全部＋cで全区間埋められるか（cはできるだけ少なく）
→　..y以下…

で貪欲。
全然思いつかなかった……。

BTreeMapの.entry(hoge).or_insert(0) += 1は必須イディオム感がある。

CodeForces Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined)
とりあえずネーミングセンスどうにかしてくれ。
二完で激冷えしたわけだが……。
A まあ。
B　どうみても枝刈り探索です！と思ったらローカルで再現できないREで終了した。
ところでthread立ち上げるとREだと認識されにくいっぽいので新テンプレートを用意した。

まあスレッドのところコメントアウトしただけなんだが……。
10^5回再帰するときはスタック４倍にしてコメント解除する。
というか最初から４倍にしといた方がいいかな。
C　全然わからんと思ったらバケツソートでシュミレーションするだけだった。萎え。

最大で10^8回ループ回るけど468msで終わる。C++は200ms切ってるけど……。でもループの中でallocateしてるのにこれってめっちゃ速いよね。
無理やり周期を求める解法もあるっぽいけどどうやって証明すんだろう。
D　また今度。
E 1 + 2 + 3 + ...ってやるとNimになる。というかdpとかしなくても「ｘに対し、Sum[1..n] <= xが成り立つような最大のn」がgrundy数だと思うんだけどなんで想定解DPなの。そもそもgrundy数って言葉editorial見るまで知らんかったのだが（蟻本見たら書いてあったけど）。Si <= 1000000000とかにしてほしかったな。

かなり不満の多いコンテストだった。まあ昨日（日付は今日だけど）のことは忘れて今日はSRM！

SRM 708 Div1
easy: Xscoregame
dp[使った数の集合][スコアの下位６桁]でDP。
00110000 000000000110000
00001100 000000001101100
00010111 000000011100111
00011000 000000111100110
00001001 000001111010101
00101001 000011111010001
00100001 000111111000001
00001100 001111110001110
みたいに、小さいケースを全探索して最適解眺めてたらこれy <= 0b111111だから下位六桁持てば状態網羅できるなってなって解けた。
そもそも気づくのに45分かかったうえに、
x = x + (x ^ y);と
x = x + x ^ y;
が違うのと配列外参照に気づかず時間を浪費したが、なんとかサブミットできて良かった。
x = x + x ^ yはRustだとコンパイル時にwarnでるし、配列外参照はRUST_BACKTRACE=１すればそれこそ一瞬でわかるのでやっぱりRustいいなあ、という。
alias cc11deb=g++ -std=c++11 -Wall -Wextra -D_GLIBCXX_DEBUG -fsanitize=address
で少しはマシになるんだが、ちょっと物足りないよね。
レートは1324→1420でhighest。

struct Xscoregame {
    int f(vector<int> a) {
        int n = a.size();
        vector<vector<int>> dp(1 << n, vector<int>(1 << 6, -1));
        int magic = (1 << 6) - 1;
        dp[0][0] = 0;
        for(int i : in(1 << n)) {
            for(int k: in(n)) {
                if((1 << k) & i) continue;
                int ni = i | (1 << k);
                for(int j : in(1 << 6)) {
                    if(dp[i][j] == -1) continue;
                    int ns = dp[i][j] + (dp[i][j] ^ a[k]);
                    int nj = magic & ns;
                    dp[ni][nj] = max(dp[ni][nj], ns);
                }
            }
        }
        int ma = 0;
        for (int j : in(1 << 6)) {
            ma = max(ma, dp[(1 << n) - 1][j]);
        }
        return ma;
    }
    int getscore(vector<int> a) {
        return f(a);
    }
};

全探索用コードのファイルに書いたのをコピペしたので別の関数になっている。
今回とかは本当にサンプル弱いので、僕みたいに自信のない人はテスト必須感がある。
challengeでは20秒くらいで部屋のが狩り尽くされててさすがにびびった。
topcoderなんだかんだコンテスト形式は面白いなあ、と思う。
ネット接続が切れるたびにArenaに再ログインしないといけない仕様は本当に嫌いだが……。