目次
AtCoder Regular Contest 136 B,C,D問題メモ
B - Triple Shift
問題
- 長さ $N$ の2つの整数列 $A=(A_1,...,A_N),B=(B_1,...,B_N)$ が与えられる
- $A$ を「隣接する3マスを好きに選び、そこのみでシフトする」ことを繰り返して $B$ に一致させられるか、判定せよ
- つまり、現在の $A_i,A_{i+1},A_{i+2}$ の値を $x,y,z$ とすると、それぞれ $z,x,y$ で置き換える
- $3 \le N \le 5000$
解法
操作では、並べ替えは発生するものの値自体は変わらないので、値やその個数が一致してないとNo。
で、制約上、端から順番に、実際に操作をシミュレートして合わせていく、ということが可能そう。
（ある数字を希望の位置まで移動させるのは最大 $O(N)$ で、全部で $O(N^2)$）
それを前提として操作をいろいろ試してみると、パターンが見えてくる。
位置 j の要素を i に持っていくとき（i<j）
■j-i が偶数なら、その間をごそっと移動させることが可能
..., A[i-1], A[i], A[i+1], A[i+2], ..., A[j-1], A[j], A[j+1], ...
↓ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
..., A[i-1], A[j], A[i], A[i+1], A[i+2], ..., A[j-1], A[j+1], ...
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
■j-i が奇数なら、どこか1箇所、入れ替わりが発生する
..., A[i-1], A[i], A[i+1], A[i+2], ..., A[j-1], A[j], A[j+1], ...
↓ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
..., A[i-1], A[j], A[i+1], A[i], A[i+2], ..., A[j-1], A[j+1], ...
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
^------^
これでシミュレートすると、最後の2要素のみ、自由に移動できずに残る。
これが $A$ と $B$ で一致すればYes、入れ替わっていればNoとなる。
難しいのは数列内に同じ要素が含まれるとき。どれを端に持っていけばよいか、一意に決められない。
しかし、これは、以下のようにすれば
同じ値 x が含まれる。 端から合わせる過程で、x のどれを持っていくか適当に決めた結果、 最後の2要素が入れ替わって残ってしまった。 A: ..., x, ..., x, ..., b, a B: ..., x, ..., x, ..., a, b xの登場順にx1,x2とする。 x1-x2間が偶数なら (x1, x2)、奇数なら (x2, x1) のように 結果的に偶数移動となるように、他の並び順を変化させずに隣まで移動させられる A: ..., ..., x, x, ..., b, a x,x ～ b,a 間も、他の並び順を変えずに x の隣まで持ってこれる。 xとbの間が偶数ならbから先に、奇数ならaから先に動かせばよい A: ..., ..., x, x, b, a, ... この4数を何回か操作することで、a,bを入れ替えられる A: ..., ..., x, x, a, b, ... 操作を逆に辿り元に戻せば、Bに一致させられる A: ..., x, ..., x, ..., a, b
ので、同じ要素が1つでも含まれる場合は、必ず一致させられるとわかる。
よりよい解法
公式解説の通り「転倒数の偶奇」が操作によって不変なので、$A$ と $B$ でそれが一致していればYes。$O(N \log{N})$
C - Circular Addition
問題
- 長さ $N$ の数列 $A_0,...,A_{N-1}$ が与えられる
- 長さ $N$ で全要素が $0$ の数列から以下の操作を繰り返して、$A$ に一致させる最低回数を求めよ
- 操作
- 任意に幅 $N$ 以下の区間を選び、一律 $1$ を加算する
- 区間は、$A_{N-1}$ と $A_0$ がつながっているものとみなしてよい
- $2 \le N \le 2 \times 10^5$
解法
両端がつながっていない場合
端の $A_0$ から、上り下りの段差数を数えればよい。
(0) 4 1 5 2 3 (0)
■
■ ■
■ ■ ■
■ ■■■
■■■■■ 4+4+1=9
差+4-3+4-3+1-3 3+3+3=9
両端に0を補うと、正と負の合計は一致するはずで、その片方のみの合計が答えとなる。
これは、操作を「差分のどこかに+1を1個、-1を1個配る」と言い換えられることからいえる。
正確には+1する場所は-1する場所より左でなくてはならないが、
全要素が非負であり、どの地点でも「今まで出てきた+1の方が、-1より多い」ことが保証されているので、実質無視できる制約。
今回の場合
操作範囲の左端にすることを「開く」、右端にすることを「閉じる」と呼ぶことにする。
ループ時は、$A_0$ で開いた操作と $A_{N-1}$ で閉じた操作、2回を1回の操作に統合できる。
■ ■ ■ ■ ■ ■ ■ ■■■ ■■■■■ || |----| 非ループ時の操作の一部を -| |----- ループ時は統合できる
統合は最大 $\min(A_0,A_{N-1})$ 回おこなえるので、 非ループ時の答えから $\min(A_0,A_{N-1})$ を引けばよい？
……というのはダメで、 「非ループの時点で全体に対する操作を最適解に含まざるをえない」ものは、最初から1回の操作なので減らせない。
3 2 ■ ■■ ■■ |--| 非ループでもループでも1回
統合できる操作というのは、より正確には「途中で一度閉じ、そこより右で再度開かれた2つの操作」となる。
よって、端から「閉じられた回数」と「それより右で開かれた回数」をDPのように求めていく。
この最大ペア数を $X$ とすると、$\min(X,A_0,A_{N-1})$ が、非ループ時から減らせる最大値となる。
本当に $X$ を達成できるの？ ループ時に統合するには、「$A_0$ と閉じられた箇所」「開かれた箇所と $A_{N-1}$」それぞれがつながっている操作でなければならないけど、それ確認してなくない？ というのがちょっと引っかかる。
たとえば $A_0～A_i$ の区間 $\times d$ 回の操作を統合させたいとして、 その間にボトルネック $A_{b} \le d$ があったりすると、$d$ 回の操作を確保できない。
■ ■ A0～Aiの操作を3回、統合したいとして、 ■ ■ 途中にAb=2があると、実際にはできない ■ .. ■ .. ■ ■ .. ■ .. ■■ A0 Ab Ai
しかしこういう場合には $A_0$ から $A_b$ までの間に $A_0-A_b$ 回分の閉じられた箇所があるはずで、 非ループ時にそっちで閉じた操作をループ時に統合することにしてしまえばよい。
どこで閉じた操作とどこで開いた操作を統合するか、というのは具体的に求める必要は無いが、 両端から貪欲にマッチングさせていくことで、統合の最大回数 $\min(X,A_0,A_{N-1})$ を達成できる。
D - Without Carry
問題
- $N$ 個の整数 $A_1,...,A_N$
- このうち、相異なる2つのペアで、筆算により繰り上がりが1度も発生しないものの個数を求めよ
- $2 \le N \le 10^6$
- $1 \le A_i \lt 10^6$
解法
$A_i$ の範囲が重要で、最大でも6桁しかない。
で、ある数、たとえば “12345” とペアにして繰り上がりが発生しないものとは、
- 一の位が4以下
- 十の位が5以下
- 百の位が6以下
- 千の位が7以下
- 一万の位が8以下
- 十万の位が9以下
であればよい。
3桁の場合で考える
仮に $A_i$ が3桁までとして3次元の座標で考える。
前処理として、“345” が与えられた整数に含まれれば格子点 $(3,4,5)$ に+1する、みたいなことをしておく。
“345” とペアになれる個数は、$(0,0,0)$ と $(6,5,4)$ を対頂点にもつ直方体に含まれる格子点の値の合計となる。
ただし自身+自身で繰り上がりが発生しないものについては、自身とのペアを除く。
3次元で累積和を取っておけば、各整数につきペアにできる値の個数をすぐに求めることができる。
6桁でも、6次元で同じことをすればよい。
実装
……のだが、6次元累積和ってどうすればいいの？と一瞬困る。
まぁ、6個の次元について順番に、他の5次元を総当たりで固定して累積和を取っていけばいいんだが、下手すると冗長なコードになる。
高速ゼータ変換を使える。
ゼータ変換というと、bit集合を使った問題で出てきて「自身を部分集合に持つ集合全体の値の総和」みたいなのを 機械的に計算できるアルゴリズムだが、今回のような多次元の累積和にも活用できる。
というか、bit集合も要は「$(0,1)$ の2値を取る次元が16個くらいあって、各次元について累積和を取る」ので、 累積和がゼータ変換の元々の意味合いともいえる。
