第9回（2010年）日本情報オリンピック エア参加記＆感想
問１ 旅人
入力を読みこみながら各宿場のX座標を計算していけばよい。O(n+m)。
かかった時間：10分くらい。
（感想）
問題文の書き方しだいで、より↑の発想に至りにくくできたとは思うけど、問１だしわざわざ難しくする必要もないのか。
＜結果＞
完答。20点/20点。
問２ お菓子の分割
ちょっと考えてわかんなかったのでとばす。
問３ つらら
「数列が与えられる。単調（増加 or 減少）狭義部分列（※連続した部分列）のうち、和が最大のものを求めよ。」
という問題と同じ。足しつつ順に見ていくだけ。O(N)。
かかった時間：20分くらい。
（感想）
つららたちが伸びて折れて伸びて折れる過程をイメージすれば終わる問題。
意外と実装ハマるひとはハマるのかもね。
＜結果＞
数列の各項が1以上50000未満だったので、何も考えずint ice[N];と宣言し、極値の判定を (ice[i] - ice[i-1]) * (ice[i] - ice[i+1]) > 0 と書いてしまい死亡。
18点/20点。
問２ お菓子の分割
うにっと考えたら解けた。
切る場所が複数箇所あるときは、左から順に切っていくと考えてよい。
また、切った瞬間に、新たに生まれたお菓子のかけらを2人（0君と1君とする）のどちらにわりふるか決めると考えてよい。
int dp[10000][10000][2] を使う。
dp[i][j][k]を、「お菓子の左から0ミリ部分〜iミリ部分以外を無いものとみなしたとき、右端をk君の所有お菓子にしつつ、0君に計jミリのお菓子をわりふるのにかかる最短時間」と定義して、iの小さい順に動的計画。O(N^2)。
かかった時間：計30分くらい
（※１）途中で0君にN/2ミリより多くわりふっても無駄なので、int dp[10000][5000][2]で十分。
（※２）メモリ制限が64MBなので、[i]を決めるのには[i-1]しか使わないことを利用して、実際はdp[2][5000][2]に配列圧縮して組む。
（※３）実行時間制限1秒でO(N^2)なのにN≦10000ってどうなのよ、と思ったけどN≦3000にしてしまうとint dp[3000][1500][2]でメモリが足りてしまうのか。
（感想）
「左からiミリ部分を半々にわける」 → 「左からiミリ部分を0君にjミリわりふる」 → 「左からiミリ部分を0君にjミリわりふって、右端をk君にする」と、dp変数のとりかたを細かくせざるを得ないことに気づいて細かくしていく問題。
情オリって、段階を踏んでいくことで少しづつ答えに近づいていける問題が多くていいよね。
＜結果＞
完答。20点/20点。
問４ 博覧会
なにはともあれマンハッタン距離定番の座標変換「 u = x + y , v = x - y 」。
（距離| x1 - x2 | + | y1 - y2 |が、max{ | u1 - u2 | , | v1 - v2 | }になるので、uとvをわりと独立に考えることができてうれしい）
「Mを求める」を「Mを決めたうえでわりふり（2つのテーマをA、Bとする）が可能かどうか調べる ＋ Mで二分探索」に言い換える。
u座標について。
ソートして、小さい順にU1,U2,……,Unとする。U1の施設にはAをわりふると仮定してよい。
すると、u座標がU1 + Mより大きい施設にはBをわりふらなければならない。
すると、u座標がUn - Mより小さい施設にはAをわりふらなければならない。
それ以外の施設には、どちらをわりふっても、u座標に関しては距離Mオーバーが起こらないのでスルー。
v座標について。
同様にする。
（V1の施設にはAをわりふると仮定する）
これら2つのわりふりを合わせたときに矛盾が起こらなければわりふりは可能。
また、v座標に注目したときのわりふりをA,B逆にしたら、2つのわりふりを合わせたときに矛盾が起こらなかったときもわりふりは可能。
そうでないとき、わりふりは不可能。
かかった時間：1時間くらい
（感想）
今回のセットの中で一番、知識ゲーの様相が強かった問題かも（とくに座標変換のあたり）。
本番中に導出できない程のむず変換ではないものの、知っているとスムーズに解けるのは間違いないわけで。
しかしまあ良問。
ちなみに、自分がこの変換を知らなかったとして本番中にきちんと導出できたかどうかは不明。
＜結果＞
完答。20点/20点。
問５ ダンジョン
「回復の泉が出てくる日本のローグライクゲームって何かあったっけ」という疑問から始まり、「普通のRPGのダンジョンにも地下N階という概念はあるのだからローグライクである必要ないね」という結論に至るまでに10分消費。
それはさておき。
プレイヤーの現在位置をnow階とする。
now階から先、回復の泉をガン無視して突き進んだときにたどりつける限界位置をpos階とする。
基本アルゴリズムは、
（１）「now階〜pos階のあいだにある泉のうち、回復量最大の泉がある階まで突き進む」
（２）「その階にある泉で、適切な回数だけ回復する」
（３）「nowとposを再計算。（１）に戻る」
となる。（２）の「適切な回数」とは、「回復量最大の泉」の位置が変化する可能性がある回数のこと。
nowもposも単調増加なので、メインループはO(N)。
ただ、「回復量最大の泉」を毎回計算しているとO(N^2)になってしまうので、うまいデータ構造を使って保持しておきたい。
もしも「最大HP」という概念がなかったら、泉の回復量は現在HPによらず一定なので、setを用意して、posが増えるたびに挿入、nowが増えるたびに削除していけばよい。これならO(NlogN)。
しかし実際は、HPには上限がある。
たとえば、最大HP100で現在HP80のとき、「元々の回復量」が50の泉を使っても「実際の回復量」は20である。
この「実際の回復量」というやつを、うまいこと計算したい。
あらかじめ、「地下1階から地下i階まで降りたときに受けるダメージの総和sum[i]」を各iに関して計算しておく（やることは問１と同じ）。
また、アルゴリズム実行中に、「今まで泉で回復したHPの総和recsum」を保持しておく。
すると、「実際の回復量」＝min{ 「元々の回復量」,sum[i] - recsum } と計算できる（now以前の泉では値が負になるが、気にしなくてよい）。
以上の議論を使うと、次のようにすれば（１）で「実際の回復量最大の泉」を計算することができる。
（★）
set中の泉のうち、「元々の回復量」が最大の泉と、2番目に大きい泉に注目。
これら2つの泉の「実際の回復量」を、それぞれh1,h2とする。
h1 < h2 なら、h1の泉はもう二度と使わないのでsetから削除。（★）に戻る。
h1 = h2 なら、h1とh2のうち、浅い階にある泉はもう二度と使わないのでsetから削除。（★）に戻る。
h1 > h2 なら、h1を求めるべき泉として、終了。
実はここで求めたh1は「実際の回復量最大の泉」ではないが、その場合は、次の（☆）で求める「適切な回復回数」が0回になるので問題ない。
こうして求めた泉のある階まで、nowを進める。nowが進んだことによりsetからいくつかの泉が削除される。
次に、（２）で回復する「適切な回数」を求める。
（☆）
・現在HPを最大値まで回復させるのに必要な最小回数
・到達限界posを1つ進めるのに必要な最小回数
・set中の泉のうち、元々の回復量が2番目に大きい泉の「元々の回復量」が、sum[now] - recsum 以上の値になるのに必要な最小回数
の3つのうち、最小のものが「適切な回数」である。このステップは割り算を使えばO(1)でできる。
適切な回数だけ回復させたら、（３）に進んで（１）に戻る。
「nowとposは単調増加」「setに同じ泉が二度挿入されることはない」ことより、全部まとめてO(NlogN)。
かかった時間：↑は、おおよそ自分の思考過程をなぞってはいるが、実際にはかなり迷走したので計2時間くらい。
どうせもっと簡単な解き方あるよねこれ。
（感想）
このシンプルな問題設定で、ここまでの良問＆難問を作り出せるのはさすが情オリとしか。
ダンジョン＝めんどい幅優先探索のICPCとはえらい違いですね。
それにしても去年の本選易化は何がやりたかったんだろうか。
＜結果＞
こんなに煩雑な問題で、俺のコードが正しく動くわけがない。
というわけで、1は通るも、2を落とし、3を落とし、4を落とし、5を落とし、なぜか6〜10が全部通って12点/20点。
ソースを俯瞰するとバグのある部分が視える力が欲しいです（眼鏡を外すと能力強化）。
ソースコード晒し
あとがき
問５をdequeで解く方法があるらしい。まぢか。
