IPSC 2010

今年は個人で参加した。
8問半解いて、全体で15位、個人の部では1位だった。

A

数列が与えられるので、ソートされてないように並び替える問題
やるだけ

B

平面上に一本直線があり、この直線上と上下左右への移動のみによる二点間の最短距離を求める問題
二点から水平・垂直な直線引いて交点求めてそれらからなるグラフの最短距離求めるだけ

C

「変数=数式」っていう形の入力を受け取って、各変数の値を求める問題
ただしループはしない
頑張ってパースするだけ

D

N個の頭を持つドラゴンを倒したい
二種類の剣があって、剣iはドラゴンの頭をci減らすがその後gi本の新しい頭が生えてくる
ドラゴンの頭を全て切ることができればあなたの勝ち
ドラゴンの頭がci未満だとその剣は使えない
しかし、自分も頭があるので、ドラゴンの頭がci-1個の時は自分の頭も一緒に切ることで引き分けにできる
勝敗判定せよって言う問題
拡張ユークリッドして場合分けしまくったら通ったが怪しい

E

ちゃんと読んでないが、たぶんインタラクティブ問題
時間かかるので放置

F

N個のサイズが異なる立方体があるので、それらを積み上げて二つの等しい高さの山を作るとき、最大の高さを求める問題(全部使い切らなくても良い)
に対する嘘解法が4つ与えられるのでそれらを全て同時に撃墜できる入力を作る問題
ランダムに入力生成すればそのうち落ちるかと思ったが全然落ちなかったのでちゃんと考えて作ったら落とせた

G

読んでない

H

指定されたMD5値になるようにファイルを生成する問題
無理ゲー

I

多角形(凸とは限らない)が与えられて、その内部の点から各辺の延長線上におろした垂線の長さの和の期待値を求める問題
頑張って積分するだけ

J

N個の机があり、各机に青と赤で数字を書く
最初、N人の男女が各机に一人ずつ居て、一定時間ごとに男は青の数字の机に移動し、女は赤の数字の机に移動する
N回の移動で、各男女が全ての机に移動し、各男が全ての女と同じ机になることがあるような番号付けを求めよっていう問題
サンプルからてきとーに類推して出したら通った

K

二人プレーのゲーム
3次元中に点がN個あって、各点は原点からのユークリッド距離が真に小さくなる格子点上へ移動させれる
各ターンに最大K個の点を動かすことが出来、全部原点に移動させたプレーヤーの勝ち
勝敗を判定せよっていう問題
同時に1〜K個のゲームを進められるNimは山のサイズを二進表記の各桁毎に和を取って全部mod(K+1)で0なら負け、そうでなければ勝ち
座標が超でかくて山のサイズがナイーブに求まらないのでちょっと大変
位置(x,y,z)に対応する山のサイズは|(x,y,z)|^2=Mとすると、|(x',y',z')|^2=K<Mとなる点(x',y',z')が存在するようなKの個数に等しい
つまり3つの平方数の和で表せるような数の個数を求めればよい
google先生に聞いたところ、表せない数は4^n(8k+7)であることが分かったため、サイズがO(log M)で求まって解けた

L

1円の切手がN種類と、2円の切手がM種類あるから、これらからK円分買うような方法の総数を求める問題
smallはKが小さいので2円の切手を何円分買うかが全通り試せる
largeはKが超でかいが、行列累乗で解けると思う
最後10分くらいで気づいたが組み終わらなかった

M

ペナルティーを減らすサービス問題
コンテスト開始〜2時間と2時間30分〜4時間30分に2回ゲームが開かれる
好きなタイミングで提出して、全参加者の提出時間の平均の2/3に近いほどペナルティーが下がる
点は入らないので、終了直前に暇になったらやればいいやと思って、4時間30分過ぎた時点でようやく問題読んだらすでに終わっていた