JOI合宿・詳細
Day0
- 学校の終業式にちゃんと行き、その後NTTDataの研修センターへ行く
- 適当にプラクティスをやって、オリンピックセンターへ向かう
- 最初の講義はｈｏｓさんが担当で、決定不能・NP困難・多項式時間で解ける問題の紹介をやった
- 夜はjubeat板とかを使ったり、いろいろしていた
Day1
- かなり寝付けなくて、かなり起きていない状態
- 朝ご飯が食べきれなかった気がする（最後まで食欲は少ないままだった）
- 研修センターへ行き、競技始まる
- まずは1問目を見て、まあオイラーツアーしてセグ木使ってDPすればできるだろうと思う（大嘘）
- 2問目をみて、直方体に含まれる格子点の和集合の数をもとめればよいと分かる
- 3問目を見て、タイムリミットが危ないが全探索＋決められた点がなくなったら終わりでよいだろうと思う
- 1でやろうと思っていたアルゴリズムに反例が見つかったので、3をまずやって、そこそこの時間でAC
- 2はやれば出来そうだと思ったので、平面操作して、上から頂点を追加していろいろやろうとした、が、頂点を管理するのではなく直線でエンベロープのように管理しようとして死ぬ
- 実装が終わる気がしないので、1を頑張ってみる。でも結局長さがiの時の最短のビルの高さでDPするという発想は生まれなかった
- どうしようもないので、1で30%に逃げる
- 大分頭が死んできていて、2は10%しかやる気が起こらなくて、仕方なく10%を書く
- 競技終わる。お通夜。本気で競技プログラミングやめようと決意する
- 実は他の人もお通夜で、競技プログラミングretireを決意していたらしい。問題セットやばすぎ
- 準急さんはよさげな点数を取っていたらしい。裏山
- 夕飯食べ、id:iwiwiさんの講義。Link-cut Treeは神がかり的らしい。永続とか、平行二分木、動的木と3大ヤバデータ構造を紹介していた
Day2
- 満点宣言とかして、意識高い人ぶる
- 1は、点集合に対してそれを覆う最小半径の円を求めるやり方は知っていたので（少しずつ動かす）、点集合に分けられれば簡単。random_shuffleしてある点から一定距離内に点があるならそれを取るというやり方で2分探索するやりかたでやる。しかし半径0の円が大量に出て、バグかと思うものの見つからず、諦め。諦めるべきではなかった
- 2やばすぎ 幾何やばい
- 3は回転処理やるだけで10%を取れるけど、満点解法としてクエリの平方分割とかを考えたけどダメだった
- 1はやっぱり4点だけだった。夜考えてみると初歩的なバグが見つかり、大体満点を取っていた人のへなちょこアルゴリズムよりいい自信はかなりあったので、非常に萎える
- 14点（超絶望）
- wataさんの講義はかなり面白かった。枝刈り最強ではと思った（小並感）
Day3
- さすがに今日は"いい成績"を取らないと死ぬ。死ぬ。
- 1は、よくある平面走査＋segtree これをとらなければ解く問題がない当たり今年やばすぎ
- 3は、20%はPKUの問題そのままで、あとはある点が使えないときそのまわりの2点がつながっているかどうかのみに関心があるので、2重辺連結成分分解とかやればよいのではと思いつつも、実装とかできず死ぬ
- 2は、50%でN<=30だったので、昨日の指数時間最強の流れかと思い探索を書く。でも実際はO(2^n^2)=O(2^900)で通るはずないだろ！
- 130点（絶望）
- imosさんの講義は実用的でありがたいなぁと思う
- 解法説明では、3は二重辺連結成分分解とかではなくlow link使えばどうにかなることを知る。ただ、思考停止して知識に持ち込めるならそれでよいのではとも思う（まだジャッジしてないので自分のアルゴリズムが正しいかどうかは不明）
Day4
- 最終日 落ち着くことを考える
- 1はよくある回転系では。ただ実装が意外にも詰まり、1時間以上掛けてしまう。setに頼らず、どこの区間を使わなくて済むかを考えて累積minを取る感じでようやく通した
- 2は解かせる気がなさすぎw 10%を普通に狙う
- 3は、MSTやってくだしあと読めるので、MSTを書く。座圧後の同じ区間の処理がやや面倒。ただ、結局満点解法はまたも分からなかった。hoscon2011であったような、隣への辺のみを保存するやり方が想定解法
- 講義はkinabaさんで、形式言語理論について。BNFとかは普段書いてるが、グラフで表すのはAho以外ではやったことがないので面白
- 2は永続赤黒木（せきこくもく）で、やはり解かせる気がなかった
- 競技が終わったので、この日はかなり起きていた。こでふぉdiv2に出た(http://topcoder.g.hatena.ne.jp/hogloid/20120325)。JOIの良問性を実感。
- 音ゲーの曲ディクテーション遊びをやって、"Sweet Rain"が"いっぺん"にしか聞こえない自分の耳に絶望。"包丁タオルで刺す"とかのやばげフレーズしか出てこなかった
Day5
- naiさんの講義という名のショーとこーディング大会。終始semiさんがぱない
- メダルとか色々もらう。代表発表Phase怖すぎ。
- 実は代表で、目標は謙虚になることといったら驚かれた。ドヤ顔がやばかったらしい
- 懇親会は結構おいしかった。りんごさん面白い
- この日も夜起きていた。きゅうりの見る動画汚すぎ
- JAPLJさんphiさん（JOIOBの方）とCOCI（こし）過去問をやっていた。
