脳log[20221011]

2022年10月11日 (火) [AtCoder] 精進。日曜にあった ARC150-C「Path and Subsequence」(青 diff)。答えを見ました。「「各頂点にたどり着いた時、最も悪くてBの何番目までを部分列として持った状態になっているか」を始点から各頂点までの距離としてダイクストラ法をする」■当日は愚直 TLE 解を書いていた>提出 #35545127。TLE を解消するには状態をまとめなければいけないと考えたのだけど、単純パスであることを保証するためにパスを記録することが避けられないとも考えていた。たとえば B 数列に要素が 1,2,1,2 と連続する部分があり、グラフ上の隣接する２頂点に対応する A 数列の値が 1 と 2 であるときに、２頂点を何度も往復することで B 数列上を 1,2,1,2 と進むことは単純パスではないために許されない。当日考えていたのはここまで。ここで２×２の状態を考えてみよう。単純ではないパスを通る不正を行って N にたどり着き、その時点で B 数列を最後までたどっている場合と B 数列を余らせている場合。不正を行わず単純パスで N にたどり着き、その時点で B 数列を最後までたどっている場合と余らせている場合。この問題を解くにあたり見つけたいのは、B 数列を余らせた状態で N にたどり着く単純パスの存在。それが存在すれば答えは No だし、見つからなければ答えは Yes。あってはならないのは、B 数列を余らせた状態で N にたどり着く単純パスが存在しないのに、同じ頂点を何度か通る不正を行った非単純パスでは B 数列を余らせた状態で N にたどり着けるという事態。ちょっと考えればわかるけど、同じ頂点を何度か通って N に至る非単純パスは寄り道を省いて単純パスに書き換えられる。寄り道をすることで生じる違いは、B 数列を余分に先に進められること。B 数列を不正で先に進めても間違いは生じない。というわけでパスを記録する代わりに B 数列上をどこまで進んだかで頂点の状態を表すことができ、その最小値を代表にすることができる。■提出 #35571487 (AC / 397 ms)。道具はすでに持っているので実装はできる。シンタックスエラーのようなすぐわかるミスを除けばバグなしで上から下まで書き下している。足りないのは考える頭。これは道具が足りていないよりも厳しい状況。■■■A 問題「Continuous 1」(緑 diff) は場合分けでやった。2WA と 2RE のち AC。尺取りの方が間違えにくいらしいけど、解法を選ぶ贅沢は与えられていない。場合分けとはこう……。文字列を 0 で切って 1? だけからなる文字列について考える。長さ K 未満の文字列が 1 を含んでいたら 0 通りだから No。長さ K 以上の複数の文字列が 1 を含んでいたら 0 通りだから No。1 を含む文字列が 0 個のとき、? からなる長さが K より大きな文字列が存在してはならず、長さが K の文字列が１つだけ存在するときに限り答えは Yes。1 を含む長さ K 以上の文字列が 1 個だけあるとき、それの長さが K なら答えは Yes。K より大きいときは 1 の左右端の位置を調べてその幅が K より大きければ No。K ならば Yes。K 未満で左右に ? が存在していれば No。さもなければ Yes。これで全部。複数考えられる場合と１つも考えられない場合をどちらも除外しなければいけないのだけど、意識の切り替えがうまくいかないときに間違えると思う。■地獄の場合分けといえば ABC160-D「Line++」(緑 diff) を思い出す。他に解法がいくつもあって全然場合分け地獄に入り込む理由がないんだけど、時間内に AC にたどりつけない人間が解法を選べるわけもなく>20200701p01。