ACM-ICPC OB/OG会の夏合宿に行っていました．

ICPC国内予選で比較的上位に入っていたためACM-ICPC OB/OG会の夏合宿へ呼ばれていました．
合宿は東京のとある宿泊施設で行われ，3泊4日でひたすら問題を解き続けていました．
他大学のICPC参加チームの方々や，OB/OG会の方々など，普段会う機会が無い方達と交流ができてとても有意義でした．
以下，解いた問題について技術的な考察など．

考察

夏合宿で解いた問題について学んだことなどを書きとめておこうかと．
問題自体は9月23日時点ではまだないですが時期にACM-ICPC OB/OG会のページにアップロードされるでしょう．
一応ネタバレっぽいのでページを畳んでおきます．

2日目 A Infected Computer

時間t[i]でソートしてシミュレートするだけ．簡単

2日目 B Magic Slayer

ナップサック問題でDP．
Single,Allの魔法それぞれについてHPがxのモンスターを倒すのに必要な最低のMP値 SingleMP[x], AllMP[x]をそれぞれDPで求め，
あとは0<=X<=max(HP)に対して 敵を全体魔法でX削る(AllMP[X]だけ消費)→単体魔法で全モンスター倒す(ΣSingleMP[HP-X]だけ消費)
のループをかければ最低値が求まる．

2日目 C Dial Lock

最右端のマスは高々1回だけ回せば揃ってくれるので，最右端を回す際にどこまで回すかで場合分けをすればk!回の探索で調べられる．
計算量はk!*k<=10!*10となる．

2日目 D Double Sorting

NP完全問題だといううわさを聞いたのだが本当なのだろうか… 見かけに反して非常に難しい問題．
A*探索をすれば良いと聞いたがまったく分からなかった．

2日目 E Symmetry

幾何．なんとかして頑張る．
合宿にはライブラリ等は一切持って行っていなかったのですが，幾何の問題は事前に多くの下積みを必要とするため，幾何系はライブラリを前もって所持しておかなければ勝負に挑むことすら出来ないということが分かった．

2日目 F Voronoi Island

ボロノイ図の領域面積を求める問題．
実は凸包カットのライブラリがあればすぐにできた…らしい．
が，そんなものを持っていなかった私達は手も足も出なかった．

2日目 G Defend the Bases

2分探索＋2部グラフの最大流問題に帰結される．

2日目 H Galaxy Wide Web Service

1,2,...,24のLCMは非常に大きいので，13,17,19,23の場合だけ特別視する．
すると，上の4つの数を除いた24までの数のLCMは小さいので時間内に探索できる．

2日目 I Tatami

探索空間が広すぎて普通に探索したのでは間に合わない…かと思いきや，普通に時間内に終わる．
4隅に置いてはいけないという条件が非常に強いためほとんどパターンが生成されないのだ．
実際，例えば盤面の真ん中に畳を1つおいたとすると

のように，赤い隅で示した部分に畳の隅が合うように置かざるを得なくなる．
この強い制約により，実際には1次元のDPにも帰結することができるらしい．
探索空間の広さがすぐには断定できない場合，実験により探索空間の広さを調べることが重要だと思った問題．

2日目 J Revenge of the Round Table

円順列という扱いにくい問題．
問題を次のように分解していき，最終的に解けるようにする．

  1. N個からなる順列(円ではない，繋ぎは考えない)で，Aから始まって，同じ国の人がk人より多く並ばない組の数DP1A[N]
  2. N個からなる順列で，Aから始まって，"繋ぎの部分も"同じ国の人がk人より多く並ばない組の数DP2A[N]
  3. N個からなる順列で，Aから始まって，繰り返し単位がNであるもの*1で，繋ぎの部分も同じ国の人がk人より多く並ばない組の数DP3A[N]
  4. N個からなる円順列で，同じ国の人がk人より多く並ばない組の数DP4[N]

DPにより解く問題であったが，DPというよりは円順列の数え上げテクニックに関する問題であると思った．

3日目 A Strange String Manipulation

実行するだけ…と思いきや落とし穴が．
double型による計算では，たとえ数式上では同じ結果になるはずのものでも，計算誤差によって微妙に値がずれることがある．
そのため，たとえば今までの最大値をcurrent_max,現在の計算値をdとして

double d=0.0
for (int j=0;j<N;++j) {
    d+=...;
}
if (current_max < d) {
    //...
}

