torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, Single Round Match 653, Division 1, Level 2 : Singing

問題概要

 Alice と Bob は 2 人で歌を歌おうとしている.曲に出現し得る音階は 1 \sim N の整数で(低い方から高い方へ)番号付けされている.Alice に出すことのできる音は区間 [ low, N ] 内の音であり,同様に, Bob に出すことができる音は [ 1, high ] である.
 2 人が歌おうとしている曲に出現する音を出現順に並べた配列 pitch が与えられる.2 人は,出現する各音について,それを歌うのは丁度 1 人となるように歌う.また,同じ高さの音が複数回出現するときは,その全てを同じ人が歌う.
 歌う人が切り替わる回数を最小化するように担当を決めたときの,担当が切り替わる回数を求めよ.
 1 \leq low \leq high \leq N \leq 1,000
 |pitch| \leq 1,000

解法

 |pitch|M と書きます.
 問題を整理すると,

  • [ 1, N ] の整数を Alice か Bob のいずれかにそれぞれ割り振る
  • 割り振り方によってはペナルティが発生する組合せがある

ということになります.かなり天下り的ですが,この手の問題は最小カットに帰着して解ける場合があるので,そのように考えてみます.(参考:最小カットを使って「燃やす埋める問題」を解く
 まず,Alice と Bob に対応するフローグラフの頂点をそれぞれ S, T とし,各音階に対応する頂点を 1 \sim NN 個作ります.また,S \right i に,Alice に歌えるなら 0 ,そうでないなら無限大(下のコードでは M としています)を重みとする辺を張ります.Bob についても同様にして,i \right T の辺を張ります.ここまでで,切り替わりのペナルティを考えない場合のグラフができています.このグラフ上での有限重みのカットは,妥当な担当者割り振りの一つとなっています.
 では,切り替わりペナルティを追加していきます.pitch 上で連続する i, j があったときに,S \right i 及び j \right T の 2 本,または,S \right j 及び i \right T の 2 本がカットされていてもグラフ全体としては S-T カットにならないようにすればよいので,i \right j 及び j \right i にそれぞれ重み 1 の辺を張ります.このようにすると,i, j の 2 音を違う人に割り振ったときにこの間の辺を 1 本カットする必要が生じて,丁度切り替わり回数に対応するようになります.全ての妥当な i について,pitch_i, pitch_i_{ i + 1 } で同じように辺を張れば,グラフが完成します.
 このグラフ上での最小カットが,問題の答えになっています.
 フローグラフの頂点数が O( N ) ,辺数が O( M ) なので,最小カット(の双対である最大流)を求めるときに Dinic 法を使ったとすると,全体は O( NM^2 ) 時間で走ることになりますが,多くの場合オーダーの見た目よりかなり高速なので,これで 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 );
	}
};