UTPC2011
ひっそりと参加。難しすぎて泣いた。
B. (iwi)
解けた。
文字列を前後から比較するだけ、、、と思ったら文字が「(」「)」とかもひっくり返るから、それは別に比較しなくちゃいけなかった。
D. 停止問題
解けた。
メモしながらBFSで回ってゴールへ行けるかどうか確認するだけっぽい。メモは、、、「位置」と「メモリの状態」だけかなぁ、、、「方向」もあった。。MemoryLimitは、、大丈夫。いけた。
E. ファーストアクセプタンス
解けなかった。
いきなり難易度あがった、、、？とりあえずO(n^2)ぐらいまではいけそう(メモしてたのに無視)
。
似た問題見たことあるなぁと思い、蟻本の区間スケジューリングの部分を復習。「終了時間が速い順に選んでいく」貪欲法。たぶん似た感じでいけるんだろうなぁ、、、書いてみる。WAWAWA。
とりあえずsmall狙いでいってみる。。。明らかにTLEだけどdfsで書く。WA。
メモ化、、、？？解いた順番とかメモできないし、、ソート順でなんとかならないかなぁ。。WAWAWA。
や、やはり、DPでちゃんと考えなければ、、、？？
解いた順番とか保持しなくていいし。どの時点で最大何問解けるかーとか立てるのかな、、
試行錯誤。。わからん！！！
結局、他の問題読みにいったりなんだりで終了。
F. 全域木
G. プログラミングコンテストチャレンジブック
H. キャッシュ戦略
I. ビット演算
難しい。
J. 乱択平衡分二分探索木
K. 巡回セールスマン問題
L. L番目の数字
異次元すぎてわからない。
反省
4完で80位。さすがutpc。レベルが高いっす:(
E以降をスムーズに解けるようになりたい。。
DP問題をより解きまくって、考え方になれるしかない。