といった感じで，計算結果を以前のものと比較しようとすると，計算誤差によって値がずれうる．
そこで，if文で比較する際に

if (current_max < d+1e-8) {
    //...
}

のように，少し値をずらせば，うまくいく，らしい…死ねばいいのに．


あと，解説者は解答の埋め込みを推していたのですが，埋め込むほどの問題でもないような…

3日目 B Erratic Sleep Habits

n日目で，睡眠時間t周期目にあるような場合にとる必要のある無水カフェインの最低値でDP[n][t]．

3日目 C Find the Point

幾何．場合分け．

3日目 D Luigi's Tavern

条件付で集合を分割する際の最大数を求める問題…かと思い気やモデル化して最大流問題に帰結できる．
集合を分割する類の問題は最大流問題に帰結することができるのかも．

3日目 E Colored Octahedra
  1. 8!通り全列挙×回転系(X,Y,Z軸0ﾟ，90ﾟ，180ﾟ，270ﾟ回転により高々64通り)のうち辞書順で先頭にあるものを調べる
  2. ポリアの数え上げ公式を使う．知りませんそんなもの…
3日目 F Marked Ancestor

Union-Findというデータ構造を使う．
Union-Findとは，分割された集合を扱うもので，

  • union_set : 元x,yの入っている集合同士を合併する
  • find_set : 元x,yが同じ集合に属しているか判定する

といった操作がほぼ定数時間でできる．


この問題の場合，まずオペレーションがすべて実行されたとして，森を構築する．
そして森の各木の根がUnion-Findの代表点となるように，Union-Findを構築する．
あとはオペレーションを逆順にたどり，マークが来たらunion_setをし，クエリが来たら代表点（TreeのRootID）を集計するようにすればよい．

3日目 G Strange Couple

期待値の計算．
頂点jから頂点t(=目的地)に行くまでの期待値をE[j]とすると，E[1],...,E[n]からなる連立方程式ができるので，それをガウスの消去法によって解けば良い．
ガウスの消去法はO(n^3)だが問題ではn<=100なので時間内に解ける．


…ところでこの期待値の式，どう出してもサンプルのものが合わないのだけどどうなってるんだろうか…

3日目 H Queen's Case

あんまり覚えていない．
状態数が30^4=81万程度しかないので，勝利条件が確定した状態からミニマックス法で逆順に辿って，勝利なら勝利，敗北なら敗北，どちらでもないなら決着がつかないと判定…とかだったような…．（あんまり覚えていません）

3日目 I Wind Passages

幾何．最大流問題に帰結出来るらしい．(?) ダイクストラらしいです．

3日目 J Secret Operation

幾何＋鬼畜．

4日目 A Anime Master

A問題とは思えないくらい難しい．結局どうやれば良かったのだろう?(4日目は解説受けてないので解答が未知の問題が多いです．)

4日目 B Cans of Toys

期待値の計算問題．
漸化式を立てられればあとは計算するだけだが，漸化式を立てるところが難しい．
もしかしたら高校レベルの確率論(確率変数含む)についても復習しておいたほうがよい?

4日目 C Containers
4日目 D Graph Destruction

3日目のF Marked Ancestorと同じようにUnion-Findを使えばほぼ同様にして解ける．

4日目 E Magic Doors
4日目 F Maximum Segment XOR
4日目 G Moving Points
4日目 H Shuffling Machine

整数k，長さnの置換βに対し，α^k=βとなるような置換αは存在するか?という問題．
k=2の場合はSPOJであった(LEONARD)ので出来そうかと思ったものの意外と泥臭い．どうやるのだろう．

4日目 I Topology
  1. まず盤面を横に区切っていく．すると各横長の領域に対し，内部になりうる領域の短点の座標のリストが得られるので，一番上の横長領域から下にトップダウンに見て行くことで領域の個数が求められる．
  2. オイラーの多面体公式で領域の数を求められる…らしい．驚き．
4日目 J Very Intellectual Card Game

実験するとカードは元の並びの回転にしかならないことがわかるのであらかじめ長さn/2の和のリストを持っておいてあとはシミュレートする．

*1:ここで繰り返し単位とは，たとえばN=6として，ABBABBなどは(ABB)^2となるから繰り返し単位は3であり，ABABABなどは(AB)^3となるので繰り返し単位は2である，といった感じのものとする