AtCoder Regular Contest 198 (Div. 2) A,B,C,D問題メモ

AtCoder Regular Contest 198 (Div. 2)

A - I hate 1

• 正整数 $N$ が与えられます。$1$ 以上 $N$ 以下の正整数からなる集合 $S$ であって、以下の条件を満たすものを良い集合といいます。
  • 任意の $S$ の要素 $x,y$ に対して、$x$ を $y$ で割った余りは $1$ ではない。

• 要素数が最大である良い集合を一つ構築してください。

• $1 \le N \le 2 \times 10^5$

$N$ 以下の偶数のみからなる集合は、（要素数最大かはともかく）良い集合であるのはすぐに思いつく。
これ以上の要素数の集合が作れるか？

作れない。

• $1$ が入っていたら、他の数を追加した瞬間アウト。
• $i$ と $i+1$ がともに入っていたらアウト。

よって、2からはじめて1個飛ばしである、偶数のみからなる集合より要素数の大きい集合は作れない。

ただし例外的に、$N=1$ の時のみ、$S=\{1\}$ が答えとなる。
このコーナーケースでWAを出すことによって、見事、問題タイトルを回収することができる。

Python3

B - Rivalry

• $X$ 個の $0$、$Y$ 個の $1$、$Z$ 個の $2$ からなる長さ $X+Y+Z$ の非負整数列 $A=(A_1,A_2,\dots,A_{X+Y+Z})$ であって、以下の条件を満たすものが存在するか判定してください。
  • 全ての $i(1 \le i \le X+Y+Z)$ に対して、$A_{i-1},A_{i+1}$ のうち $A_i$ 未満のものはちょうど $A_i$ 個である。
  • ただし、$A_0 = A_{X+Y+Z},A_{X+Y+Z+1} = A_1$ とします。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1 \le T \le 2 \times 10^5$
• $0 \le X,Y,Z \le 10^9$
• $3 \le X + Y + Z$

• 2の両端に2未満の要素は2個→両端は0か1
• 1の両端に1未満の要素は1個→一方には0、他方には1か2
• 0の両端に0未満の要素が0個→両端に何が来てもよい

0は自由度が高く、また好きなだけ連続させることができる。1,2は制約が強く、連続させられない。

0から始めて、間に1か2を挟んで次に0が出てくるまでのパターンは、以下に限られる。

• 0120, 0210
• 020
• 01210
• 0110

これらを（それぞれの末尾の0は除いて）好きに繰り返して1と2の個数を合わせ、余った0は最後に連続させれば構築できる。
よって、この4種類を使う回数を上から $a,b,c,d$ 回とすると、以下を満たす非負整数解が存在すればよい。

• $a+b+c+d \le X$
• $a+2c+2d = Y$
• $a+b+c = Z$
• $a,b,c,d \ge 0$

このままだと解きにくいが、式3つに変数4つで何なりと合わせることは可能そう。 適当に2変数ほどを、

• $d \le \min(Y/2, X-Z)$
• $c \le \min(Z, X-d, (Y-2d)/2)$

それぞれの上限から $0～10$ 個ほど減らした範囲を探索すると、残る $a,b$ も決まるので、条件を満たすか確認し、満たすものが見つかればよい。

Python3

上の解法では、条件を満たす $(a,b,c,d)$ の組があったとしても、そのうち $c,d$ が探索範囲にあるものが必ず存在するといえるのか？ の確認がイマイチできてなかった。
以下のように考えると見つけやすい。

• 1を2個以上、0120で使う意味は無い。0120120→0121020 と、移動させても変わらないから。
• つまり、ある $(a,b,c,d)$ で不等式が成り立つなら、$(a-2,b+1,c+1,d)$ でも成り立つ。
• $Y=a+2c+2d$ のため、$Y$ が偶数なら $a=0$、奇数なら $a=1$ と決め打って問題ない。

$a$ を確定させると、$b+c$ および $c+d$ が $Y,Z$ の式から決まる。
また、$b+c+d$ の上限が決まっていることから、 $c$ をなるべく多くして（$c=\min(b+c,c+d)$ として）、不等式を満たすのに不利にならない。

$a,c$ の2変数が固定されると、$b,d$ も決まる。これで、各ケース $O(1)$ で判定できる。

C - Error Swap

• 長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ と $B=(B_1,B_2,\dots,B_N)$ が与えられます。
• あなたは以下の操作を $31000$ 回まで行うことができます。
  • $1 \le i \lt j \le N$ を満たす整数の組 $(i,j)$ を選び、$A_i$ を $A_j - 1$ に、$A_j$ を $A_i + 1$ に置き換える。

