Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

いもす法 累積和 AtCoder Regular Contest 048 B - AtCoderでじゃんけんを

Problem

arc048.contest.atcoder.jp

note

あらかじめあるレーティングの人が何人いるのかの累積和と、あるレーティングである手をとるプレイヤーが何人いるかを記録しておく。 そうすると、それぞれの勝敗が次のようにO(1)でもとまる。

     int win = dp[players[i].r][(players[i].h + 1) % 3 ];
        int draw = dp[players[i].r][players[i].h] - 1;
        int lose = dp[players[i].r][(players[i].h + 2) % 3 ];
        cout << imos[players[i].r - 1] + win << " " << imos[MAX_N-1] - imos[players[i].r] + lose << " " << draw << endl;