パナソニックプログラミングコンテスト2020 - E - Three Substrings
概要
ある文字列sが存在し、次の操作を考える。
- sの空でない連続部分文字列を1つ選び、これをpとする。pのそれぞれの番目を'?'に置き換えるorそのままにする。
この操作で得られた3つの文字列、a, b, cが存在するとき、元のsの最短の長さを答えよ。
制約： 1 <= |a|, |b|, |c| <= 2000
ACするまで
1. 文字列は3つしかないので、3!=6通りの順番全部試して、その順に挿入していけばよくね？
2. 文字列に完全に含められるのならば、完全に含めて、そうでなければできるだけ長さが短くなるように合体させる。
3. 実装していて、時間が足りねーとなって終了
4. 直感的に、次のような greedy が思いつきやすいかもしれません。(中略)実はこれには反例があります。(by 公式editorial)
自分の解法は嘘解法でしたぁ！
5. そうでなければできるだけ長さが短くなるように合体させる。->これは最善とは限らないのです。
6. 貪欲に飛びつく前に考えるべきは、愚直で間に合うか否か？今回は愚直でやれば(工夫をすれば)間に合う！
7. りんごさんの大変洗練されてる実装を参考にしながらAC。
考察
競プロの基本は全探索！(素振り)
基礎体力がないと今回のような問題の全探索は見抜けない。
ひとまず、1つの文字列(ここではa)を固定して、ほかの2つはそいつからどれぐらいズレてるか？を全探索するとどうなるかを考える。それぞれの長さがたかだか2000なので、-4000から4000までありうる。(ここで、連続してない場合などについては考えなくていい。なぜならば、連続してない部分を削ったものもこの全探索の中に含まれていて、正しい答えを出すため)
これでは2乗の計算量になる。
あとやるべきことは、その状態で条件を満たすのか？を判定することである。
愚直にやると、判定にも線形時間がかかるので、結局3条になり険しい。
しかし、判定が依存してるのは、aとの相対位置である。つまり、相対位置が同じのものはわざわざ何度も計算する必要がない。
また、3つしか文字列がないので、一致するかは、
aとbはどうか？bとcはどうか？cとaはどうか？
の3つを調べればよい。
というわけで、2乗の計算量で実装できる。
実装上のテクニックとしては、aとの相対位置ごとに一致を探すのもいいが、実装は大変である。
重複してない部分はノーカン、毎回1文字ずつ照合するものをずらす(それはそう)という2つの性質から、
for (int i = 0; i < A; i++) for (int j = 0; j < B; j++) if (!match(a[i], b[j]))ab[50000 + i - j] = true;
このように書くと簡潔にすべてのオーバーラップできる。実装上のテクニックとして覚えたほうがいい。
ACソースコード：
Submission #10898306 - Panasonic Programming Contest 2020
一言
久々の通常記事だなぁ(サボリ)
