ABC277-D(Green-)

ABC277-D

概要

カードが$ N $枚で$ A _ i $である。最初はすべて手札。次のようなことをして、手札に残るカードの和を答えよ。

1. 手札からカード1枚を選ぶ。
2. 次の行為を好きなだけ繰り返す。
   1. 場にあるカードの値が$ X $なら、元のカードを捨てて、$ X $か$ (X + 1) \mod M $の値のカードを場に出す。

$ N \leq 2 \times 10 ^ 5, M \leq 10 ^ 9, 0 \leq A _ i \leq M $

考察

どういう場合がいいのか

明らかに、$ X $のカードが複数枚あるなら、実質全部出すことができる。

となれば、同じ種類のカードをまとめて、番号が連番(modのところで跳ぶ)のものを全部集計して、その連番部分で最大のものを取ればよい。あらかじめ全部の和は全部足し合わせておく。

実装上での技法

今回みたいにmodでつながっていれば系は、同じ配列をお知りにくっつけていくと楽。

1234->12341234
        ____ <-このように連続をうまく実装できる

あとは、普通に連続が続く、続かないならその時点で切って答えを更新。

だがここで忘れやすい2点が。

最後の更新

int v = 0;
for(){
    if(継続){
        v += ???;
    }
    else {
        //ここで終わり
        vで答えを更新;
        新たな連続部分を始めるにあたっての初期準備;
    }
    vで答えを更新;//忘れるな！！！
}

今回は同じものを2週させているので、これは発生しないが、2週させないものならば、最後にvで答えを更新を忘れるな！

連続区間の長さに制限を

悔しいながら今回何回も引っかかってしまった。

同じ配列$ X, Y, ... $をくっつけて長さ2倍の$ X, Y, ..., X, Y, ... $でmodでの番号ループを対応するなら、区間の長さをたかだか$ \mathrm{length}(X, Y, ...) $に制限する実装を書くべき。

今回の場合、例えば

5 5
0 1 2 3 4

の場合、全部一気にとれるので、そのまま2週目も取り始めて結果的に0 1 2 3 4 0 1 2 3 4と取ってしまう。

これの対策として以下の2つがある。

streakの長さに制限をつける。

ACコード

これが一番やりやすいしミスらない。絶対に越えてはならない連続区間の長さを設けて、それを超えたら強制的に終了させる。

int streak_length = 0;
for(;;){
    if(streak_length > 所定の長さ){
        goto end_streak;
    }
    
    ...
    end_streak:;
    //連続区間終了操作
}

やらかしてしまった時に出る異常値を最後で弾く

ikefumyさんのACコード

やらかしてしまった時に出る異常値は、今回では何週もしてしまうということで、全ての和が$ S $なら、2倍引かれて$ -S $となる。このように問題となる条件を毎回見つけて弾く。

一言

久しぶりに出たらめちゃくちゃレート溶けて青コーダーやめました。次で戻します。