コンテストページ
https://codeforces.com/contest/1202/
✔A - You Are Given Two Binary Strings...
なるべく小さい位置の 1 同士を打ち消したいですから、尺取り法の要領でそれを探します。
✔B - You Are Given a Decimal String...
各 i, j に対して、差 k が何手で実現可能かを DP で前計算をしておくと良いです。
✔C - You Are Given a WASD-string...
縦と横は独立です。 横のどこかに挿入して、横幅の最小値を求めましょう。 開始点を 0 として、各時点での座標を求め、左右からの累積 min, max を前計算です。 すると各時点で両側の min, max がわかりますから、左右に 1 つずらすのをすべて試しましょう。
C にしてはかなり大変な問題で、順位表も D と逆転していたようです。
✔D - Time to Run
133333.... を用意して、適宜 7 を入れます。 これで三角数の和はすべて作れます。 2,5,8,12,23,33 は作れませんが、これは 1引いておきます。 するとはじめは "1337" になりますから、これの後ろに '7' を挿入です。
✖E - You Are Given Some Strings...
s_i, s_j の境界の場所を全探索です。各場所から左と右それぞれに伸ばして s の要素を作れる個数を求めて、掛け算をして場所に関して足し合わせると答えになります。
各場所から左に伸ばせる数を計算するために、t を左から走査しましょう。このとき、過去の文字列を直接記憶すると間に合いませんから、「今の所一致している最長のもの」を記憶しましょう。それを伸ばしていきながら、それの部分列になっているようなものをついでに回収していきたい気持ちです。ただ部分列を回収するためには、前計算を頑張る必要があります。また、一致しなくなったときに何に遷移するのかも前計算で頑張る必要があります。
s の要素を短い順に見ていきましょう。ある文字列を見ているとしましょう。それより以前に見た文字列の終端がどこにいくつ含まれているのかを前計算です。この計算は先述の t の部分列の数え上げとまったくおなじですから、結局 s ∪ { t } の上で帰納的に計算する感じになります。
もう一つ必要な前計算は、s の各要素の各場所で何のアルファベットを受け取ったらどこに遷移するかです。これもできそうな雰囲気はあるのですが、私は力尽きてしまいました。そもそもこの時点でかなり重実装だと思うのですが、これは本当に正しい方針なのでしょうか……
