2013-10-06

SRM 593 Div1 250 HexagonalBoard

18:08 |

縦横 N 個の蜂の巣状のマスがあり、いくつかに印がついている。隣り合った印は違う色で塗りたい。最低何色必要か求めよ。
1≦N≦50

左上から色を決めていく（間違い）
各マスの色は、その左、左上、右上に使われている色のどれとも違う色にする
提出
嫌な予感がする
U 字状に印が繋がってた場合、一番下で合流するまで上端右側の色は決められないのでだめだ
これはあかんやつや

wikipediaとかで調査。どうも一般グラフの効率的な彩色アルゴリズムはないっぽい
蜂の巣状というのがヒントかも
全部に印がある場合、3色で塗れる

1 2 3 1 2 3
 3 1 2 3 1 2
  2 3 1 2 3 1
   ....

というわけで答えは0,1,2,3色のどれかなので泥臭く決めるのだろう
印がなければ0色
edgeがなければ1色
2色で済む場合は、DFSして交互に決めていけば色は自動的に決まる。
具体的には、グラフが森の場合と、閉路はあるんだけどすでに訪れたとこの色が自動的に決まる色と一致している場合。

// 左上の 1 から DFS 開始
- 1 ?
 2 - ?
  1 ? -
↓ 1に戻ってきたけど2の隣なので1で良かった、結果オーライ！的な
- 1 2
 2 - 1
  1 2 -

戻ってきた時に第3の色が必要なら return 3, そういうことが無かった場合は使った色数を返す。
ていうのを実装。なんかコードが汚い。75.97点。
accepted

vector <string> B;
VVI vis;
ll ans;
int N;
class HexagonalBoard {
	public:
	void dfs(int x, int y, int col) {
		if(vis[y][x]) {
			if(vis[y][x]!=col) {ans=3;return;}
			return;
		}
		vis[y][x]=col;
		int dx[] = {-1,0,1,1,0,-1};
		int dy[] = {0,-1,-1,0,1,1};
		REP(i, 6) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(0<=nx&&nx<N && 0<=ny&&ny<N && B[ny][nx]=='X') dfs(nx, ny, col==1?2:1);
		}
	}
	
	int minColors(vector <string> BB) {
		B=BB;
		N=B.size();
		vis = VVI(N, VI(N));
		ans = 0;
		REP(y, N) REP(x, N) {
			if(!vis[y][x] && B[y][x]=='X') dfs(x, y, 1);
			if(ans==3) return 3;
		}
		REP(y, N) REP(x, N) {
			ans=max(ans, vis[y][x]);
		}
		//cout<<w<<endl;
		return ans;
	}
};

SRM 593 Div1 450 MayTheBestPetWin

18:09 |

N匹の動物たちが2チームに分かれてリレー競走をする。動物 i は A[i]〜B[i] の時間で走る。
チーム分けが決まると、チームの合計タイムの差としてありうる値の最大値が決まる。その値が最小になるようにチーム分けしたとき、その最小値を求めよ。
2≦N≦50, 1≦A[i], B[i]≦10,000

わからん B[i]-A[i] すると何かに使えるか？
...

終了

@nico_shindanninさんの生放送を見る. ＼オススメですよ／（宣伝）
Sum[i] = A[i]+B[i] と置くと、答えはうまく Sum[i] だけで表せるようだ
|S fast - T slow| = |ΣA[s] - ΣB[t]| = |(SumA - ΣA[t]) - ΣB[t]| = |SumA - ΣSum[t]| (s in S, t in T)
|S slow - T fast| = |ΣB[s] - ΣA[t]| = |(SumB - ΣB[t]) - ΣA[t]| = |SumB - ΣSum[t]| (s in S, t in T)
おおおおお

↓あとで(accepted in practice room)

class MayTheBestPetWin {
	public:
	int calc(vector <int> A, vector <int> B) {
		int N = A.size();
		VI SUM(N);
		REP(i, N) SUM[i]=A[i]+B[i];
		int sumA = accumulate(ALL(A), 0);
		int sumB = accumulate(ALL(B), 0);
		int maxK = 10000 * N * 2 + 500;
		VVI dp(2, VI(maxK));
		int men=0;
		dp[men][0] = 1;
		REP(i, N) {
			REP(k, maxK) {
				if(dp[men][k]==0) continue;
				dp[1-men][k] = 1;
				dp[1-men][k + SUM[i]] = 1;
				assert(k + SUM[i] < maxK);
			}
			men ^= 1;
		}
		int ans = 1<<30;
		REP(k, maxK) {
			if(dp[men][k]) ans = min(ans, max(abs(sumA-k), abs(sumB-k)));
		}
		return ans;
	}
};

kojingharangの日記

2013-10-06

SRM 593 Div1 250 HexagonalBoard

SRM 593 Div1 450 MayTheBestPetWin