SRM参加記録など雑記です。社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。rating:2079(-5)500が最近全然解けない。Statementコーディングフェーズどう見てもイテレーションするだけ。愚直にやれば、dp[i-1][val+j]+=dp[i][val]*ways[i-1][val+j]でi-1番目の人がval+j点取るようなDPが計算できるまあでもjの範囲が広くDP更新の計算量が200000とかあって全然無理・・ways[i][val]の計算方法も全然分からん。考えたが結局無為に1時間のコーディングフェーズを過ごしてしまったこんな難しい問題で100人も解けるなんてどうなってるんだ。みんな頭いい後で色々調べたらすごく典型的なDPで解ける問題だった。100人しか解けなかったのが不思議なくらい。なんでこんな解法に気づかなかったのか。色んな解法があるみたいだけど、簡単なのは以下のようなsumを計算する方式と思う。(こういうのはいっぱい解いてるはずなのだが・・)dp[i-1][val+j]+=dp[i][val]*ways[i-1][val+j]という更新式を考えていたが、dp[i][val]+=dp[i+1][val-j]*ways[i][val]という式に変えてみる。jをイテレートするので、更に変形するとdp[i][val]=(dp[i+1][val-1]+dp[i+1][val-2]+...+dp[i+1][0])*ways[i][val]というわけで、dpsum[i+1][val-1]みたいな変数で、dp[i+1][0]+...+dp[i+1][val-1]の和を計算しておけばO(1)で更新できるこれが分かれば、waysの計算も全く同じような方法で計算できることがわかる。OpenTipsDiv1SRM455SRM456SRM457SRM466SRM467SRM468SRM469SRM470SRM471SRM473SRM474SRM475SRM476SRM477SRM478SRM479SRM480SRM481SRM482SRM483SRM484SRM485SRM486SRM487SRM488SRM489SRM490SRM491SRM492SRM493SRM494SRM495SRM496SRM497SRM498SRM499SRM500SRM502SRM503SRM505SRM504.5SRM506SRM507SRM508SRM510SRM511SRM512SRM513SRM514SRM515SRM516SRM517SRM518SRM519SRM520SRM521SRM522SRM523SRM524SRM525SRM526SRM527SRM526.5SRM528SRM529SRM530SRM531SRM532SRM533SRM534SRM535SRM536SRM537SRM538SRM540SRM541SRM543カウンター356927リンク集SigmarのProfile。