WUPC 2019
A
文字列を前から見ていき部分文字列'WA'を、’AC'に変える。一度変えたら、また文字列先頭から走査をやり直す。
N<=1e5
'WWA'は’WAC' -> 'ACC' というようになる。
方針としては、'WA'を置き換えたあと、次に見る文字を「今見てる文字の1つ前の文字」にすると良い。
'WA' -> 'AC'だと、置き換え前の文字列のsuffixが置き換え後の文字列のprefixに一致する。そのため置き換え後の文字列と見終わった文字列がマッチしてしまうことがある。
'AW' -> 'CA' だと、一致するのは置き換え前の文字列のprefixと置き換え後の文字列のsuffix。これだと、置き換えで新たにマッチするようになったとしても、まだ見終ってない位置でマッチする。嬉しい。
本番での方針
走査するときに、'WA'の前に連続してる'W'の数を数えておく.
'WA'にヒットしたら、数えておいた'W'の分だけ遡って置き換えを行う
感想
本番での方針は微妙に実装が複雑だった。1つ目に書いた方針「着目する文字を1個前のにする」が気づきやすくて実装も楽でよいかなぁという感じ。
B
H*Wのグリッドが与えられ、グリッドには0〜9の値が入っている。 操作として、グリッドの連結な集合Sを選んで、Sの各値を max(S) mod 10に更新できる。
グリッドをすべて0にすることはできるか?できる場合はその操作回数は?
各値の遷移は下記のようになる。集合の最大値が5であるとき、その集合は値0に遷移する。https://gyazo.com/a6761a241cb46da18ee1397fbfe00878
とりあえず下記が言える。
入力されたグリッドの値がすべて0の場合は、操作回数0が答えになる。
入力に5が含まれない場合、答えは「0への遷移は不可能」
値6, 7, 8, 9に対しては操作を行い、4以下に遷移させる必要がある。
お気持ち
操作対象の集合はできるだけ大きく取ったほうが良い。
結果は集合を大きく取っても悪くならないため(例えばグリッド上に9がある時点で4回操作するのは確定で、値6を別の集合で操作したとしても結果はよくならない)
ただし値5のグリッドは、1つは操作せず残さないといけない
これはH とWが2以上だと、問題にならない(いくらでも避けて集合が取れる)
入力のHかWの片方が1だと、操作対象に含められない値5がグリッドを二分する形になる。「値5のグリッド1つを残してすべて操作対象にする」というのが一般にできなくなる
https://gyazo.com/5aefdec15c665a500eec9a3fcfac32b5
H > 1の場合、値5のグリッドを1つ残して操作対象の集合が作れる。そのため入力のうち、5以下になるために必要な遷移回数が最も大きい値が答えを支配する。例えばそれが9なら、 9->8->6->2で3回操作をして、値5を含めた集合を取って5->0をするので答えは4回になる。
H == 1の場合、あるグリッド5が、表全体を二分する。そして、左側の集合が5以下に遷移するのに必要な操作回数 + 右側の集合が5以下に遷移するのに必要な操作回数 + 1回が答えになる。
制約は小さいので、「表全体を二分するグリッド5」は全探索できる 感想
H==1のケースに気づくのに40分+4WAくらいかかって険しかった。
グリッドで高さ or 幅が1のケースがコーナーになるのはあるあるなので気をつけたい...
C
は死亡のC~
「木にすると嬉しそう」までは考えたけど、それ以降詰めることが出来ず of the DEAD