blog.bouzuya.net

2022-01-21 第八回 アルゴリズム実技検定 (PAST) J - 数列の反転 を解いた

第八回 アルゴリズム実技検定 (PAST) J - 数列の反転 を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_j

指定した位置の値を出力するクエリ (出力操作) と指定した範囲を反転させるクエリ (反転操作) がある。

指示通りに実装すると、数列全体の反転操作を何度も要求されたとき 10^10 になってしまい間に合わない。何かしら工夫が必要になる。

反転操作は何度繰り返したとしても、ある位置 i (0 <= i < 2 * N) で出力される値は i + 1 か 2 * N - i かの 2 種類しかない。値は位置と反転されているかで決まる。反転されているかはある位置を含む反転操作が奇数回かで決まる。

反転操作は区間なので区間加算を処理できると良さそうだ。区間加算は BIT やセグメント木を 2 つ使うか遅延セグメント木で処理できる。……がちょっと考えてみるとそこまでする必要もない。

反転操作は左右対称なので左半分があれば良い。右半分が問題になったときは反転した左半分の位置だと考えると同じことになる。そこで左半分で考える。ある位置が反転されているかを知りたいときはその位置よりも左側から中央までの反転が奇数回かが分かると良い。ある位置より左側を対象とした反転が何回あるかを取れると良い。つまり 1 点加算と区間和を高速で処理できると良い。

今回は BIT を使用した。

反転操作と左右対称の 2 箇所で反転しているので混乱する。現状の全体を出力する関数を途中まで使って壊れていないかを確認した。

今日のコミット。