SRM455

300

ドーナッツを探す
O(n^4)のDP
手抜きしてO(n^5)でやったけど間に合った
254.56

900

550>900の法則より900からやることに
ただのDPかと思って組んだらサンプルが通らない…
問題文読み直したら勘違い発覚orz
ルートvの部分木はv以下のノード全部取り出したやつだと思ってたorz
それじゃあ同じペアで使っちゃだめというのが効いてくるから計算量がやばくなるなぁ…
というわけで諦めて550やることに

550

六角形の個数を求める問題
六角形は三角形から３つ三角形取り除いた形で、三角形の大きさ決めると、そのサイズの六角形の個数は計算で求まる
あとは単純に全部足すだけ…なのになぜか重複できてるなーとかありえないこと考えて、単純に足せなかったorzorz

Challenge

300でTLEっぽい探索のを２つ撃墜成功
DPがあやしいのがあったので自分のをその形に書き直してバグるの探して撃墜成功
そのあと調子に乗って撃墜ミス*2orz
+100.00

合計354.56の20位
2917 → 2911

ところで、550は三角形の大きさ決めた時の個数がΣ_{a,b,c}[1<=a,b,c&&a+b,b+c,c+a<=n-1]でこれ計算するのめんどくさくて数列検索投げたわけだけど、これくらいシグマ計算プログラム作っとけば簡単に計算できる気がするなぁ。
そしたら何も考えずにΣ_{x1,y1,...,x6,y6}[x1,y1,...,x6,y6が六角形]
って書くだけでしゅーりょーするんじゃないだろうか…