20191019_ABC143/

README

ABC143 感想

23分4完で1400弱。 Eのダイクストラは合っていたがバグを取り切れなかったので、AOJを引き続きやっていきたい。

• AはMax関数作っておこう問題。
• Bは愚直に2重ループで。
• Cはランレングス圧縮したが、文字が変わる境目の数を数えても良いっぽい。
• Dは2つを固定して二分探索、バグらせて数分無駄にしたのが悔しいが、まずまず。
• Eはワーシャルフロイド2回というのがスマートな想定解法。
  • 自分は全頂点ダイクストラをやった。
  • 補給回数と残ガソリンを記憶させて補給回数優先で有効な方を記憶するdpを行う感じ。
  • 大枠はうまくできていたが、細かい部分でタイポしたり、flagがないせいでTLEしてしまったりした。
  • AOJのダイクストラ実装を螺旋本などでしっかり学習したい！

Eの復習（2019-11-24）

コンテスト後に強いテストケースが追加されたため、 priority queueを使ったダイクストラでは弾かれてしまった（密に辺が張られており、無駄な更新が多い場合？）。

これに関しては、螺旋本で解説されている、愚直な O(|V|^2) のダイクストラだとうまく通る。

ワーシャルフロイト解法

燃料 L で到達可能な街間のコストを1と設定した上で新しいグラフを作り、 その INF or 1 なグラフに対して再びワーシャルフロイトを行えば良い。

最初は燃料が満タンの状態からスタートすることを踏まえ、 答えが存在する場合はその答えに -1 することを忘れないようにする。