読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

CODE FESTIVAL 2016 予選A D

考察

まず問題文にある式がどういうものかを考えてみる。
(左上の整数) + (右下の整数) = (右上の整数) + (左下の整数)を(i,j) + (i + 1,j + 1) = (i,j + 1) + (i + 1,j) と考える。
そしてこの式を変形すると,
(i,j) - (i,j + 1) = (i + 1,j) - (i + 1,j + 1)または
(i,j) - (i + 1,j) = (i,j + 1) - (i + 1,j + 1)となる。
この変形した式が表すのは,列jと列j + 1間の値の差は行iと行i + 1で同じであるということで,これは行と列を逆にしても同じことが言える。

となると
(i,j)-(i,j+1)=(i+1,j)-(i+1,j+1)=(i + 2,j)-(i + 2,j + 1)...
という風にすべての行において(i,j) = (i,j + 1)が成り立ち, 列jにある値と列j + 1にある値の差は必ず一意になることが分かる。
これも行と列を入れ替えても同じことが成り立つ。

また(i,j)の値と(i,j + 2)の値の差もすべての行において等しいことが分かり、
これは(i,j) - (i,j + 1) = (i + 1,j) - (i + 1,j + 1) = (i + 2,j) - (i + 2,j + 1)...から列jと他のすべての列との差がすべての行において等しいということが分かる。

ある列kを基準にし,列kを0と考え,列kと他の列(0 \le i \lt C)との差をx_iとする。
また行についても同じように考えることが出来て,ある行kと他の行(0 \le i \lt R)との差をy_iとする。

以上のことを含めるとb_{i,j}は行iであり,列jに存在する値とし、
b_{i,j} = x_j + y_iを求めることが出来る。

x_0x_1x_2
y_0b_{0,0}b_{0,1}b_{0,2}
y_1b_{1,0}b_{1,1}b_{1,2}
y_2b_{2,0}b_{2,1}b_{2,2}
そして,このx_j(0 \le j \lt C)y_i(0 \le i \lt R)を頂点にして,与えられたa_i(0 \le i \lt N)を頂点x_{r_i}と頂点y_{c_i}間をつなぐ辺としてグラフにして考える。

適当な頂点から始めて辺を辿っていき,x_j + y_i = a_kとなることを目指し各頂点を通り,x_j,y_iを求めていきます。
この辺を辿っていく操作は各連結成分ごとに行います。

最終的にb_{i,j} = x_j + y_iとなっているか矛盾しているかを判定することができます。
ここで,問題の制約上各マスの値は非負整数となっているので、必ず各マスの値が0以上の値になっていなければなりません。
もし、x_j + y_i \lt 0の組み合わせが存在する場合は0以上の値に収まっていないマスが存在するので、解は「No」になります。

例)問題ページのサンプル4

x_0x_1x_2
y_00 10
y_1
y_210 20
f:id:tookunn:20160926213246j:plain
まず,上記で示したように入力で与えられたN個の辺を重みa_i(0 \le i \lt N)にして,頂点x_{r_i}と頂点y_{c_i}に張る。
それから,適当な頂点を選びます。今回の例ではy_0を選んでいます。y_0から辿っていき,それぞれx_i(0 \le i \lt C),y_i(0 \le i \lt R)を求めていきます。
今回の最初に辿る先としてはx_0x_2があります。
a_i = x_{c_j} + y_{r_i}から,辺の重みはつながっている二つの頂点の重みの合計と同値になっていなければならないので,頂点の一方でも重みが分かっていれば,
y_{r_i} = a_i - x_{c_j}みたいに式を変形して求めることが出来ます。
以上からx_0 = 0,x_2 = 10となります。
そして,y_2 = 10となり,すべての辺についてa_i = x_{c_j} + y_{r_i}が成り立つので、Yesとなります。

例)問題ページのサンプル2

x_0x_1x_2
y_001020
y_13040

f:id:tookunn:20160926213218j:plain
今回も適当な頂点として、y_0を選び,y_0 = 0とします。
そして,最初に辿る頂点はx_0,x_1,x_2になり,x_0 = 0,x_1 = 10,x_2 = 20となります。
ここで、最後に辿るy_1が問題になります。
x_0からy_1に辿るとy_1 = 30になりますが,そうなってしまうとy_1 + x_2 = 50になってしまい,y_1,x_2間の辺の重みと異なってしまうので,
今回はNoという結果になります。

公式解説
http://code-festival-2016-quala.contest.atcoder.jp/data/other/code-festival-2016-quala/editorial.pdf

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.*;
 
public class Main {
	int R,C,N;
	int[] r,c,a;
	long[][] b;
	boolean[][] used;
	ArrayList<Edge>[][] graph;
	
	private class Edge{
		int t,w;
		public Edge(int t,int w){
			this.t = t;
			this.w = w;
		}
	}
	
	private class P{
		int type,pos;
		long weight;
		public P(int type,int pos,long weight){
			this.type = type;
			this.pos = pos;
			this.weight = weight;
		}
	}
	
	public void solve() {
		R = nextInt();
		C = nextInt();
		N = nextInt();
		
		r = new int[N];
		c = new int[N];
		a = new int[N];
		
		used = new boolean[2][];
		used[0] = new boolean[R];
		used[1] = new boolean[C];
		
		b = new long[2][];
		b[0] = new long[R];
		b[1] = new long[C];
		
		graph = new ArrayList[2][];
		graph[0] = new ArrayList[R];
		graph[1] = new ArrayList[C];
		
		for(int i = 0;i < R;i++){
			graph[0][i] = new ArrayList<Edge>();
		}
		
		for(int i = 0;i < C;i++){
			graph[1][i] = new ArrayList<Edge>();
		}
		
		for(int i = 0;i < N;i++){
			r[i] = nextInt() - 1;
			c[i] = nextInt() - 1;
			a[i] = nextInt();
			
			graph[0][r[i]].add(new Edge(c[i],a[i]));
			graph[1][c[i]].add(new Edge(r[i],a[i]));
		}
		long[] min = new long[2];
		for(int i = 0;i < N;i++){
			if(used[0][r[i]])continue;
			Queue<P> q = new ArrayDeque<P>();
			//type,pos,weight
			min[0] = Long.MAX_VALUE;
		    min[1] = Long.MAX_VALUE;
			q.add(new P(0,r[i],0));
			while(q.size() > 0){
				P p = q.poll();
				if(used[p.type][p.pos])continue;
				used[p.type][p.pos] = true;
				min[p.type&1] = Math.min(min[p.type&1],p.weight);
				b[p.type][p.pos] = p.weight;
				for(Edge e : graph[p.type][p.pos]){
					q.add(new P(((p.type + 1)&1),e.t,e.w - p.weight));
				}
			}
			
			if(min[0] + min[1] < 0){
				out.println("No");
				return;
			}
		}
		for(int i = 0;i < N;i++){
			if(a[i] == b[0][r[i]] + b[1][c[i]])continue;
			out.println("No");
			return;
		}
		
		out.println("Yes");
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
 
	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;
 
	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}
 
	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}
 
	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}
 
	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}
 
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}
 
	public int nextInt() {
		return Integer.parseInt(next());
	}
 
	public long nextLong() {
		return Long.parseLong(next());
	}
 
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

考察とか結構自分の頭の中を整理するために書いたようなものなので,他の人は分かりづらいものになったかもしれませんが,
少しでも何かの気付きの手助けになればと思い,記事にして残しておきます。
間違い,指摘等あれば遠慮なくどうぞ