いもす法 累積和 AtCoder Regular Contest 048 B - AtCoderでじゃんけんを
Problem
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;