TCO2010

TopCoderOpen2010の決勝戦(Championship)が日本時間で今日の朝にあったのですが，アルゴリズム部門，マラソンマッチ部門の2つで日本人が優勝したようです．とてもめでたい．
で，それはそれとしてTopCoderOpen2010のSemifinal1〜ChampionshipまでのEASY，MEDIUMを解いたのでとりあえず．

TCO2010 Semifinal1 EASY : DistantPoint

なんじゃこりゃと思ってしまうけど，実際に5*5とか9*9とかで手を動かしてやってみると単純にやってやればいいことが分かる．実装がちょっと面倒．

TCO2010 Semifinal1 MEDIUM : AliceInWanderland

TSPっぽくやる．実際，うさぎは動くものの，うさぎの移動スピードと主人公の移動スピードは同じなのでわざと遅れて捕まえても意味は無い(早く捕まえられるなら早く捕まえるのがよい)のでTSPでできる．TSPの部分よりも，ある点からうさぎを捕まえるのにかかる最短時間を求める方が難儀した．下手にやるとTLEになるし…．
具体的には，つかまる時間を求める際にうさぎの移動コマンド数分だけ2分探索をするようにしたのだけど，それだとどうもTLEになるようだったので，1度2分探索をしたらその次の結果もあまり変わらないであろうことを利用して，前の結果±2を上限，下限にして2分探索をするようにした． (説明下手ですいません)

TCO2010 Semifinal2 EASY : YetAnotherRobotSimulation

まず，矢印の入れ方は隣り合う2つを入れ替えても結果は変わらない．よって，結果は命令に入れる↑矢印の個数，←矢印の個数，↓矢印の個数，→矢印の個数のみに依存する．命令の長さはたいしたことないので，これらを全部ループで試せばいい．
各向きの矢印の個数を決めてやったら，あとはその命令によってx座標=v, y座標=uになる確率を組み合わせ係数とか使って適当に出せるので，その2つを掛ければよい．(x成分とy成分で独立に考える)

TCO2010 Semifinal2 MEDIUM : SellingGold

変なミスしてWA出しまくった問題．
値段の合計をP，ゴールドの合計をGとする．要素を2つに分けたとき，片方の値段の合計がp，ゴールドの合計がgだったとすると，最小化したい値は p/g+(P-p)/(G-g) となる．gの値を固定して考えた場合，これはpが最小(or 最大)のときにもっとも小さくなることがわかる．
そこで，dp[g][num]を dp[g][num] := 要素からnum個とってゴールドの合計をgにするときの値段の最小値 としてDPで出す．
実際にはこれだけではどうもうまく式を立てられなかったので，これにさらに j:要素のインデックス を付けて，
dp[g][num][j] := インデックスjまでの要素からnum個とってゴールドの合計をgにするときの値段の最小値
として計算した．ただ，これをそのまま愚直に確保するとMLEになるので，使っていない要素を縮小してメモリの使用を減らすなどした．

TCO2010 Wildcard EASY : SequencePermutation

実際に観戦していたのですが，全然分からんなーと思っていたらラスベガスの皆様があっという間に解いていって驚いた問題．
手の付けようが無いように見えるのだけど，列の転倒数に着目して考えると適当なDPで解ける．
反転を1回するごとに列の転倒数はちょうど1だけ増減するし，また逆に，転倒数がMであるような任意の列は反転操作をM回やれば得られる(これはなんか多分置換使って証明できた気がする) ので，答えは (転倒数Mの列の個数)+(転倒数M-2の列の個数)+(転倒数M-4の列の個数)+... になる．
これは dp[N][M] := 長さNの転倒数Mの列の個数 としてdpをすると求めることが出来る．

TCO2010 Wildcard MEDIUM : CalculationCards

とても素敵な問題．
まず，最左の0とプラスマイナスのカードを適当にソートして並べて，次に掛け算のカードをそれらの間に任意に並べる，ということを考える．
次に，項単位でプラスマイナスのカードと掛け算のカードを任意に動かす，という操作をすると，これによって任意の列が実現できるのが容易にわかる．
また，この最後の項単位で動かすという動作によって計算結果は変わらないので，プラスマイナスのカードは最初から固定していると考えていい．
すると，答えは (プラスマイナスのカードの和)×(1つの項のところに集まりうる積の平均値) となる．

1つの項に集まりうる積の平均について考える．
n個の掛け算のカードからなる積全体の総和をE[n]とおくと，E[n]は (1+x*c[0])*(1+x*c[1])*...*(1+x*c[N-1]) におけるx^nの係数に等しくなる．(ここでc[j]は掛け算カードjに書かれている数字)
あとは，それを使って組み合わせ係数や階乗を使って数え上げると求められる．(適当な説明ですがここが一番ややこしいです)

TCO2010 Championship EASY : EvaluatingElections

難しい問題．一見Greedyのように見えるけど値の範囲が小さいのでDPで解ける．(Greedyでも解けるっぽいですがよく知りません
自分ともう1つの政党しか無いときが最悪なのでそれを仮定し，敵の政党が勝ったら-1，引き分けなら±0，自分が勝ちなら+1として， dp[num][j] := 地区jまでを見たとき，人数numが自分に投票したときに得られる最小のスコア とおく．
これで dp[num][N] がはじめて正になるような最小のnumを答えにすればよい．

TCO2010 Championship MEDIUM : EnclosingSquare

数論．個人的に250よりもこっちの方が簡単に感じたのですが多少の個人差がありそう．
pickの定理を使えばきれいな条件式が成り立つので，あとは約数なりGCDなり平方数なり使って解けます．

…しかしこうやってみてみるとTopCoderって本当に数論と組み合わせ的なDPばっかりですねぇ．