20191116_ABC145/

README

ABC145 感想

Dで詰まってしまうと慌ててしまうので、やはりここまでスムーズに通すことが前提条件。 一つの手法にこだわらず、最初はBFSで思考を広げるのが良いのかもしれない。

• Aは落ち着いて事実を整理。 r*r が答え。
• Bも落ち着いて、計算量が許すのでruneスライスを文字列にキャストする。
• Cは久しぶりに順列のライブラリを呼び出した。もう少し早くと期待が、これ以上焦ると良くない。
• DはDPの式は一瞬で建てられてしまうだけに良くなかった。圧縮の方法を探って時間を費やしすぎてしまった。
  • DPするにしても、事実の整理のために式変形を紙とペンで行うことはとても重要。
• Eはコンテスト後に復元を使った解法を書き終えてみたが、嘘解法らしい。
  • 時間でソートする模範解答をしっかりと理解する必要がある。
  • 典型: ソート処理などしてからDP
    • DPでも嘘解法やっちゃう時があるんだ。。というアホな感想を抱いてしまうので。
  • 両側からGCDを累積させて計算したことがあるように、今回も左右からDPを2回計算しておくことで、間のものを最後に注文するものとして選択できる。
    • DPの中で落ち着いてこれをやるのは難しそう。

のしさんの嘘解法チェック

3 3
1 1
1 1
2 3

答えは5になるが、ナップサックDP＋復元だと4となってしまう。

maspyさんのツイート

E。 「ソートの応用」と位置付けるよりは、

・最適解を1つとる ・最適解に仮定できる構造を探す ・構造が見つかったらそれをもとに探索空間を小さくする

というような思考手順と理解すると良いと思います。かなり大事な典型ですね。

dpと組み合わせることも多いです。（EDPC-Xなど）