AtCoder Grand Contest 039（教訓編）
現状
前回のコードでの漏らし（WA）は以下のようなケース
主にT末尾の変更を適宜合計回数から差し引く処理が上手く行ってなかったぽい（他にも色々あるが）
❯ python main.py debug abaaba 1 1 # 出力。K=1はほぼ全探索なのでこっちは正しい ❯ python main.py debug aba 2 2 # abaを2回繰り返すので上と同じ1になるはずだが・・・
反省点と改善点
今回のコンテスト（今までの過去問）を通じて以下の３つを意識していこうと思った
- １．計算量の考慮
- ２．パターンの幅出し
- ３．リカバリ
１．計算量の考慮
「全部試すか否か」と、「全部試さないならどうするか」をまず考える。今回のケース では、
- i . 全探索で間に合うか？ → Tそのものを扱うと間に合わなさそう（間に合いそうなら愚直にやる）
- ii. どういう方針に変更するか？ → Sを考えてTに拡張する（＝TをSで分解する）
となるが、ii. はもう少し掘り下げる必要が多分あって、
- A . やりたい処理をもっと効率的に行う実装が実はある（例：バブルソート→マージソート）
- B . 複数の要素に分解して何らかの計算をし、最後に合算する（今回の問題はこれ）
- C . 法則を数式に落とし込んで解の計算を行う（漸化式とか）
- D . 乱択アルゴリズムを使う（一昨日知ってめちゃめちゃ感動した。後述）
みたいに色んなパターンがありそう。上から順番に考えていくのが効率的かも。
ABC140 - Dの分類をどこにするかがちょっと悩ましいけど・・・。
これの引き出しをもう少し増やしていってうまい感じに整理し直したい。
ちなみに、乱択アルゴリズムは下記を読んで知った（特に25ページ目からの行列の問題の解法がすごい）
www.slideshare.net
元の話に戻り、今回の問題で上記A〜Dを考えてみると、「隣り合わせないための最小置換回数」はソートみたいになんていう名前で呼ばれる処理なのかわからなくて全然ググれないし、ありふれた処理というよりは特殊な処理の気もしたので多分A. は考えなくてよさそう（諦めに近い）
B. の分解を考える場合は、
「元の要素を分解する（最小の）単位は存在するか？」を考えて、存在する場合は以下をどう扱うかを考えればいい
- それ単体での計算結果
- 他と組み合わせた際の計算結果への影響（単位のパターンが複数ある場合、組み合わせ別に考慮）
今回の場合は「隣り合う文字が同じなら置換しないといけない」ことを考えると、
- 「隣り合う2文字のペア」を単位とする（2つが同じ／異なるの2パターンが存在）
- 「同じ文字が1個以上連続する箇所」を単位とする
の2つの単位がぱっと浮かびそう。厳密には端っこに位置する／しないでもパターンを考慮する必要が出てきたりするのでそこは円順列とかじゃない場合は注意しておく。
「それ単体での計算結果」については、Sが100文字以下なので計算量的に上記のどっちの単位を採用しても全探索でOK
ただし、他と組み合わせた際の計算結果への影響については、「同じ文字の連続」については別の「同じ文字の連続」と組み合わせた時につなぎ目で置換処理が発生しない（＝余計な計算をしなくていい）のに対し、「隣り合う2文字のペア」では組み合わせた際にも置換処理するかの判定が必要になってくるので、実装が煩雑になる。
よって、「同じ文字が1個以上連続する箇所」を単位にTを分解し、最後に合算するのがよさそう。
踏まえると、「同じ文字が1個以上連続する箇所」を単位にTを分解し、「その単位自体での置換結果」と、「それを繋げてTに戻す時の処理」を考えればよい。
２．パターンの幅出し
自分でテストする時のテストパターンが貧弱だと考慮漏れに気づかずに火傷をする可能性があるので、どういう基準でパターンを考えていったら良いのかを少しずつ整理したい
計算手法や結果の変わり目がどこかに着目をして、現時点では以下のパターンがありそう。
数値
- 偶数／奇数で（計算手法や結果が）変わるか？
- 正／負で変わるか？
- 0／1／2以上で変わるか？
文字列
- すべて同じ文字／すべて異なる文字で変わるか？
- 対称性のあり／なしで変わるか？
３．リカバリ
２．にも関係するが、今回の問題では「abaaba」みたいな「適当にアルファベット生成して検算したら気づけたじゃん！」な落とし穴にハマったので、これの対策も考えた。
（更に言うと、提出し直してはWAが出てを繰り返してたくさん失敗したので、この非効率さへの反省もある）
そもそも今回の問題だと、「左右のペアを比較して置換をしていく」部分についてはTの長さが短ければ全探索でも解けて正しい答えが得られる。
となると、全探索に頼らない実装をした提出用のコードと計算結果を比較することで、提出用のコードが正しそうかは事前にある程度わかりそう。
そこで、具体的な手順として以下のリカバリも意識しておき、必要に応じて使っていきたい（最初から考える必要はないかも）
① 正しい答えを得られる解き方があるか（全探索とか）
② どの程度まで入力を生成したら必要なパターンをカバーできそうか
主に以下を検討していけばよさそう
- 数値：与えられた数値を大きくしていくときに大きさに依存する非連続な変化があるか？
- 文字列：文字種は何パターン必要か？
例えばSやKが10の時と11の時とで偶奇以外の変化はなさそう
今回のケースでは両隣のアルファベットとの違いだけが問題になるので、アルファベットは3つあれば十分
③ 正しい答えを得られる解き方のコードを書く
④ 入力群を生成するコードを書く
⑤ 提出用のコードの計算部分を関数に書き換える
⑥ 正しい答えを得られるコードと提出用のコードに、生成された入力群を入れて答えを比較する
その他
解き直しは後日。はてブのスタイルだと編集画面だとそんなに読みにくくないのに投稿した記事を見ると読みにくかったりするので文章の見せ方もちょっと意識してみたい気がしてきた。文字が大きすぎるだけなのかな。
