DPその3 少し苦戦中
30日経ったので毎日書くことはやめにして、ここからは何日かに一度まとめて投下していきます。まずは100選の方の進捗から。実はあまり進んでいなくてまだQ49とかで止まっているのだが、、。
45 AOJ 2199 - 差分パルス符号変調
ナップザックDP最後の問題。正直題材にあまり興味がそそられないのだがまあやるしかない。計算量的には全然いけるはずなのに初めTLE。おかしいな。結局細かくいじったらギリギリ通ったけど何かモヤっとする。unordered_mapを使っているのがいけないのかな、という気もするけれど、だからといって代わりになるものも思いつかない。(この件がきっかけで先のコンテナの記事を書いたのだけれど)
46 ALDS_10_B - 連鎖行列積
連鎖行列積。定番問題…なのかもしれないけれど初めてやった。初め区間DPではなくナップザックDPで解こうとして失敗して一度仕切り直し。結局そこからも20分くらいかかった。。というのも、vectorでいちいちtemplateの引数書くのめんどくさいから省いていたら、どうもtemplateの引数推論ってC++17からしか対応していないらしくて。ノーマルC++で実行して思いっきりCE出しましたはい。てか何でAOJってデフォルトのコンパイラC++なの？？
47 JOI 2015 本選 2 - ケーキの切り分け 2
諸事情によりまだ実装途中。また追記します。
48 AOJ 1611 ダルマ落とし
場合分けするとゴチャゴチャするからあまりしたくないのだが、これはどうしても必要なパターン。想定解は[tex:O(N3)]なんだけど、初め書いたコードは[tex:O(N4)]時間だったので、解説を見てからもう一度書き直し。2回目はわりときれいにコードが書けた。AOJって公式の解説がないからいちいちググらなくちゃいけないのが少しめんどいなあ。
49 DPL_2_A - 巡回セールスマン問題
世にも有名なTSP。いつか高速な解法を見つけてみたいなあ、と夢があるけれど、まずはこの問題を解けなければ話にならない。bitDPの一問目。すべての頂点は一度ずつしか通らないので通ったかどうかをbitで記録できるのだが、そこを見落としてstart=goalの状態で探索してバグって時間がかかってしまった。もったいない。
50~はまたある程度進んだら書きます。