• あなたの目標は $A=B$ とすることです。目標が達成可能か判定し、可能な場合はそのような操作列を一つ出力してください。

• $2 \le N \le 100$
• $1 \le A_i,B_i \le 100$

総和が異なる場合はNo。以下、同じとする。

同じ箇所に2回続けて操作しても意味が無いので、$N=2$ のときは「操作しないで一致」か「1回操作して一致」しかない。
以下、$N \ge 3$ とする。

$i=1,2,...,N-2$ の順に、$A_i$ を $B_i$ に合わせていく。

$A_i \lt B_i$ の場合、以下のように $A_i$ を増やせる。（ここでの $A_i$ は、初期状態ではなく、$1,...,i-1$ を合わせるまでのswap操作を反映した時点で先頭から $i$ 番目にある値）

• 右端まで順番にswapして送る
• 右端まで着いたら左端に戻す

右端までの要素数を $w$ として、1週あたり $w-2$ 増やせる。

    ┌(+1)↴┌(+1)↴┌(+1)↴┌ ... ↴
... Ai     ○      ○      ○  ... ○
     ^----------(-1)---------------'

端数は途中で打ち切って元に戻せばよい。

$A_i \gt B_i$ の時も同様に、今度は-1の方を多くなるように周回すればよい。

    ┌------------(+1)-----------↴
... Ai     ○     ○     ○  ... ○
     ^(-1)-'^(-1)-'^(-1)-'^- ... '

ここまでで、最後に2つ $A_{N-1},A_N$ が残る。
2つだけではほとんど調整できないが、 $A_{N-2}$ を媒介としつつ、$A_{N-2}$ は変えずに $A_{N-1},A_N$ を変える方法を探せばよい。

すると、以下のようにすれば、4回で $b,c$ を $b+1,c-1$ にできることがわかる。

  a    b    c
        `--'
  a   c-1  b+1
   `-------'
  b   c-1  a+1
   `--'
 c-2  b+1  a+1
   `-------'
  a   b+1  c-1

$A_{N-1} \gt B_{N-1}$ の場合は事前に1回swapして $A_{N-1} \le B_{N-1}$ の状態にしておき、 上記の4回の一連の操作を必要回数繰り返すことで $B$ に揃えられる。

回数の見積もりだが、、、正直、本番提出時点ではちゃんと31000回以内に収まる証明はできておらず、お祈りで通った。

$A_i$ を $B_i$ に合わせるための操作の副作用で、$A_{i+1}$ 以降の要素は増えたり減ったりする。
初期状態では $1 \le A_i,B_i \le 100$ という制約はあるが、 途中では負になったり100を超えたりもしうるので、$|A_i-B_i| \le 100$ とは限らなくなってしまう。

とはいえ、あまり大きく外れることはなくて、 例えばある $i$ で $A_i$ を $B_i$ に揃えるため $x$ だけ増やしたとき、 代わりに $A_{i+1}～A_N$ の総和は $x$ 減っているのだが、操作の特徴からおよそ均等に約 $x/(N-i)$ ずつ減ることになる。
「およそ均等に増えたり減ったりする」点が重要で、「$A_j$ が1000増え、$A_k$ が1000減る」みたいなことは発生しない。
またそのため、$B_i$ の制約から大きく逸脱する、たとえば「$A_{i+1},...,A_N$ が一律に $1000$ 減る」みたいなことも、 $A_{i+1}$ 以降と $B_{i+1}$ 以降の総和が合わなくなるため発生しない。
増減幅は $\pm 100$ の範囲に抑えられ、$|A_i-B_i| \le 200$ の範囲に収まると見積もれる。（端数処理などで一部の要素がこれを若干超えることは発生しうるが、微差）
これはかなり余裕を持った見積もりで、$|A_i-B_i|$ が $200$ 近くになる状態は一時的には発生し得るがそれが維持されることはないので、実際はもう少し少ないはずだが、まぁ上限として見積もっておく。

$A_i$ を $x$ 増減させるのには約 $x \times \frac{N-i+1}{N-i-1}$ 回の操作が必要となる。（$N-i+1$ 回の操作で $A_i$ を $N-i-1$ だけ増減可能）
この $i=1,2,...,N-2$ を通しての総和は、$x=200, N=100$ として、切り上げで $21713$ となる。
また、残りの末尾2要素の調整は4回で1増減できるので、$800$ 回以内には可能。
計 $22513$ 回以下となり、細かな誤差があって $N$ の数倍程度の操作が加わっても、$31000$ 回以内には可能と見積もれる。
（この誤差がどれほどになるかは、ちゃんと把握できていない）

