AtCoder Grand Contest 052 E. 3 Letters
atcoder.jp
苦労した問題は後々のために記事を書いておこうかな・・・と
自力でのACは無理で、公式解説を読んでも理解できませんでした。
結局、以下のページを大いに参考にしました。
AtCoder Grand Contest 052 A,B,C,E問題メモ [いかたこのたこつぼ]
私の解法は、いかたこさんのページで紹介されている2つの解法をマージしたようなものになっています。
解説 (というか思考過程の気持ち)
端を例外とすると、できる操作は ABA → ACA みたいに、同じ文字に挟まれているときだけです。まず、文字列なのでこの操作における不変量を考えたくなります。
ABCを012に対応付けます。mod3で隣接項の差を考えてみましょう。
隣接項の差は
ABA は 1,2 (B-A=1 , A-B=2)
ACA は 2,1 (C-A=2 , A-C=1)
となります。
これは、2である項から1を引き、隣の1に1を加えるという操作と言い換えられます。
不変量として、「隣接項差列の総和」が使えそうです。これを活用したい！！
端の処理を不変量に組み込む方法を考えます。
まず、隣接項差列が初項の情報を持っていないのが嫌です。初項の情報がないと、列から文字列を一意に復元できません。
そこで、隣接項差列の先頭に初項の値をpushしてみます。
ABAならば、{0,1,2} CBAならば {2,2,2} です。
さて、この列で初項を変更するとどうなるでしょうか？
ABA→CBA は {0,1,2}→{2,2,2} なので、残念ながら総和は不変ではありません。
でも、CBAが {-1,2,2} ならばどうでしょうか…？
「初項の値をpushする際、mod3で正しい値なら何をpushしても良い」というルールにすることで、初項の情報を追加しつつ、「総和が等しい」条件も守れました。
こうすることで、初項に対する操作を「ある値から1引いて、隣を1増やす」操作にまとめることができました。
では、次に最終項の操作を考えます。
ABA→ABC とすると {0,1,2} → {0,1,1} となります。
これでは総和が変わってしまって嫌です。
これは、適当な(情報を持たない)値を後ろにpushすることで解決できます。
ABA を {0,1,2,-3}
ABC を {0,1,1,-2}
とします。(総和が等しいと嬉しいので、総和が0になるようにpushしました)
すると、最終項に対する操作も「ある値から1引いて、隣を1増やす」とみなすことができます。
このようにして作った列 (エンコード済列と呼びます) の集合から、元の文字列への写像は単射となっています。
また、「ある値から1引いて、隣を1増やす(ただし、端以外は1,2を保つ必要がある)」操作の集合から、元の文字列への操作への写像も単射です。
後は、この列上での最小操作回数(最短距離)を求めればOKです。
さて、２つの総和が等しいエンコード列間の距離を考えてみます。
これは、以下の方法で求められます。
まず、累積和を取る。(サンプル1が例です)
CABC : {2,1,1,1,-5} → [2,3,4,5,0]
CBAC : {2,2,2,2,-8} → [2,4,6,8,0]
次に、縦で見て差の絶対値を取ります。→ [0,1,2,3,0]
これの総和 (=6) が答えです。
証明は面倒ですが、累積和の差は「それより左に1がどれだけ余っているか？/足りないか？」を表していることを考えると分かります。
また、値が移動していく過程を考えると、「最初・最後以外の項は全て 1,2 の内のどちらかである」という条件を保ったまま移動させることが可能で有ることが分かるので、これが最小回数と一致します。
距離の求め方が分かったので、最後に元の問題を解きましょう。
まず、文字列Tをエンコードします。
次に文字列Sをエンコードするのですが、エンコードは全射ではあるけれど単射ではないので、いくらかの自由度が有ります。具体的には、初項を mod3 が等しい範囲内で自由に変更できます。(併せて最終項も変わります。)
Sのエンコード列の初項を増加せていった時、Tのエンコード列との距離は下に凸な形になります。そのため、三分探索で最小の値を求めることができます。
以下はACコードです。
