hotpepsiの練習帳

TCO15 Algorithm Round 2A

01:11

https://competitiveprogramming.info/topcoder/srm/round/16475/div/1

Easy (300) ModModMod

問題

• 配列mの各要素でmodを取る関数f(x)がある
• f(1)からf(R)までの合計を求める

方針

• 普通に再帰で書く
• 死
• (終了後)
• [1,R]の個数を配列cntで覚えておき、それぞれを1で初期化する
• MODの最大値Uを覚えておき、R+1で初期化
• mの各要素Mについて、順番にMODを取っていく
• MがU未満のとき、[M,U)の数値xについて、cnt[x % M]にcnt[x]を加える
• その結果、cnt[1]～cnt[M-1]までの部分に、総数が入る
• MがU以上のときは無視していい
• 最後に[1,U)のiについてi×cnt[i]の総和を求める
• https://github.com/firewood/topcoder/blob/master/tco_2015/ModModMod.cpp

結果

x-- 0pt 430th/902 rating 1303 -> 1287 (-16)

順番に計算するだけだけど全く思いつかなかった。

チャレンジのみ無効でrated

http://togetter.com/li/828905