naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 031

3/16(土) 21:00-23:40
1完1226位
パフォ1182でレート冷やして1694→1651 (-43)
f:id:n4_t:20190317142634p:plain:w480

終了1分16秒後にB通った><
仮にこのBが間に合ってもパフォーマンスに大差ないほどにBのAC者数が多かった。

A - Colorful Subsequence(200)

最初2^{26}\times 26のbitDPを書いてて
なんか遅いなあ(10秒弱かかるし)とか呑気に思いながら
みんなバンバン通してるし
もっと簡単に書けるのでは
ああ
ある文字について(どれを使うか + 使わないか)の選択ができて
それを掛け合わせるだけの話だ
AC 28:51

B - Reversi (700)

最初Ciが0〜9しかない問題を二重BITで解いてた
RE
その後DPを書き直したけど計算が合わない
WA(6)
同じCiが来る次の場所を探す時、単に1つでも違う色が入ったかを見れば良いと気づいて
でももう時間がない

終了1分16秒後にようやくAC

AC

TLから

圧縮しても変わらないのか(なるほど)(なるほどすぎる)
次に同じ数が来るところまでを裏返すか裏返さないかだけ見れば良くて
そうするとかなりシンプルに書ける
AC

教訓

ちょっと直せば行けるのでは?的なデバッグをせずしっかり考察すべき

C - Differ by 1 Bit (800)

B難しいなあと思って先に開いた
グレイコードでAで始まりBで終わる区間を持ってくる?
WA(1)
いやループになってなくてもよくて
最初と最後が1bit差でなくても行けるケースがあるのか...

D - A Sequence of Permutations (1000)

見てない

E - Snuke the Phantom Thief (1300)

見てない

F - Walk on Graph (2000)

見てない