ABC122

AGCも終わったし今度は気楽だなと思っていたら、やはり緊張はする。このABを瞬殺できるように復習したい。

A - Double Helix

スピードが出なかった。A問題は、読んだときには解けてるので、考えることはコーディングの時間を減らす方法だけだ。時間を減らすのが目的だから、時間をかけて考えることはできない。結局、if文を4つ書く。ACGTを知ってると有利だと思った(自分は知らない)。

B - ATCoder

これもスピードが出ない。まず、部分文字列の説明で「先頭と末尾から」の部分を見落として、連続しなくてもいいと思って実装してしまう。サンプルが合わないので間違いに気づく。そうなると全探索はやや難しくなるが、ACGTだけで構成される長さの最大を見ればいいのできれいに書ける。ここもACGTは手書きとなり、悔しい。

C - GeT AC

ちょっと難しそう。しかしよく見ると、"AC"同士が重なることがないため、単なる累積和で行けそうだ。ただ、"AC"という文字列の長さは2なので多少は気を使う。累積和では、"AC"の'A'をカウントする。r_iにその'A'があっても意味がないのでデクリメント。ここは満足のいく出来。

D - We Like AGC

AGCTを0123と読み替える。サンプル1の説明がやけに親切で、当然その通りの方針でやる。現れてはいけない部分文字列は、012,102,021,0X12,01X2。これを取り除く。包除?いやさすがにここまで複雑なのは無理。Nは小さいものの、これは無理では??「漏らす前に全完」が無理になった。便意に耐えきれないのでトイレに行った、というよりは、トイレで考えることに逃げたという感覚。本当にわからなかった。少ししてDPを思いつく。yukicoderで見たことがある。俺の苦手なDPか!(DPが全部苦手という意味ではなく、苦手なタイプのDPが来たということ)

DPで保持する値が、条件を満たすものか満たさないものかを考えていた。トイレから戻り、条件が「含まない」という否定文であることが混乱の原因と認識する。冷静に。一箇所でも条件を満たさないところがあればダメなので、条件を満たす文字列の数でDPする。DPの場合分けは3文字分64通り。dp[k][xyz]のkが文字数なのか最後の文字の位置なのか(どっちでもいいけどどちらが自然か)。そういう必然性を、考えて経験値を溜めながら少しずつ輪郭を明らかにしていく。dp[3]だけ手で埋めれば直前のものしか参照しなくてよさそう(だから空間計算量は小さくできる(けどやらない))。条件を満たさないものは最後にまとめて0にすればいい。シフト演算子は優先順位が面倒なので乗除算を使う。なんとか書き切った。我ながらすごいと思った。サンプルは親切だった。

典型ではあるけど、これを早解きできる人は頭おかしいと思う。競プロを始める前の自分が全く経験したことのない考え方で、こういうDPをするためのハードウェアが備わっていない。こういう考え方をする必然性がイメージできない。