Educational Codeforms Round 108(Div.2)参加後記

Educational Codeforces Round 108 (Div. 2)

初めてDiv.2で2つのSolveを完成しました.しかし、A、Bの問題は簡単すぎる.Cも解けるのが惜しいな

A. Red and Blue Beans

(r, b)(r,\b)(r, b)1つ以上のパケットに分割できるかどうかを決定する.ri, bir_i,\b_iri​, Biはそれぞれ1個以上装着し、∧∧∧∧≤ri≦d∧r i∧b i≦d∧≤ri≤dである.
まず入力の大きさを見て、直接するのではなく、数式で表す方法があると思います.(でも入力がこんなに大きくて、最初はint資料型で、一度間違えました)
入れられるかどうか確認すればいいので、できるだけ多くのバッグを入れることができます.r, br,\br, bどちらにしても、より少ない方の個数(ここではr≧brgebr≧b)でパケットを作成すれば、パケット内のbbbは必ず1つしか入らない.∣ri∣∣≦d∣r i∣b i≦d∣ri∣≦dの条件下で、最大限に入れることができるrrr個数はb×(d+1)b\times (d + 1)b×(d+1)となる.

public class A {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			long r = Integer.parseInt(st.nextToken());
			long b = Integer.parseInt(st.nextToken());
			long d = Integer.parseInt(st.nextToken());
			if (r < b) {long temp = r; r = b; b = temp;}
			System.out.println(b * (d + 1) >= r ? "YES" : "NO");
		}
	}
	
}

B. The Cake Is a Lie

n×mn×mn×mの配列の(1, 1)(1,\1)(1, 1)から(n, m)(n,\m)(n, m)、正確にはkk料金しかかかりません.(y, x)(y,\x)(y, x)1つのセルを右に移動するとロー・インデックスと同じコストが消費され、1つのセルを下に移動するとカラム・インデックスと同じコストが消費されます.
最初はnnとmmmのサイズ制限を見てDPでアクセスを試みた.もしそうであれば,これまでに消費されたコストはDP関数のパラメータとして必要であり,当然O(100)である.×100×104)O(100\times 100\times 10^4)O(100×100×104)になると、割り当て配列だけでメモリを超える.
もしかすると x)(y,\x)(y, x)ここまでの費用を公式で知ることができますか.このような考えは、私自身が何度か描いて、ある方法で(y、 x)(y,\x)(y, xに到着しても)料金は固定されていることがわかります.しかし、これでDPで解く必要がなくなることに気づいたので、すぐに公式で終わりました.

public class B {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());		
			System.out.println(N - 1 + (M - 1) * N == K ? "YES" : "NO");
		}
	}
	
}