AtCoder Regular Contest 024 B - 赤と黒の木 - 思考のジャンプ幅が狭いなら，飛ぶ回数で補えばいいじゃない！！

f:id:hiro_kato:20190522105030j:plain

結論

色の変化に関する規則性・法則性を見つけるため書き出す．シミュレーションするときには，数が増えた場合や境界付近がどうなるかを愚直に確認する．
規則性・法則性を数式で表現できないか試す．
環状のままだと対処しづらいため，規則性・法則性を保持したまま，直線として扱えないか試す．
コーナーケースの特定には，サンプルをフル活用するととにもに，制約条件から想定しうる極端な条件が揃ったときを書き出してみるとよさそう．

はじめに

AtCoderで出題された問題を復習しています．
公式解説や上位陣による解説ブログを読んで，自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います．

想定読者

解説を読んで解き方はわかったものの，なぜその方法を思いつけるのか？と思った方．

筆者の実力

AtCoderのレートで緑下位．

記事の特徴

なぜその発想に至ったのか，どうしたら解法を詰められるかといった点について，筆者なりの解釈をつづります．
試行錯誤した過程から，得られた前提知識や着眼点を言語化していきます．
間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．
- 連絡先：@k_hiro1818

問題のリンク

B - 赤と黒の木 (100点)

ACコードの一例

発想・解法とそれらを引きだすための方法・解釈

答えとして出力すべきものは何か?
- すべての要素の色（赤・黒）が変化しなくなるまでに必要な日数
- 上記の条件を満たさない場合は-1
制約条件で気をつけるべき点はないか?
- データ数 $N$ が最大で $10^{5}$ であるため，計算量が $O(NlogN)$ よりも大きいとTLEする．
最初の一歩をどう踏み出せばいい?
- 問題文や制約条件を読んでから，サンプルを見る．
- ある要素 $i$ とその両端が同じ色のときに，色が変化する．
- 色の変化に規則性・法則性がないか?をノートなどに書きだしてみる．
答えを導く大まかな手順はどうなっている?
- 色の変化に規則性はないか? を確認
  - 同じ色の要素が3個，4個，5個，6個，…と続くと，色が変化しなくなるまでに必要な日数はそれぞれ2日，2日，3日，3日，...となる．
  - 異なる色が隣り合う部分では，色の変化は発生しない．
  - 以上から，同じ色の要素の数が最長となる部分が，最も色が変化する回数が多そう（=必要な日数が最大となる）
- 規則性・法則性を数式で表現する．
  - $ceil(x / 2)$ と表現しました． $x / 2$ 以上の最小の整数を表します．
- 与えられた要素が環状になっていることへの対処は?
  - 規則性・法則性を満たしたまま，直線として考える．この問題では，色が異なる境界で切ることで達成できる．
- コーナーケースとなる条件を列挙する．　　
  - すべての要素が同じ色のとき，変化が発生しない．
  - サンプル2のように，環の両端（ $color_{1}とcolor_{n}$ ）が同じ色のとき，かつ，要素の数が全体で最大となる場合．
実装のポイントは?
- 赤と黒がそれぞれ連続している登場する回数を数えて，配列やリストで管理する．
- 組み込み関数や標準ライブラリを活用する(max(), math.ceil()，enumerate(), set(), len())．