一応、「$B_i$ と合わせる $A$ の要素を、$A_i$ 固定ではなく、その時点で $A_i,A_{i+1},...,A_N$ のうち $B_i$ に一番近い要素にする」などの小手先の処理の追加で 若干、回数は抑えられそうではあるが、ちゃんと回数見積もりができていないことには変わりない。

Python3

上記の「ぐるぐる周回させて増減させる」という解法では、 $|A_i-B_i|$ が大きくても気にせず合わせにいったり、 副作用により元々大きい $i+1$ 以降の $A_{j}$ を更に増やしてしまったり、などの無駄があった。 これを減らす。

以下の2ステップであわせる。

• 1ステップ目
  • $A$ をソートした結果を $(A_{i_1},A_{i_2},...,A_{i_N})$ とする。
  • $B$ をソートした結果を $(B_{j_1},B_{j_2},...,B_{j_N})$ とする。
  • 各 $k=1,...,N$ につき、$A_{i_k}$ を $B_{j_k}$ に（位置はともかくまず値として）あわせる。
• 2ステップ目
  • 「値を変化させないswap」により、位置をあわせる。

$(1,N)$ 以外の任意の組では「値を変えないswap」が3回かけておこなえる。
$(1,N)$ の組では5回でおこなえる。この解法ではこれを使っていく。

bとcのswap    aとbのswap    aとcのswap
 a   b   c     a   b   c     a   b   c
 `---'             `---'     `-------'
b-1 a+1  c     a  c-1 b+1   c-1  b  a+1
 `-------'     `-------'     `---'
c-1 a+1  b     b  c-1 a+1   b-1  c  a+1
 `---'             `---'         `---'
 a   c   b     b   a   c    b-1  a  c+1
                             `---'
                            a-1  b  c+1
                             `-------'
                             c   b   a

1ステップ目を考える。
$D_i$ を、「$A_{i}$ の値を合わせにいく対象を $B_j$ として、$A_i-B_j$」と定義する。
$D_i$ の正負に従って、各 $A_i$ を「-」の要素、「0」の要素、「+」の要素、の3つに分類する。

全ての $i$ で $D_i=0$ になるまで、次のように操作していく。
ここで、各 $A_i$ の分類は、自身の増減に伴い「-」「+」「0」のどれであるかは適宜変化していくものとする。

• ①左にある「+」から順に、以下をおこなう。
  • その要素が「+」である間、自身の左にある最も近い「-」とswapすることを繰り返す。
  • 左に「-」がなくなったらひとまず待機して、次の「+」に移る。
• ②全ての「-」が、全ての「+」の左にある、という状態になるまで、以下を繰り返す。
  • 最も左の「+」と、最も右の「-」を、値を変えずにswapする。
  • ①に戻る。

操作回数を①と②に分けて見積もる。ただし、$A,B$ の最大値を $M$ とする。

①は、公式Editorialにあるように $\frac{NM}{4}$ で抑えられる。

②を考える。
各周回の①が完了した時点で残っている「-」「+」の個数を $C_-,C_+$ とすると、 その周回では $\min(C_-, C_+)$ 回の操作が②に必要となる。
1回目は、仮に初期状態で1回も①をおこなえなかったとすると、上限は $\frac{3N}{2}$ となる。
2回目以降、①完了時点で残っている各「+」「-」要素の $D_k$ は、①開始前と比べて $\min(C_-,C_+)$ 以上必ず減少している （互いに、$\min(C_-,C_+)$ 回以上、$|D_k|$ を減らす方向にswapされているので）。
つまり、②の操作1回おこなう状況にある時点で、各 $D_k$ は1減っていることが保証される。
$|D_k|$ の最大値は $M$ なので、$3M$ 回以内には全ての $D_k=0$ になる。

あとは、2ステップ目で位置を合わせればよい。
$(1,N)$ のswapは必要になったとしても1回なので、$3(N-1)+2$ 回以内に必ず並び替えられる。

あわせておよそ $\frac{NM}{4}+\frac{9N}{2}+3M$ 回の操作で達成でき、$N=M=100$ の代入で3250回となる。

②は、毎回、値を変えないswapをするのではなく、 「-」「+」のいずれかが残り1個になるまでは値の変わる（1回の）swapにした方が、 それによって $D_k$ が増加してしまっても、その解消もまた1回で済むので若干効率がよいのでは？と思ったが、 周回数が増えてしまう可能性もあり、操作回数のちゃんとした見積もりができなかった。 （あと、減るとしても100以下しか違わないので微差）

D - Many Palindromes on Tree

