問題概要
Alice と Bob は 2 人で歌を歌おうとしている.曲に出現し得る音階は の整数で(低い方から高い方へ)番号付けされている.Alice に出すことのできる音は区間 内の音であり,同様に, Bob に出すことができる音は である.
2 人が歌おうとしている曲に出現する音を出現順に並べた配列 が与えられる.2 人は,出現する各音について,それを歌うのは丁度 1 人となるように歌う.また,同じ高さの音が複数回出現するときは,その全てを同じ人が歌う.
歌う人が切り替わる回数を最小化するように担当を決めたときの,担当が切り替わる回数を求めよ.
解法
を と書きます.
問題を整理すると,
- の整数を Alice か Bob のいずれかにそれぞれ割り振る
- 割り振り方によってはペナルティが発生する組合せがある
ということになります.かなり天下り的ですが,この手の問題は最小カットに帰着して解ける場合があるので,そのように考えてみます.(参考:最小カットを使って「燃やす埋める問題」を解く)
まず,Alice と Bob に対応するフローグラフの頂点をそれぞれ とし,各音階に対応する頂点を の 個作ります.また, に,Alice に歌えるなら 0 ,そうでないなら無限大(下のコードでは としています)を重みとする辺を張ります.Bob についても同様にして, の辺を張ります.ここまでで,切り替わりのペナルティを考えない場合のグラフができています.このグラフ上での有限重みのカットは,妥当な担当者割り振りの一つとなっています.
では,切り替わりペナルティを追加していきます. 上で連続する があったときに, 及び の 2 本,または, 及び の 2 本がカットされていてもグラフ全体としては カットにならないようにすればよいので, 及び にそれぞれ重み 1 の辺を張ります.このようにすると, の 2 音を違う人に割り振ったときにこの間の辺を 1 本カットする必要が生じて,丁度切り替わり回数に対応するようになります.全ての妥当な について, で同じように辺を張れば,グラフが完成します.
このグラフ上での最小カットが,問題の答えになっています.
フローグラフの頂点数が ,辺数が なので,最小カット(の双対である最大流)を求めるときに Dinic 法を使ったとすると,全体は 時間で走ることになりますが,多くの場合オーダーの見た目よりかなり高速なので,これで AC をとることができます(わたしのコードは最悪 24 ms でした).
コード
// 最大流( Dinic 法 ) O( |E||V|^2 ) class Dinic; // Dinic( |V| ) // connect( from, to, cap ) // solve( s, t ) class Singing { public: int solve( int N, int low, int high, vector <int> pitch ) { --low; --high; transform( ALL( pitch ), pitch.begin(), bind( minus< int >(), _1, 1 ) ); const int M = SZ( pitch ); Dinic mincut( N + 2 ); // [ 0, N ) := pitches const int SRC = N; const int SINK = SRC + 1; REP( i, N ) { mincut.connect( SRC, i, low <= i ? 0 : M ); mincut.connect( i, SINK, i <= high ? 0 : M ); } REP( i, M - 1 ) { const int a = pitch[i], b = pitch[ i + 1 ]; mincut.connect( a, b, 1 ); mincut.connect( b, a, 1 ); } return mincut.solve( SRC, SINK ); } };