天下一プログラマーコンテスト2014 本戦

2014-09-07 | [Competitive programming]

3 位 。・°°・(＞_＜)・°°・。

A

読んで自明だったので書いたら RE がでてふえっ！？ってなって配列の範囲外参照に気づいて (◞‸◟)(>_<)(◞‸◟) した後書きなおして通す

B

10*10 に気づいたらビット並列するだけだとわりとすぐ気づいたので書いて通す

C

wild card がない場合は典型というのはすぐ気づいた．

wild card があっても，DP 中ではじめて使う段階で wild card を実際の値にしていいことがわかったので，事前計算を適当にやって DP をして通す

D

みたら C(N, 0) + … + C(N, K) を求めろと書いてある．

パスカルの三角形を適当に眺めていたら，K を固定して N を 1 増加させる操作は 1 回につき定数でできることがわかったので， 平方分割して通す

E

満点はどう考えても頭のおかしいデータ構造とかが必要そうに見えて (実は違うらしい) 無理そうだったので部分点を取りに行く

最初ローリングハッシュを使って 100 点を取った後，N <= 20,000 は実は 2 乗いけるのでは？？？となってメモリやばくない + 危険性がまったくない (suffix array) 方法で書きなおして 200 点を取るがすでに手遅れ

満点はまったく取れる気がしなかったのであとは適当に考えたり順位表眺めたりしてた． 解説聞いたけどまったく理解できなかった

結果

ペナルティ差で 3 位 (◞‸◟)

2 位とのペナルティ差が 4 分強で，WA 1 回に満たないし E で static RMQ のライブラリを整備していたりしたら簡単に逆転したレベルだと思うので，とてもつらい． N <= 20,000 が O(N^2) で解けることが最初から見えていたら最初からそれで解いてたと思う．

（ペナルティゲーはやめてほしいなあ…）