AtCoder Grand Contest 026 - 情報妖精の競プロ日記

AtCoder Grand Contest 026 に参加しました！
AtCoder Grand Contest 026 旧版
 AtCoder Grand Contest 026 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Grand Contest 026
rated
7/14(土) 21:00 ～ 23:30 (150分)
200-600-600-1100-1600-2000 (6問)
ペナルティ: 5分

方針

3完できれば恐らくパフォーマンス2400届く、2完なら早解きになるかな？
最低でも2問、幾何や全探索みたいな苦手問題が出なければ3問解きたいね

A - Colorful Slimes 2

$N \leq$ スライムの色数なので、色を変える時は未出現の色にすると決めておけば、色を変えたスライムは必ず両隣と色が一致しないことになります。
後は、連続したスライムの数に応じて何体色を変えるか考えてみましょう。
連続したスライムの数を $L$ とすると、 $L$ が偶数の時は半分だけ色を変えれば大丈夫です。
逆に $L$ が奇数の時は2番目のスライムから1個飛ばしで色を変えれば大丈夫ですね。
ということは、どちらにしろ $\lfloor \frac{L}{2} \rfloor$ 体の色を変えていけば大丈夫です。
後は先頭から順に変えていく数を確定させれば $O(N)$ で求めることができます。

B - rng_10s

まず、制約が大きいのでそのまま愚直にシミュレーションすることはできなさそうです。
そこで、例えば今在庫が $x$ と $y$ を用いて $Bx+y (0 \leq y < B)$ 本ある時、 $x$ 日後には $y$ 本になることは自明ですよね。
ということで、 $A$ に関して $B$ より大きいなら $\mod B$ しておきましょう。
注意点として、 $A < B$ ならそもそも初日に購入できないのでNoを返す必要があります。
次に、 $D$ 本の在庫を仕入れる時も同様に考えると、 $D$ に関しても $\mod B$ できることが分かります。
更に、 $B \leq C$ の時も売り切れる前に確実に仕入れられるので、 $D < B$ でない限りはYesになることが分かります。
また、 $D < B$ ならどう考えても在庫は減る一方なのでNoであり、ということは考える必要があるのは $C < B$ のみとなります。
ここまで見ると、全ての変数が $B$ 以下になりましたね？
ということは、 $\mod B$ 上で全て考えると上手くできるのではないかという推測が立てられます。
さて、この時に実際にどうなるかを実験してみましょう。
9 7 5 9についてmod 7上で考えると、
2本→4本→6本→-1本、これはNoですね。
14 10 8 12について考えると、
6本→0本→2本→4本→6本、以下ループするのでこれはYesです。
さて、このループに関してどうなるか更に検討してみると、次のようなことが分かります。

最初の本数を $A \mod B$ とすると、 $(A + Dx) \mod B$ の本数でループし、その値の中に $C$ より大きく $B$ より小さい値が存在するとNoになる

この時、拡張ユークリッド互除法の考え方を用いると、 $(A + \gcd(B, D)) \mod B$ の全ての値を取ることができると分かります。
後は式を細かく調整すると、 $B - \gcd(B, D) + (A \mod \gcd(B, D)) \leq C$ ならばYesになることが分かります。
つまり、纏めると以下のようになります。 $G = \gcd(B, D)$ であり、 $A \% B = A \mod B$ とします。