ABC061

README

ABC061過去問感想

• A問題、B問題は特になし
• C問題は考え方はあっていたが、新しくテンプレートに記述した標準入力の遅さがネックになってTLEしてしまった
  • 場合に応じてテンプレートのコメントアウトを切り替える（アホな）運用をしていくことにする
  • 自分は辞書を使ったが、キーが小さい範囲の整数のときは、配列を確保してしまったほうが速度的にもコードの読みやすさ的にもいいと思われる
  • n <= 100000 における O(nlogn) は100msec程度に収まっているので大丈夫
• D問題
  • 一工夫してベルマンフォード法に帰着する問題
    • 一工夫する前から負のエッジが存在し、始点と終点が固定されていることからも、ベルマンフォード法を用いるという発想にたどり着くのはそれほど難しくなさそう
  • ACするためには、終点が負の閉路に含まれているかどうかまで導かないといけない
    • 単に負の経路を検出するだけでは不十分
      • 負の経路をたどった場合に終点にたどり着けるかどうかはわからないため
      • 例えば、有向グラフのため負の経路に閉じ込められて、終点に向かうことができるケースなどは想定できる
  • ともかくベルマンフォード法の要点を理解するのに良い問題

D問題の復習（2019/07/20）

ベルマンフォード法の復習とした。

• 負の閉路がない場合のベルマンフォード法は、n-1回の更新で十分だが、多少更新回数がオーバーしてしまっても問題なさそう。
• 解答PDFでは、負の閉路の検出パートで「距離的な更新が起こらなくても、直前の点のループ判定が true の場合は、先のノードも true とする」というふうにあった。
  • が、その部分の条件判定部分が無いコードでも通ってしまった。。
    • ひょっとしたら部分的に嘘解法になってしまっているかも（テストケースが若干弱い？）
      • もしかしたら十分なのかもしれないが、ちょっと自信をもって判断ができない。
• 個人的には、負の閉路判定パートでも頂点数のループで十分、というところが重要だと感じる。
  • isRoop のbool値がグラフ全体に伝播するのに、もともとのベルマンフォード法と同じく頂点数のループで十分、という考え方。