トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302) G,Ex問題メモ

トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)

G - Sort from 1 to 4

• 全ての要素が $1,2,3,4$ からなる長さ $N$ の数列 $A=(A_1,...,A_N)$
• 2項のスワップを繰り返し、広義単調増加にするために必要な最小操作回数を求めよ
• $2 \le N \le 2 \times 10^5$

$A$ が順列だったら、過去のABCのE～F問題くらいに出たことがあったかも。
証明は簡単ではないが、解法は直感的に思いつきやすいように思う。

$A$ をソートして、最終的な目標となる数列を $B$ とする。

A  3 1 4 1 2 3 2 3
B  1 1 2 2 3 3 3 4

巡回置換を見つける。

Ai→Bi = Aj→Bj = Ak→Bk→...
       ~~~~
       Bi=Aj であるような j を選ぶ、という意味

と辿っていって、$A_i$ に戻ってきたら1つの巡回置換。

A  3 1 4 1 2 3 2 3
B  1 1 2 2 3 3 3 4
   i     j k          3→1→2→3 の巡回置換

1つの巡回置換ループは、その長さを $n$ として、$n-1$ 回のスワップでそれぞれを正しい値にできる。
なので、なるべく多くのループを作ることで、$N-(ループ数)$ のスワップで全てを正しい値にできる。

順列の場合は $B_i=A_j$ となる $j$ が毎回1つしかないので、巡回置換の取り方も一意に決まるが、、、
今回は「$B_i=A_j$ となる $j$」が複数候補あって、どれを選ぶかでループが変わってくる。

ただ、項が1,2,3,4の4種類しかないので、ループの長さもたかだか4。 1個あたりが短い方から貪欲に確定させられないか、確かめる。

$(A_i,B_i)$ のペア（4×4で16通り）毎にカウントする。

$A_i=B_i$ の場合、そこは長さ1のループと言え、操作する必要は無い。

$(a,b),(b,a)$ というペアは長さ2のループにできる。
貪欲にマッチングさせていくと、$(a,b)$ か $(b,a)$ のいずれかが0になり、もう片方はいくつか残る可能性がある。

「ペアを全てマッチングさせず、いずれも敢えて少し残しておくことで、総合的には得する」ことはあるか？

ない。
数の整合は取れているので、もし最適なループの分け方に「$(a,b)$ だけを含むループと $(b,a)$ だけを含むループ」があった場合、 組み替えて「$(a,b),(b,a)$ のループと、それ以外」にすることが必ず可能。

a→b→c   b→a→d→e
^-----'   ^--------'
↓
a↔b  b→c→a→d→e
      ^-----------'

ループ数（操作回数）を悪化させずに長さ2のループを増やすことができるので、長さ2は最大まで作ってよい。

長さ3のループを考える。
残りは長さ4しかないので、ここまで来たら長さ3をたくさん作った方がよいのは明らか。

$(a,b),(b,c),(c,a)$ という3つ組を固定すると、$a→b→c$ の長さ3のループになる。

この時、たとえば $(a,b)$ は、$a→b→d$ のループを作るときにも使われるが、$c$ を含む方に貪欲に使ってよいのか？

貪欲に使った結果 $(a,b)$ が足りなくなり $(b,d),(d,a)$ が余ってしまった場合に、 逆にこちらを優先的に消費して、$(b,c),(c,a)$ の方を余らせた方がよかった、ということはないのか？

ない。
2個ペアを最大まで取った後、各 $(a,b),(b,a)$ の片方は0なので、双方向の辺は残っていない。
その上で、$a→b→c$、$a→b→d$ 両方が残っているのは、下の形しかない。

 a ----→ b
 ↑↖  ／│
 │  ×  │    ※(c,d)に関しては、残っているのが (d,c) の方かもしれないが、
 │↙  ＼↓      その場合、c,dを入れ替える
 d ←---- c

この中でループは $a→b→c,a→b→d,a→b→c→d$ の3通りしかない。
長さ3の2つで共通するペアは $(a,b)$ のみで、長さ3を最大まで取った結果、$(a,b)$ が残ったならそれは長さ3が取れる上限に違いないし、 $(a,b)$ が無くなったら長さ4も取れないので、（全体では整合が取れているので）長さ3の2つだけで残りを全て消費できるということになる。

よって、取る順番に依らず、長さ3のループは貪欲にとっていい。残ったものが長さ4のループとなる。

Python3

Ex - Ball Collector

• $N$ 頂点の木の各頂点に、ボールが2つずつ置かれている
  • 頂点 $i$ のボールには、それぞれ整数 $A_i,B_i$ が書かれている
• $i=2～N$ のそれぞれについて、以下に答えよ
  • 頂点 $1$ から $i$ までの最短パス上の各頂点において、置かれた2つのボールのうちそれぞれ1つを拾っていく
  • 拾ったボール群に書かれた数字の種類数の最大値を求めよ
• $2 \le N \le 2 \times 10^5$

木ではなくて数列上で同様のことをする問題は、過去に出題されたことがあった。
（$N$ 個のペア $A_i,B_i$ から1つずつ取って種類数を最大化）

数列での解法は、 「ボールに書かれた整数を頂点と見なして、各 $A_i,B_i$ を結んでいく。 各連結成分について、それが木なら辺数、木で無いなら頂点数が、取り得る種類数の最大値」 というもの。

これは、辺数（uniteされた回数）も保持するUnion-Findで実現できる。

木においても同様のことが言えるが、毎回1から各頂点への最短パスでUnion-Findを構築してたら当然TLEなので、 親とかで構築した結果を使い回す必要がある。

頂点1を根としてDFS（オイラーツアー）しながらUnion-Findを操作していくが、

• 親→子への移動では、子の $A_i,B_i$ を結ぶ
• 子から親へ戻る移動では、子で結んでいた $A_i,B_i$ を「外す」

という操作が必要になる。

通常のUnion-Findでは外す操作はできないが、外すのは「履歴において直前で結んだ頂点」なので、 履歴を管理して、1手戻す操作を可能にする「Rollback Union-Find」を使うことで、実現できる。

Python3