冬コンテスト

開始

簡単な問題がない！！！
JがただのDPな気がしたので提出したらWAったorz
間違いに気づいて直したら二乗のDPじゃなくて三乗になってしまった…のでパス
きたまさがAの最小二乗法やってようやく1AC

1時間経過

Cの漸化式をがんばって立てて2AC目
早くも解ける問題がなくなる…
みんなJいっぱい解いてたから実は1000^3/6くらい間に合うんじゃね、とか思って出したけどTLEorz

2時間経過

GCJで昔やった問題を思い出してBを通す
空間凸包をO(N^4)でてきとーに書いて通す
空間凸包は、同一平面上の点を列挙した上で平面凸包したけど、摂動させればよかったのか…
Jがいっぱい通ってるのでもう貪欲に違いない！と決めつけてかかるも通らないorz

3時間経過

Hをきたまさががんばって通す
いっぱい通っているJとSJTUが通したIをみんなで考えるも全然通る気配がないorz

4時間経過

しかたないので嘘DPでJを通すｗ
Gやり始めたら超簡単で20分くらいで通った…
Iにランダム投げてしゅーりょー

終了

7問解けてなんとか_(ryには勝てたけど、SJTU強すぎ…
自分がずっとJ考えてたのが明らかにまずかった
Standingとか参考にせずにとっとと幾何＆探索やるべき

SRM 459

250

0.5刻みで全部試した
241.08

500

一番下の数字の寄与は二項係数となるので、個数制約なしのナップサックみたいな感じのDPするだけ
430.89

1000

O(NM)くらいで解の存在判定ができる？→わかんね
パターン見つけゲー？→わかんね

Challenge

なにも落とせるのがない…
結局提出された解答全て撃墜もシステムテストも通った…

合計671.97の11位
2840 → 2886
久しぶりにまともに上がった気がする

SRM 458

250

弾性衝突=すり抜け
242.65

450

まず、コインの金額が決まっていたら貪欲に使うだけなので、a円以上のコインでb円を払おうとすると残りb%a円をそれ未満のコインで払うことになる
よって、
dp[i]:=一番小さいコインがi円の時に全部i円未満になるまで貪欲に払うのに必要な最小枚数
とすると、
dp[i]=min{dp[j]+Σprice%j/i | j=2i,3i,...}
となる
415.13

900

ちょっと考えると、a,b,c,dが満たすべき制約が見えてきて、bとdの関係がよく分からなかったけどb>=dなら全部いけるんじゃねとか思ってしまったorz
提出してからN=100000くらいまでa,b,c,dの組を列挙してみたところ、b>=dでもだめなパターンが存在するぽいことが判明…
しかしパターンが分からなかったorz
b-d<=(b,d)らしい
Challenge Succeeded

Challenge

450でDPしてなさそうなやつを落とそうと思ったが落とせなかったorz
-25.00

合計632.78の34位
2842 → 2840
rngさんのセットで上がった記憶がない…

SRM 457

Petr+ACRush部屋にあたっていきなり絶望した

250

めんどくさいので24*60*19通り全部生成して試した
235.46

500

あれーmodとらなかったらオーバーフローするんじゃね…
とか思ったら、全然そんなことはなかったｗ
どれがmod nで等しくなるかを全パターン試して、1〜nの振り分け方に+nするしないの自由度分を掛けた
315.58

1000

久しぶりのフローキター
と思ったが、超絶TLEしてorz
最小コスト求めるのはただの最小費用流で、そっから辞書順最小化するためには、経路修正すれば良い
辺e=(v,u)に流れている流量を減らすためには、残余グラフ上でv->uのパスを見つけてそっちに流せば良くて、このパスの費用が0ならもとのコストのままで切り替えれる
逆に、辺e=(v,u)に流したいときはu->vのパスを見つければ良い
残余グラフには負の辺がよゆーで含まれるけど、最小費用流計算時のポテンシャルを使えば負の辺なんてないので、コスト0の辺のみからなるパスを探せばおk
と思ったんだけど、なぜか通らない…
Petrのを見たらベルマンフォードしてたのでおとなしくベルマンフォードしたら余裕でTLEorz
よく見たらグラフのサイズがそもそも違ったｗ
で、サイズ修正したらコスト0辺でも通った…
バグってたのかたまたまなのかわからね

Challenge

こんなカオス部屋で撃墜なんてできる訳ないね
二人の撃墜に耐えたやつは全部システムテスト通りましたとさｗ

合計551.04の31位
2848 → 2842
どんどん下がるよ！

Σ電卓(2)

いろいろ改良したらかなりまともになったのでとりあえず完成

六角形の個数を求めるやつだと、

$x1$y1$x2$y2$x3$y3$x4$y4$x5$y5$x6$y6[0<=x1,y1,x2,y2,x3,y3,x4,y4,x5,y5,x6,y6<=N][x1+y1,x2+y2,x3+y3,x4+y4,x5+y5,x6+y6<=N][x1x4-y4][x3+y3=x4+y4][x4>x5][y4=y5][y5>y6][x5=x6][x6-y6=1

こんな入力を与えると、

long res = N * (12 + N * (4 + N * (-15 + N * (-5 + N * (3 + N))))) / 720;
if ((1 + N) % 2 == 0) res += (45 + N * (-48 + N * (-52 + N * (60 + N * (5 + N * (-12 + 2 * N)))))) / 2880;
if (N % 2 == 0) res += N * (-48 + N * (-52 + N * (60 + N * (5 + N * (-12 + 2 * N))))) / 2880;
return res;

こんな出力を吐いてくれるようになった。
オプションでmodとったり、BigIntegerにしたりも可能。
SRM454の方は、20行くらいあって長過ぎorz
もっと頑張れそうな気もするけどめんどいからいいやｗ
そのうちどっかで公開するかも。
ひっそりと公開しました http://ow.ly/SuLM
パスワードはてきと

今年のまとめ

1月

TopCoderの暗号マラソンにハマった
この問題が自分の中で一番のお気に入り

2月

OBOG会の冬合宿でロシア＆中国チームのヤバさに絶望した

3月

TCO＆ICPCChallenge＆引越しで忙しすぎて死んだ

4月

ICPC WF@ストックホルム
全然ダメぽだったorz

5月

多分課題に追われてた

6月

TCO@ラスベガス
惨敗orz
UTPC3位orz
まぐれでターゲットに！！

7月

ICPC国内予選勝利！

8月

天下一プログラマーとかいう大会で優勝した
なぜかオープンキャンパスで講演したりした
恐怖のロシア合宿で絶望した

9月

OBOG会夏合宿で初めて勝利した
記念すべき第一回KMCMonthly開催(Monthlyなのに第二回は未定ｗ)

10月

まぐれターゲットから陥落orz
ICPC@台湾
奇跡の逆転優勝！

11月

ICPC@東京
JavaChallengeと本戦の２冠達成！
GCJ@マウンテンビュー
まぐれで3位ゲット！

12月

某原稿に追われる日々

いろいろと充実した一年だったなぁ

SRM456

250

2(0,+1)=(+1,+1)+(-1,+1)
だから、上に進む回数は一回以下として良くて、(dx+dy)%2で場合分けするだけ
245.12

450

ソートを昇順と勘違い→カットいっぱいした方が得じゃん→ちょうどC回カットでいいね→サンプル通らね→よく読んだら降順じゃん→脳内ちょうどC回のまま
もうだめぽ
190.88

1050

さっぱりわからない

Challenge

450で二分探索がwhile (ub - lb > EPS)な人がいっぱい…
しかしどうやったら落とせるのかさっぱり…
しかたないので書き写してローカル実行して無限ループするのを探すことに
見つかった→撃墜失敗…
JavaとC++で挙動が違うとかO2のせいかーーー
+25.00

合計461.00の80位orz
2911 → 2848