第9回(2010年)日本情報オリンピック合宿 エア参加記&感想
遅ればせながらエア参加。
辛うじて全部時間内に自力で解法が分かって良かった。危ない危ない。
応答(部分)がどのくらい部分なのか不明なので、厳密な点数は算出不能。
1日目 JOIポスター
再帰一発。
1日目 戦国時代
よくある座標変換u=x+y,v=x-yをして、後はひたすら泥臭くカウント。
バグ嵌ったりして結局2時間くらいかかった。もっと綺麗に解ける気がしてならない。
1日目 階段
まず尺取メソッド(これって公式用語じゃないよね?)っぽいことをやった後で、ちょっと捻ったdp。
2日目 足し算
今回の合宿中最大の重問……と言っていいよねぇ? 情オリへの好感度がごりごり下がるレベル。ねがぁ。
重実装ゲー。これに無駄に苦戦したせいで、2日目は制限時間ギリギリだった。
2日目 DNAの合成
setに頼りつつ、うなうなdp。
DNAをreverseするとちょっぴり幸せになれた。
2日目 地域
まずd_maxを決め打ち2分探索する構造に書き換えて。
YES,NOの判定は、適当な親ノードを決めて、葉の方から昇っていくdp。
自分を親とする部分木を考えたときに、「分かれた地域の数」+「自分より上にあとどれだけ伸ばしてもセーフか」を保持してだいぱる。
……で、解き終わった後で解説のスライドを見たら、まず「木をn個に分ける = n−1本の辺を切る」ことに気付こう、とか書いてあった。
そんな難しいこと言われて初めて気付いた。
3日目 本選会場
Union-Findるだけということに気付けばUnion-Findるだけ。
3日目はシムロードがあるからこんな問題に時間をかけている暇はない。
3日目 かくれんぼ
クエリが与えられる問題を見たら平方分割を疑え。
鉄則、ていうかお約束通り、平方分割したら後はただの区間ゲー。(≠平方分割木)
どうせ、セグメント木とか平方分割木とかでも解けそう。俺はどっちでもいいけど。
3日目 シムロード
手動一択。
残った2時間のうち、30分を便利ツール製作(更地の連結チェッカーとか)に充てて、100×100サイズの入力3つを、それぞれ30分ずつかけて手動。
とりあえず間に合ったけど、これでどの程度のスコアが得られるのかは不明。
4日目 コンテスト
箸休め。もとい骨休め。もとい脳休め。
……ところで、この問題文、2度閲覧した場合にどうなるか書かれてなくないですか?
4日目 高速道路
クエリが与えられる問題を見たら平方分割を疑え。
無理矢理なアダ名づけを見たら叙述トリックを疑え、くらいには鉄板法則。
しかしまあ、妙に実装が重かったので、もしかしたら全然違う別解があるのかもしれない。俺はどっちでもいいけど。
4日目 プラグ
なんとなくいもすさん臭のする問題。(てきとう)
一意解ならば一つに決まる箇所が必ずある、を示すのに妙に手間取った。