AOJ埋め13 - ICPC突破専用ザク

去年の模擬アジア地区予選のセット．
当時やったときは3問しか解けなかったけど，今なら7問か，運が良ければ8問ってところじゃなかろうか．Neko's Treasureが難しい．
過去に解いたといえど1年も経ってるともうほとんど覚えてないですね．

2175 Whist

シミュレートするだけなのだけど，問題文を読むのが面倒．
問題文を正しく読めれば悩むところはほとんどないけど問題文がちょっと分かりにくいので時間がかかっちゃうかも．

2176 For the Peace

軍縮をする．
DPかなーと思ったけど状態数が多いので良くわかんなかった．
あんまりちゃんと証明はしてなかったのだけど，国の持っている武力の最小値を下回らない程度まで他の国を軍縮してやり，それができなくなったら，差がDを超えない程度で軍縮できる国があるか見て，あったらどれでもいいから軍縮をして最小値を更新し，なければNoを出力して終了する，ということをしてやったら通った．

Kは小さいので1文字ずつ吐いてやればいい．列を部分に分けていけばできる．
位置をnとする．長さkの数字は9*10^(k-1) 個あるので，長さkの列の長さはk*9*10^(k-1)である．これで位置nが何文字の長さのところにあるのかが分かる．
これが分かると，どの数字の位置にあるのか，また数字の何桁目なのかが分かるので，求めることができる．
等号とか1 origin / 0 origin とかに気をつけないとヘンな動作をしてしまうので気をつける．

2178 Futon

座標がでかいのでそのまま配列に確保することができない．
仕方ないのでmap<int,map<int,int> > に座標を格納してあとは2彩色．
計算量はマップへのアクセスとdfsのコストでO(NlogN)くらいかしら．

2179 Safe Area

Safeな場所を2つのセーフラインor外壁にぶつかるまで移動させることができるので，2つの太い直線に接する半径Rの円の中心(ふつう4箇所ある)が調べる候補になる．
太い直線に接する半径Rの円の中心は，直線を平行移動させれば直線同士の交差判定で出せるので，あとはその候補座標について可能かどうか調べればよい．

2180 Water Tank

2分探索っぽい問題．
最初あまり深く考えずにやったら最初のサンプルがどうしても合わなくておかしいなーと思ったのだけど，どうやら与えられた時間(0〜86400)まで水が残っていればいいというわけではなくて，これをずっと繰り返しても水が尽きてはいけない，ということだったらしい．
よくわからないけど，2日やって，2日目に水が満タンにならないのなら1日経るごとに水がどんどん減少していつかは水が尽きるだろうし，2日目のどこかで水が満タンになるならいくら繰り返しても大丈夫っぽいので，2日目まで調べるようにしてAC．

2181 Neko's Treasure

難しい問題だと思う．
問題文には「the minimum number of walls〜」を返せと記されているが，実際に返すべきは最大値であることに注意する．(assuming that Maki made an optimal choice of walls. であるから)
まず，円は交差・接触が無いように選ばれるため，s,tを両方含まない円，s,tを両方含む円の存在は無視できる．
次に，簡単のため，tを囲う円が無いと仮定すると，円の包含関係によってsを根とする無閉路な有効グラフを作れ，答えはこのグラフの最長パスの長さになる．
そして，tを囲う円が仮定すると，sとtを独立に考えてその和を答えにすれあばよい… としたいところだけど，最適解になる円同士が交差している可能性があるためそのようには考えられない．
その代わり，sで使う最外殻の円を固定するとtで使える円が限られるようになるので，N^2ループを回して最適解を得られる．
実装で結構悩んで割とバグりまくったし，ついには本番のジャッジデータを引っ張り出したりした．

2182 Eleven Lover

DPっぽいかと思ったけど特にDPとかしなくてもいい．
mod 11で
a[0]+a[1]*10+a[2]*10^2+a[3]*10^3+... ≡ a[0]-a[1]+a[2]-a[3]+...
なので，V[n]:=Σ_{k=0→n} (-1)^k*a[k] とおくと，部分a[i+1],a[i+2],...,a[j]が11-Sequence ⇔ a[i+1]≠0かつV[j]-V[i]≡0 とかが従う．なので，a[i+1]≠0，j<i，V[j]=V[i] となるようなものを順次カウントしていけばいい．O(N)でできる．