第10回日本情報オリンピック(JOI)本選

出来事

学校でゼミをやってから代々木に直接行った。
いつもの面子との再会と、きゅうりperyaudo組との遭遇。
Practiceはほとんどやらずにずっと駄弁っていた
ちなみに今回はVimではなくEmacsを使うことにした
名刺はPractice中に配りまくった。しかし、40枚刷ったのに参加者が60名いたので全員には配れなかった。
宿泊棟ではsemiexpの持ってきた魔法少女リリカルなのはVividとかを読んだり、ニコニコでお兄ちゃんのことなんかぜんぜん好きじゃないんだからねっ!!を視聴したりしていた。僕はなれるSE!を持ってこようと言っていたのに持って行かなかった。yeyさんがみつどもえを持ってきていた。魔法少女プリティ☆ベル読みたかった。
周りはプログラム書いてた。
蟻本持ってる人多すぎ！
24:30くらいには就寝した
6:00くらいに目が覚めた
今回の本選は開始すぐに問題をネットで公開したらしい。すごい。
本選は去年より易化していたような気がするが嘘かもしれない
後輩は残念な成績だったようなので今後に期待
チューターがいっぱいいた
iwiがいたのでサインを要求した
semiexpは眼鏡を取ると怒る
Queueべぇは恐ろしいという話に。
「よく説明するアルゴリズムは解説用のアニメーションを使い回すべきではないだろうか」という話をした。

1. 惑星探査 (Planetary Exploration)

最初にN*Mの文字行列が与えられる。その後クエリとして矩形が与えられるので、矩形中に存在する文字の個数を数えよ。

2次累積量を計算すればよい。

2. 古本屋 (Books)

N冊の本があり、基本価格とジャンルが決まっている。このうちK冊の本を売る。各本の買取価格は「基本価格+そのジャンルの買取冊数-1」で与えられる。買取価格の合計値の最大を求めよ。

ジャンル内では必ず高いほうから売るのは明らかなので、それぞれのジャンルについて何冊売れば何円儲かるかが決定できる。あとはナップサック。

3. JOI 国の買い物事情 (Shopping in JOI Kingdom)

重み(長さ)付き無向グラフが与えられる。いくつかの頂点は目的地である。辺上の点または節点で、目的地のいずれかに到達するための最小コストが最も大きいものを求めよ。

Dijkstraに全ての目的地を始点として突っ込んで節点のコストを求める。辺上の最大コスト点は(cost[a]+cost[b]+length)/2で求まる。

4. 歩くサンタクロース (Walking Santa)

完全な格子グラフ上に家がN個ある。サンタは最適な始点を選び、そこからそれぞれの家と始点の間を往復する。最初に始点に到達したときから、全ての家に到達し終わった瞬間までの移動距離の最小を求めよ。

Manhattan距離なのでxとyは分けて考える。どの家を終点にするかに応じて、最適な始点の位置は中央値または中央2値のいずれかとして決まるので、コストは事前のO(n log n)の計算によってO(1)で求まる。

5. 微生物実験 (Bug Party)

微生物がn匹いる。各個体には放出量と許容量が割り当てられている。その部分集合を選ぶとき、放出量の平均値がどの個体の許容量より小さいか等しければ可能であるとする。可能な最大の部分集合を求めよ。

部分集合の個数をkとおくとき、kについて二分探索すると、某IOIの問題になる。すなわち、優先順位つきキューに許容量の降順で突っ込み、不可能な部分集合の場合はキューから放出量の降順で取り出す。これでk以上について可能かがわかる。一種のshakutori methodである。これでO(n log^2 n)。

Segment Treeを用いた解法でO(n log n)があるとのこと。