AtCoder Regular Contest 136 B,C,D問題メモ

AtCoder Regular Contest 136

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})$

Python3

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})$ を達成できる。

Python3

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以下

であればよい。

仮に $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個くらいあって、各次元について累積和を取る」ので、 累積和がゼータ変換の元々の意味合いともいえる。

• ゼータ変換・メビウス変換を理解する - Qiita

Python3