Codeforces Round #490 (Div. 3) - D. Equalize the Remainders
概要
nとその約数のmが与えられる。n個のa_iから成る数列も与えられる。
1回の操作で数列の要素を1増やすことができる。
あなたは、mで割ったあまりが0, 1, 2, ..., m-1となるものの個数がすべてn/mになるようにしたい。最低の操作回数とその操作結果の一例を示せ。
制約： 1 <= n <= 2 * 10^5 1 <= m <= n 1 <= a_i <= 10^9
ACするまで
1. やるだけっぽい。やれたとは言ってない。
2. 余ってるものから足りないものへと移すのが根幹。この際、余ってるものリストのうち、どれから足りないものへ移しても、増分を考えたら同じなので、一番古いやつを移す。
3. 実装する。しかし実装法により沼
4. TLE
5. うまく実装する。AC!
6. 実をいうともっと強引でコーディング量が少ない実装してもよかった。
考察
この問題の基幹をなすアルゴリズム自体は難しくなく、体感と同じように「足りてるところから足りないところへと移す」である。
この際、ここまで見ての足りてるところのうちどれを移しても最終的な手数は同じであると示す。
K個の移すべき数字があるとする。それらを移しても残りはK-1個となり、移しコスト自体の増分はここでK-1が固定で増えるといえる。
K個のうち、例えば4つの場所A, B, C, Dがあり、(Aから入ってCから出る) + (Bから入ってDから出る) == (Aから入ってDから出る) + (Bから入ってCから出る)
と手数は同じであるとわかる。これと上のK-1個の考察を踏まえると、移すべき数字はどのような順番で取り出しても最終的な同じような手数になる。
この性質を使う例題としては、
F - Permutation Oddness(箱根DPとの見事な合わせ技)
A - 1D Matching(これを利用した数え上げ)
がある。
さて、実装上のポイントではあるが、mod mはm-2, m-1, 0, 1, ...とループするので、全体的に回すループはmではなく2m回にすればループを処理できる。
また、これは実装次第ではあるが、移すべき数字リストは、今回の場合結局1つ1つの数字を見るので、(移すべき数字, 個数)と管理するよりも、(移すべき数字)を個数個入れるとした方がコードが簡潔になる。
また、次のように、tmpが負で、-tmpの値を使って自分自身の更新や計算をする場合、一旦リネームしたほうが見通しがよくなりデバッグしやすい。
int tmp;//tmpは負 int cnt;//cntは正 int rtmp = -tmp; if(rtmp - cnt > 0){ ... }else if(rtmp - cnt == 0){ ... }else { rtmp = cnt - rtmp; } //最後にtmpに-rtmpの値を代入することでコードがわかりやすくなる tmp = -rtmp; //tmpをそのまま使うなら、条件式が-tmp - cnt > 0になり、非常にわかりづらい。
ACソースコード(queue)：
Submission #67188013 - Codeforces
ACソースコード(stack)：
Submission #67188677 - Codeforces
ACソースコード(どれがいくつあるのかをペアで保管 冗長)：
Submission #67188863 - Codeforces
一言
こういうところやぞお前