• 頂点に $1$ から $N$ の番号がついた $N$ 頂点の木 $T$ と $N \times N$ 行列 $A = (A_{i,j})$ が与えられます。$T$ の $i$ 本目の辺は頂点 $U_i$ と頂点 $V_i$ を結ぶ辺です。また、$A$ の成分は $0$ または $1$ です。
• 整数列 $x=(x_1,x_2,\dots,x_N)$ のスコアを以下のように定義します。
  • 頂点 $1,2,...,N$ に整数 $x_1,x_2,...,x_N$ を書き込む
  • 頂点の組 $(i,j)(1 \le i,j \le N)$ に対して、$T$ における $i$ から $j$ への単純パスが通る頂点に書かれた整数列が回文であるとき、「$(i,j)$ が回文ペアである」という。
  • $A_{i,j} = 1$ かつ $(i,j)$ が回文ペアでないような $(i,j)$ が存在するとき、$x$ のスコアは $10^{100}$ とする。
  • そのような $(i,j)$ が存在しないとき、$x$ のスコアは $1 \le i,j \le N$ かつ $(i,j)$ が回文ペアであるような $(i,j)$ の個数とする。

• 全ての整数列 $x$ に対する、スコアの最小値を求めてください。

• $1 \le N \le 3000$
• $1 \le U_i,V_i \le N$
• $T$ は木である。
• $A_{i,j} \in \lbrace 0,1 \rbrace$
• $A_{i,i} = 1$
• $A_{i,j} = A_{j,i}$

発想は比較的素直だが、いくつかのステップがあり、それぞれに実装方法が複数ある。
時間をかければACまでは辿り着けそうだが、なるべく実装がシンプルな方法を思いつきたいところ。

問題の肝は、以下になる。

• $A_{i,j}=0$ である $(i,j)$ は回文ペアであってもなくても良いが、$A_{i',j'}=1$ である他の回文ペア次第では、回文ペアでなければならないような場合もある。そのような $A_{i,j}$ を、0→1にしてください。

たとえば、長い回文ペアの内側だったり、回文ペアが包含関係にある場合に対称の位置にあるペアなどがわかりやすい。
ただ、パスが絡み合う場合、パターンは多岐にわたり、とても場合分けで解くのは無理そう。

       a   b   c   d   e   f   g      (a,g) が回文ペアの場合、
... --①--②--③--④--③--②--①--    (b,f),(c,e)なども必然的に回文ペア

       a   b   c   d   e   f   g      (a,g) と (a,c) が回文ペアの場合、
... --①--②--①--④--①--②--①--    対称の位置にある (e,g) も必然的に回文ペア

以下のステップで解く。

• ①$A_{i,j}=1$ である各パス $(i,j)$ に対し「同じ値で無ければならない頂点」をUnion-Findで結んでいく。
  • 上例では、$(a,g)$ が回文ペアなら、$(a,g),(b,f),(c,e)$ が同じ値で無ければならない。
• ②各頂点ペアについて、回文ペアか判定する。
  • $(c,e),(b,f),(a,g)$ の各頂点ペアの値がそれぞれ同じなら、$(a,g)$ は回文ペア。

これらをおこなうにあたり、以下のデータを前計算しておく。 普通に各頂点からDFSすればよい。$O(N^2)$ でできる。ついでに各点間距離も計算しておく。

• $P[i,j]:=i$ から $j$ に近づくように1つ移動した時にいる頂点
  • 上例では、たとえば $P[a,g]=b$
  • $P[i,i]$ は未定義

①は、$A_{i,j}=1$ である各 $(i,j)$ からはじめて、

• $(i,j)$ をUnion-Findで結ぶ
• $(P[i,j], P[j,i])$ をUnion-Findで結ぶ
• さらにその1つ内側をUnion-Findで結ぶ
• …

多始点DFSの要領でできる。一度結んだ頂点ペアは再度探索されないように探索済みフラグを付けておくと、 各頂点ペアにつき高々1回、全体 $O(N^2)$ の処理となる。

Union-Findで異なるグループになった （同じでなければならないという制約が課されなかった）頂点ペアは、必ず違う値にしてよい。

②は、距離が短い頂点ペアから順に、回文ペアとなっているか調べていく。

長さが0の頂点ペア $(i,i)$ は必ず回文ペア（問題の制約上、はじめから $A_{i,i}=1$ のため、特に処理の必要なし）
長さが1の頂点ペア $(i,j)$ は、Union-Findで $i,j$ が同じグループかどうかですぐに判定できる。
長さが2以上の頂点ペア $(i,j)$ が回文ペアかどうかは、以下をともに満たすことと同値である。

• $i$ と $j$ がUnion-Find上で同じグループ
• $(P[i,j], P[j,i])$ が回文ペア

距離が短い頂点ペアから順に判定すると、$(i,j)$ を調べるときには $(P[i,j], P[j,i])$ の結果が分かっているので、高速に判定できる。

Python3