SRM565 Div.1
実に5ヶ月ぶり、今年最後のSRM。
8月はSWoPPといろいろ、9月は旅行いったりなんだり、後半から12月頭まではSCとその後処理
としばらく参加できていなかった…
結果
o--(+0/-0) 228.60pts 219th
1959->1965(+6)
維持できてよかった。
250 MonstersValley
典型的なDP、k番目まで来たときのpriceとdreadの合計が一緒ならそれらは区別しないでよいので
コストが同一ならdreadは大きければ大きいほどよい。
dp[i+1][j] := i番目まで来たときにコストjで可能な最大のdread
として
dp[i+1][j+price[i]] = max(dp[i][j] + dread[i], dp[i+1][j+price[j]]); //brideする場合 if(dread[i] <= dp[i][j]) dp[i+1][j] = max(dp[i][j], dp[i+1][j]); //素通り
として更新していけばよい。strictly greaterのミスが多かったようだった。
書くときにどっちだか覚えていなくて一旦問題文読み直していたので助かった。
問題文途中まで読んでDPDPと思ったのでsampleも全く見ずに書いたのではやかった。
500 TheDivisionGame
問題文読んでNimだなーと思う
→素因数の数=石の数だから素因数分解しよう
→10^9ぐらいの大きさで10^6ぐらいの範囲だと全部愚直にやると間に合わない
→区間篩して残ったのはO(sqrt(n))でいいや
→…区間どうやって数え上げるんだろう??
オワタ。数え上げ他の人のコード読んだけどよくわかりませんでした。
Twitterででもなんでも教えてください。
全区間からあてはまらない区間を引いていってる人が多そうだった。
素因数の個数は区間篩するときに一緒に引いてカウントしてるのを見た。賢い。
Grundy数は本当にわからない。
grundy数はよく解らないことがわかった。
— いささん (@Isa_rentacs) 5月 30, 2011
Grundy数わからん(定期ポスト)
— いささん (@Isa_rentacs) 1月 24, 2012
ゲーム系って応用が難しいと感じている…Nimは読んで理解しても新しいゲームに応用できない(Grundy数わからん)
— いささん (@Isa_rentacs) 10月 22, 2012
Grundy数わからん(2ヶ月ぶり4回目)
— いささん (@Isa_rentacs) 12月 20, 2012
そろそろ1回ちゃんと理解したいです。