AGC037-B:RGB Balls - 思考の墓場

なんかだいたいこんな感じだけで通してしまったかも...。

問題

考察と解法

　最小化すべきものは，条件を満たすように $N$ 人に区間を割り当てたときの長さの総和である。本問の場合，区間としては $(l,r$ ]という半開区間を考えるべきだろう。さて，整数 $l_1,r_1,l_2,r_2$ があり， $\max(l_1,l_2) \lt \min(r_1,r_2)$ を満たすとしよう。ここで， $2$ 人に $l_1,l_2$ のどちらか， $r_1,r_2$ のどちらかを割り当てることを考える。このとき， $2$ 人とt $2$ つの区間の組み合わせは $4$ 通りあるが，どの場合でも $2$ つの区間長さの和は

$(\max(r_1,r_2)-\min(l_1,l_2))+2(\min(r_1,r_2)-\max(l_1,l_2))$

と書ける。この例からわかるように，区間の長さの総和を小さくするには，区間の重なりが小さい方がよい。従って，ボールの割り当てを番号の小さいボールから順に決めるときに，以下の原則を満たすべきだと考えられる。

ボールを $1$ つも割り当てられていない人に， $1$ つ目のボールを割り当てるタイミングはできるだけ遅い方がよい。
ボールを $1$ つでも割り当てられた人は，できるだけ早く $3$ 色のボールの割り当てを終えた方がよい。

　サンプル $2$ (BBRGRRGRGGRBBGB)を例に詳細を述べよう。(文字列全体で) $1$ 文字目の $B$ は， $N$ 人のうち誰かに割り当て始めるしかないので，このボールの割り当て方は $N$ 通りある。 $2$ 文字目のBは， $1$ 文字目のBを割り当てられた人以外に割り当てる必要があるので，割り当て方は $N-1$ 通りある。 $3$ 文字目のRはどうだろうか？それ以前のBのうちどちらかを割り当てられている $2$ 人に割り当てるか，それ以外の $N-2$ 人に割り当てるかのどちらかであるが，実は前者の方が真によい(このことの証明は後に回すことにする)。従って，このRの割り当て方は $2$ 通りである。 $4$ 文字目のGは現在B,Rを割り当てられた人に割り当てるのが最適であり，それは $1$ 通りである。この手続きを繰り返していくだけで答えが求まる。

　「この手続き」をもう少ししっかり述べよう。割り当てにおいて，各人に以下のような優先度を定めることができる。

優先度 $2$ ( $2$ 色のボールを割り当てられている)
タイプ2-1 Rがほしい
タイプ2-2 Bがほしい
タイプ2-3 Gがほしい
優先度 $1$ ( $1$ 色のボールを割り当てられている)
タイプ1-1 RかGがほしい
タイプ1-2 RかBがほしい
タイプ1-2 GかBがほしい
優先度0 ボールがまだ $1$ 色も割り当てられていない

答えの初期値を $1$ とし， $i$ 番目のボールを割り当てるときに優先度の高い順に該当する人が存在するかを調べ，いる場合はその人数だけ答えに乗算し，各タイプの該当者の人数調整を行う。これをボール $3N$ まで繰り返すことで答えが求まる。ここで，優先度 $1$ のうち存在するタイプが $2$ 種類の場合にどれに割り当てるべきか困りそうだが，この決め方をしているときに優先度 $1$ のうちの $2$ 種類以上のタイプが存在することはない。例えば，タイプ1-1とタイプ1-2は言い換えればBを割り当てられた人とGを割り当てられた人であるが，割り当てる過程でタイプ1-1が先に現れた場合，以後のGはタイプ1-1が存在しなくなるまでタイプ1-1に割り当てられることになる。逆の場合も同様なので，タイプ1-1とタイプ1-2は存在することができない。

　最後に，この解法の正当性を証明する。最小化すべきコストの計算方法を変えてみる。 $i$ 番目のボールを割り当てられたときに得るコストは，割り当てる以前で優先度 $1,2$ のいずれかに属している人の数である。こうすると，優先度 $2$ の人に割り当てることができるならば，それより小さい優先度の人よりも先に割り当てることで，全体のコストを真に小さくできることは明らかだろう。

　次に，優先度 $0$ よりも $1$ の方が先の方が真によいことを示そう。優先度 $0$ を先に割り当てた場合，優先度 $1$ に割り当てた場合に比べてその時点でのコストは同じだが，その後に損をすることになることを示そう。優先度 $1$ 人を $j$ とし，人 $j$ が持っているボールの色をBとする。今割り当てたい色をRとし，それを $i$ 番目とする。このR以後最初に現れるGの位置を $r$ 番目とする。上に述べた割り当て方では，このGは人 $j$ に割り当てられることに注意しよう。コストが優先度0である人 $j'$ を選び，Rを $j'$ に割り当てたときに， $r$ にあるGがどう割り当てられるかで場合分けする。

$j$ に $r$ 番目のGを割り当てることができる場合， $i$ より後から $r$ の間( $i'$ 番目とする)にRが存在することになる。 $j$ に割り当てるRを $i$ 番目に， $j'$ に割り当てるRを $i'$ 番目にすることでコストを小さくできる。
$j$ に $r$ 番目のGを割り当てることができない場合，人 $j$ に $i$ 番目にあるRを割り当てることで，人 $j$ に $r$ 番目にあるGを割り当てることができるようになる。こうすることで $j,j'$ にかかるコストをそれぞれ小さくできる。 RGBのは関係は入れ替えても同様の議論ができる。従って，優先度 $1$ の人に先に割り当てるべきであることがわかった。

　他のいかなる割り当て方よりもコストが真に小さくできるので，この数え方で不足はなく，正当性が言えた。

実装

Submission #6957966 - AtCoder Grand Contest 037
コンテスト中のものなので，上の解法と変数名の対応はめちゃくちゃ。