CODE FESTIVAL 2015 決勝 : F - 歩くピアニスト

これは本番思いつかなかった。
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_f

問題

無限に続く長い鍵盤のピアノがある。
最初にドを鳴らす。
以後、直前に鳴らした鍵盤に隣接する白い鍵盤を鳴らすことができる。
そして最後にドを鳴らして曲を終わりにしたい。

ド～シを鳴らす回数C[1]～C[7]が与えられる。
これらの慣らす回数を満たす打鍵順が存在するか判定せよ。

解法

以下Editorialに則って解いた。
ドレミファソラシドが1周分無向グラフになったものを考える。
最初と最後に鳴らすドの分を除くと、ある音を1回鳴らすためにはそこに隣接する辺を2回通らなければならない。
言い換えると、隣接する2辺の通過回数は音を鳴らす回数の倍になるはずである。

ドは初回に鳴らす分があるので1回分C[1]をデクリメントしておく。
各頂点の通過回数から、各辺の通過回数を求めよう。
仮にドとレの間の辺の通過回数をxと置くと、レとミの間の通過回数は2*C[2]-x…と順次辺の通過回数がxの式で書ける。
最終的にシとドの間の辺は2*(C[7]-C[6]+C[5]-C[4]+C[3]-C[2])+xとなる。
よって2*(C[7]-C[6]+C[5]-C[4]+C[3]-C[2])+x+x=2*C[1]より、x=C[1]-C[2]+C[3]-C[4]+C[5]-C[6]+C[7]と求まる。

各頂点の次数は必ず整数なのでオイラー閉路が存在し、基本的には達成可能である。
ただし以下の場合は達成不可なので、それを検出しよう。

• 通過回数が負になる辺がある
• 辺の通過回数0の辺を通らないと到達できない打鍵回数正の鍵盤がある

ll C[10],D[10];
int can[7];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	FOR(i,7) cin>>C[i];
	if(C[0]==0) return _P("NO\n");
	C[0]--;
	
	D[0]=C[0]-C[6]+C[5]-C[4]+C[3]-C[2]+C[1];
	for(i=1;i<=6;i++) D[i]=2*C[i]-D[i-1];
	FOR(i,7) if(D[i]<0) return _P("NO\n");
	
	can[0]=1;
	for(i=1;i<=6;i++) {
		if(D[i-1]==0) break;
		can[i]=1;
	}
	for(i=6;i>=1;i--) {
		if(D[i]==0) break;
		can[i]=1;
	}
	FOR(i,7) if(C[i] && can[i]==0) return _P("NO\n");
	return _P("YES\n");
	
	
}

まとめ

本番は二部グラフのマッチングにしようとしてたけど、それだとダメだったっぽいな。
でもシンプルな設定ながら面白い問題でした。