physics0523's Training #1 - physics0523's 精進ログ

1. C - Add Mod Operations (ばちゃ中2問目, 2500diff, 自力AC)

とりあえず $(A+x)\%y$ という操作を観察する。

気付き1: 適当に操作をかけても $A_i-A_{i+1}$ の値は変えにくいので、これを無理に変えに行く必要がある

気付き2: 片方が $\ge y$ 、片方が $<y$ でないと $A_i - A_{i+1}$ の値は変えられない

気付き3: 最大の $1$ 要素だけを $\ge y$ にすることで、最大の要素だけをうまいこと調整できないか?

気付き3-1: ↑この操作を使えば、「まだ一度も $\ge y$ に直面していない要素」の大小関係は保存できそう

例えば $7 \rightarrow 3$ としたいとき、大きい定数 $big$ をとって $x=big-4, y=big$ とでもすれば実現可能。

更に言うと、全ての要素をたった一度だけ $\ge y$ に直面させると、 $a \rightarrow b$ と変化させたいときに ( $\ge y$ のタイミングが回ってきたときに ) $big - (b-a)$ だけ値を捨てさせればよい。

また、この $big$ を十分大きく取れば、たとえば $k$ 回目の操作で $k \times big$ のように運用しても ( $\mod big$ を最後にとるものとして ) 正しい結果が得られそう。

最後に全体にある値を足して $\mod big$ する (オフセット調整) ものとすれば、ひとまず $N+1$ 回が構成できる。

あと $1$ 回をどう削るか? 答えは、もともと $A_i$ が最小であるものについて値を捨てさせなくてもいいように、他の $A_i$ に対して捨てさせる値を調整すればよい。

これで $N-1$ 回でオフセット調整以外が完了して、この問題に正解することができる。

これ以上の詳細は実装にて。

ゆっくり時間をかければ詰め切れるんだけどなぁ系。 3h だと焦って見えなくなるだけで最近のAGC-Cにしては弱いんかな…