Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

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数は本当にわからない。





そろそろ1回ちゃんと理解したいです。