PKU 2007 Warmup 1 for Regional Contests

Pku

アクセスしたらちょうど始まったところだったので参加．
結果は7問全てacceptで5位．ただ一発で通ったのが4つなのでTopCoderだと3問は落してる．ただD以外はもう少しtest caseが入ってくるので間違いには気づいたと思う．
解いた順番はC->E->F->A->B->G->D

Problem C

シミュレーション．

Problem E

x = argmin(sum_i (a[i] + x) % L)を求めよという問題，xを1からLまで試せばいいが，合計のみを出せばいいというところに気をつけるとLに対して線形でもとまる．添え字を1個ミスってはまってた．

Problem F

やるだけ，だけど面倒．%dのところでおそらくintの範囲を超えた数字もきてるのでInteger.parseIntとかやると通らなかった．

Problem A

S回繰り返したときのiでの状態a_i^Sは

a_i^S = a_(i-2^k)^(S - 2^k) xor a_(i+2^k)^(S - 2^k)

となるので再帰的に求まる．

Problem B

境界条件とかがよくわからなかったけどパネル上の300*300点の格子点のどれかからスタートしたと思って，全部シミュレーションしたら通った．Javaだから時間面で優遇されているので100*100まで減らす必要があるかもしれない．

Problem G

線分の交点を直接求めてやればいい．精度が要求されるみたいなことが書いてあったので有理数クラスとか作って計算した．

Problem D

N*N*4状態を幅優先探索．状態遷移に関しては強引に書き下した．