fLIP [CODE FESTIVAL 2017 予選A - B]

atcoder.jp

解説にある「ボタンを押す順序は関係なく、また、各行/列に対して 2 回以上ボタンを押す必要はありません」という部分がイマイチよくわからなかったので、記事を書いて理解を深めることにしました。

といっても、その疑問は以下のような図を描いた途端に解消されました。

私は前述の解説を見たときに、「ボタンを2回以上押すことで、1回押しただけではできない特殊なマス配置を作り出せるのではないか」と考えましたが、この図を見ればそんなものは存在しないことがわかります。7列目に注目してみると、この列はボタンを1回押してありますが、ここからさらにもう1回押すと、ボタンが押されていない最初の状態に戻ってきてしまいます。特定のボタンを0回押したときのマスの状態と、2回押したときのマスの状態が等しくなっているんですね。1回と3回でも同様です。したがってこの問題では、各行各列にある n*m 個のボタンを、それぞれ押してあるか押してないかという On/Off の2パターンのみを考えればよく、押した回数を考慮する必要はありません。

また、行内・列内で複数のボタンを押すとき、それらを押す順番は黒マスの数に影響しません。上の図を見てわかる通り、2,3,5,7列目のボタンをどの順番で押しても、黒マスの数は同じです。このことから黒マスの数は、押されているボタンの位置に関係なく、押されているボタンの数によって決まることがわかります。

以上から、黒マスの数を k 個にできるかどうかを求めるには、「行に配置されたn個、列に配置されたm個のボタンのうち、それぞれ何個押しているか」を全探索すればよい、ということになります。

黒マスの数は

(行内で押してあるボタンの数*m) + (列内で押してあるボタンの数*n) - (2*n*m)

で計算することができ、これが k と等しいかどうか判定していきます。

//codefestival2017-qualA-b

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt();
		for (int i=0; i<=n; i++) {
			for (int j=0; j<=m; j++) {
				if (i*m + j*n - 2*i*j == k) {
					System.out.println("Yes");
					return;
				}
			}
		}
		
		System.out.println("No");
		
	}
}