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

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

　素直に解けばよい。計算量について学べた。

　二分探索して ${x}$ を絞り込む。迷路の探索方法にそろそろ慣れたいところ。

　ダイクストラ法などの最短経路問題。なにを記録するのか明確に意識すること。町の探索に、キューを使用した。

　まずはスタート兼ゴールである地点1に隣接した道を除き、非閉区間の有向グラフにおける全点対の最短経路を調べる。その後、地点1に隣接した道から2つ選んで、総合で最短経路になる閉路を見つければよい。

　使用したアルゴリズムは、ワーシャルフロイド法。python の場合、scipy ライブラリの関数を利用できる。

　飴の数え方を工夫する。各行に置かれている個数と、各列に置かれている個数を記録する。そして、 ${i}$ 個の行と ${k-i}$ 個の列の列の組み合わせを数え上げるのが基本方針。

　但し、高橋君が立っているマスに飴が置かれている場合、二重にカウントしてしまっているので、それを考慮する必要がある。高橋君が立っているマスに飴が置かれていて且つ合計が ${k+1}$ のときはホントはピッタリなので答えに加える。 ${k}$ のときは、ホントは足りてないので答えから除く。

　python の Counter メソッドが数え上げに便利。

　貪欲法。一度選択した情報を再度選ぶことはない。今回の問題のように、一直線上を移動し、同じところに戻る必要もなく、ひたすら進めるだけ進むような問題に応用可能。

月～土に解いて、日曜にふりかえるのがよさそうに思えてきた。