JOI 2011 Round 2

本選という名前が付いているらしい。

1.惑星探査
枠の中のJ,O,Iの数を数える。Jungle,Ocean,Iceとかまた良く考えてるなぁ。
中身はこの間出したTKC3のKOG*1を3回やるだけ。実装量があれなので時間がかかった。20分くらい?

2.古本屋
DP。適当にソートする。これをナップサック問題というらしい。

3.JOI国の買い物事情
どうみてもDijkstra。本選2日前にDijkstra書いて覚えて(そのときは実装に1時間かかりました)、なぜか2日後であるJOI本番に出るとは。20分で書きました。
ただし問題文が読みづらい。長文だからなだけかも知れない。最後は(p+q+r)/2を各辺で試すと答えが出る。

4.サンタクロースが出る問題
これは解けていないが、JOIで出せるぎりぎりの数学ゲーのような気がする。

5.微生物実験
Greedyからにぶたん、SegTreeとするらしい。
Greedyに気がつかない人なので、DPで解いていた。しかもO(n^3)。
部分点でさえ入る保障がない。Greedyは苦手というかあんなの気がつくかよ(最小値だけ考慮というとこまで来てあの解説の図もかきました でもやっぱり僕にはDPしか見えません)

バグ死があると不参加です。
バグ死がなくても周りがいいと不参加です。
せいぜい良くても最下位です。
自分が解けないというより周りのレベルが高くなりすぎて大変です。
レーティングがほしいです。

追記
事故で64点もとってしまいました。全部通った+DPで5が点数取れたみたいです。

どうやらJOI Round 3にはすすめるらしいです。

*1:http://ux.getuploader.com/tozangezanSOURCE/download/53/prob..zip