一問一答十二週目 - 競プロ引退しました。

AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。

　6→5→… となるように目が出るケースを考えればよい。

　典型的なグラフ探索問題という印象。DFS か BFS をきちんと勉強する必要があります。

　条件分岐の洗い出しがキモ。

　「一個の S と二個の C で SCC を作る」場合と「C 四個でSCCを作る」場合が考えられる。

　前者は(Sの個数 x2) ≦ (Cの個数) の場合で、(Sの個数) + (余ったCを4で割った商)が答えとなる。後者は (Sの個数 x2) > (Cの個数) の場合で、(Cの個数を2で割った商)が答えとなる。

　公式の解説通り、移動距離の総和が初めてXを超えるような時刻 t を愚直に求めればよい。

　スピードはまだまだだけど、きちんと考えれば割と太刀打ちできるようになってきた気がする。