Codeforces Round 1109 (Div. 3) 参加記

2026/07/14

私です。

Codeforces Round 1109 (Div. 3) に参加しました。4完です。D問題よりC問題の方が難しかったです。 1時にパソコンが使えなくなるという制約があるので、大体フルで参加できなくて悲しいですね。

ちなみに、今回も itertools のコメントアウトを忘れました。確認したんだけどなぁ…

もっと賢い方法がありそうですが、私はランレングス圧縮で解きました。

結構悩みました。具体的な方法を考えるより、理論上可能かどうかで判定するとうまくいきました。

簡単な証明のようなものを書きますが、

作りたい配列 $P$ の一番簡単な形は $P[i] = i \; (\forall i)$ です。なので、それを作れるか否かを判定するだけで良いと思います。(多分あってます)

個人的にこの問題が一番難しかったです。類題を挙げるならば、Codeforces 1103 - B になるのでしょうか。いや、問題を確認してみると全然違うかも。

まぁ考え方は似てるので許してください。

まず、 $GCD(x, y) \ne 1$ のケースを考えてみましょう。

となります。

次に、 $GCD(x, y) = 1$ のケースです。

$x, y$ が互いに素なので、 $mod$ を変えることができます。しかし、自由に変えられるのかを考える必要があります。未証明なのですが、 $x + y \le n$ なら変えられるような気がします。そして、それは制約で満たされています。

これらの考え方で解くことができます。

ここ3週間ぐらいどこかのコンテストで出ている気がしますね。そうです。クエリ逆読みです。

$A$ の累積和配列 $P_A$ を作成する。
$B$ を昇順ソートする。
$B$ の先頭に $0$ を追加し、 $B$ の後ろから $(B_{i-1}, B_i)$ で取り出して以下の操作を繰り返します。
- $|P_A[B_i] - P_A[B_{i-1}]|$ を足す。
最後に $P_A[n] - P_A[B_m]$ を足します。

イメージ的に ABC466 - E に似ている気もしますが、こちらは制約的にDPは不可能です。

ある範囲の値全部の符号を反転させると、その範囲における総和の符号が反転します。なので、範囲の総和を累積和で管理します。

後ろから見ていくことで、そこまでに見た範囲の値を確定することができます。なので、ある範囲に対して、貪欲に大きい方を取れば良いです。

ここでタイムアップなので、E問題以降は解けませんでした。

最初にも書いたのですが、今回は本当にちゃんと itertools のコメントアウトを確認したのですが、相変わらずこれでペナをつけるのはもったいないなぁと…

Codeforces用の環境を作成するべきなんでしょうか。うーん…

それでは、また。