WUPC2012 - kyuridenamidaのブログ

お久しぶりです。ブログ更新してませんでした。

WUPC2012(早稲田大学プログラミングコンテスト2012)にオンライン参加しました。僕は早稲田の学生ではないです。

結果から言うと全体で2位でした。良かったんじゃないかなと思います。

運営の皆さん、お疲れ様でした！楽しかったです。次回もあれば是非参加させてください。

コンテスト開始[00:00]

A問題を読む。readingに5秒掛からないあたりWUPCすき。経過日数という単語を見た瞬間に経過日数ライブラリを貼り付ける。
そろそろAtCoderにおけるカレンダー関連の問題飽きてきたナァという印象。バグが発生しない。

A Accepted [00:01]

通した当時は順位表見れなかったけど、FirstAcceptance頂いてたらしい。ハッピー。
B読む。読みやすすぎる。2個以上連結かぁ・・・。ウーン、"以上"とか言ってるけど3個以上連結しても損するだけなので2個選ぶ全探索する。バグが発生しない。

B Accepted [00:03]

これまたFirstAcceptanceらしい。
Cを読む。サンプルの図を見て把握して問題文一切読まずに実装、読みやすいとかいうレベルではない。ちょっと実装遅いけどコンパイルしたらサンプル一致した。バグが発生しなくてハッピー。Ｎが縦でＭが横ということに細心の注意を払った。

C Accpted [00:11]

ちょっと実装に７分は遅すぎるんよ～。(今まで何回も実装してきているので)
Dを読む。もうこの図を何度見たことか。超典型DPだったので瞬殺・・・しようと思ったけどなんか配列外参照とか恐いナァ・・・とかブルブルゆっくり実装してしまった。

D Accepted [00:14]

おー、通った。ヤッター。
Eを読む。フムフムグラフ・・・。ちょっと文多いなあ(ゆとり並感)。「最短経路」「４で割り切れるｏｒ７で割り切れる」という記述だけ見て、２８の余りを保持するダイクストラを思いつく。こういうのTopCoderのDiv2Hardとかでよく要求される発想だよね。JOI予選2011-2012問6とか。
実装。一発でコンパイル通ってサンプルも通るがそろそろコーナーケースが出てきそうな気持ちになる。まあとりあえず提出する。

E Wrong answered [00:22]

ファ！？少しだけチラホラＷＡしている。なんだろう。なんか方針間違えたのかなあ・・・。と思いつつソースは間違っていないと仮定して問題文を注意深く眺めてみる。
すると「コンテスト会場に着いたらそこから戻ったりすることは出来ない。」とか書いてある。ストーリー読んでれば自然に気づけただろうナァと思いつつまあ仕方ないネと思いながら提出。

E Accepted(1WA) [00:24]

残るはF・・・。真っ先に図を見る。えっ平行じゃなくてもよいのかヤバイヤバイ。
あっ違う。軸に平行じゃないと駄目なことを示す図だった。
ここまで30分以内に出来てしまったので"上級者は1時間で全完できる"を思い出して、『最後の問題だし防衛問題で難しいのだろう。』という発想の元考える。尺取法っぽいのとか考えるが思いつかない。
33分になっても思いつかないのでちょっと考えをリセットしてみたら、ああ二点決めたら他の２頂点定まるなということに気づく。
最初にその発想はあったのだけれど、それを捨てたのが軸に平行じゃなくてもいいと思ってたからということに気づいて絶望する。うーん、頭回ってないなあという感じ。
とりあえず実装してみる。バグる。
ちょっとなおす。

F Accepted [00:45]

やったー全完だー。standingsが見れるようになっていることにここで気づく。ペナ除けばk_operafanさんが最も早く全完していたが、こっちは１ＷＡだったので１位になっている。心ウキウキする。
ただどう考えてもみんなＷＡすると思っていたＥでＷＡしていない勢がいて、1時間以内にノーミス全完者が現れたらやばいなあと思う。明らかにそれしてきそうな人がいるし恐らく抜かれると思っていた。
53分くらいにmamekinさんに抜かれた。ノーミスとかスゲー

最終結果

全完で、ペナルティが60:42(45:42+15:00(1WA))で2位でした。YJSNPIって名前で参加してました。　順位表 - WUPC 2012 | AtCoder

感想

満足です。問題が読みやすくてとても嬉しかったです。
なんていうかＥまでほとんどコンパイル成功したらＡＣしてるソースが出来上がっていたので、実装が波に乗ってるな～と思いました。調子狂うと僕ヘボヘボになるので、Ｆで調子狂って良かったです。
ところで、僕じゃないkyuridenamidaがなぜか参加していて(1時間と十数分経過したあたりから参戦していた)、1WAも出さず全完していたので誰かと思いましたが、@rng_58さん疑惑濃厚。ソースが明らかにそれだし、参戦時刻が起床時刻と大体一致しているのでそうっぽい。何してるんすか！
CTPCを感じた。

自分の解法

A

日付からある年からの経過日数を求めるライブラリがあるのでそれ使って差取った。 O(1)

B

2つだけ選ぶのを全探索した。 O (N^2)

C

スタート-コンピュータ,コンピュータ-ゴール間で幅優先探索した。O(NM)

D

上からある座標にいるときに得ることのできる最大の和を保持するDPした。配るDPなので実装楽だった。O(N^2)

E

今どこにいるかと、28(4と7の最小公倍数)で割った余りを頂点とする拡張ダイクストラで通した。制約は読みましょう。O( (N+M) log N )

F

O(N^2)で長方形の左上と右下とかの2点を決めると、残りの2つの頂点座標も決まる。その頂点座標が本当に存在するのかどうかをO(1)で判定し、その長方形の内部に点が存在するかは前処理O(1000^2)の累積和によってO(1)で判定できる。したがって、全体の計算量はO(N^2)となり、5sであれば十分間に合う。

ソース(のテンプレ除いた一部)

A

static int getDays(int y, int m, int d)
{
  if(m <= 2){
    --y;
    m += 12;
  }
  int dy = 365 * (y - 1);
  int c = y / 100;
  int dl = (y >> 2) - c + (c >> 2);
  int dm = (m * 979 - 1033) >> 5;
  return dy + dl + dm + d - 1;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	cout << getDays(2012,c,d) - getDays(2012,a,b) << endl;
	
}

B

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	string t[50];
	for(int i = 0 ; i< n; i++) cin >> t[i];
	string a = "~";
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n ; j++){
			if ( i != j ){
				a = min(a,t[i]+t[j]);
			}
		}
	}
	cout << a << endl;
}

C

char c[500][500];
 
struct NODE{
	int x,y,c;
	NODE(int x,int y,int c) : x(x) , y(y) , c(c){}
};
#define INF (1<<21)
int bfs(int sx,int sy,int gx,int gy){
	queue<NODE> Q;
	Q.push(NODE(sx,sy,0));
	int done[500][500] = {};
	rep(i,500)rep(j,500) done[i][j] = -1;
	int dx[] = {-1,1,0,0};
	int dy[] = {0,0,-1,1};
	while(Q.size()){
		NODE q = Q.front(); Q.pop();
		if( c[q.y][q.x] == '#' ) continue;
		if( done[q.y][q.x] != -1) continue;
		else done[q.y][q.x] = true;
		if(q.x == gx && q.y == gy ) return q.c;
		for(int i = 0 ; i < 4 ; i++){
			Q.push(NODE(q.x+dx[i],q.y+dy[i],q.c+1));
		}
	}
	return INF;
}
int main(){
	ios_base::sync_with_stdio(false);
	int H,W;
	cin >> H >> W; 
	int sx , sy , gx , gy , cx, cy;
	for(int i = 0 ; i < H ; i++){
		for(int j = 0 ; j < W ; j++){
			cin >> c[i][j];
			if( c[i][j] == 'S' ){
				sx = j;
				sy = i;
				c[i][j] = '.';
			}
			if( c[i][j] == 'G' ){
				gx = j;
				gy = i;
				c[i][j] = '.';
			}
			if( c[i][j] == 'C' ){
				cx = j;
				cy = i;
				c[i][j] = '.';
			}
		}
	}
	int ans = bfs(sx,sy,cx,cy) + bfs(cx,cy,gx,gy);
	if( ans > INF ) cout << -1 << endl;
	else cout << ans << endl;
}

D

int c[110][110];
int dp[110][110];
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j <= i ; j++)
			cin >> c[i][j];
	dp[0][0] = c[0][0];
	for(int i = 0 ; i < n-1 ; i++){
		for(int j = 0 ; j <= i ; j++){
			dp[i+1][j] = max(dp[i+1][j],dp[i][j]+c[i+1][j]); 
			dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+c[i+1][j+1]); 
		}
	}
	int ans = 0;
	for(int i = 0 ; i < n ; i++)
		ans = max( ans , dp[n-1][i] );
	cout << ans << endl;
}

E

struct NODE{
	long long pos,mod,cost;
	NODE(long long pos,long long mod,long long cost) : pos(pos) , mod(mod) , cost(cost) {}
	NODE(){};
};
bool operator < (const NODE &a,const NODE &b){
	return a.cost > b.cost;
}
vector<NODE> e[1000];
 
int main(){
	ios_base::sync_with_stdio(false);
	int N , M ;
	cin >> N >> M;
	for(int i = 0 ; i < M ; i++){
		int a,b,c;
		cin >> a >> b >> c;
		e[a].push_back(NODE(b,-1,c));
		e[b].push_back(NODE(a,-1,c));
	}	
	priority_queue<NODE> Q;
	int done[1000][28] = {};
	Q.push(NODE(0,0,0));
	while(Q.size()){
		NODE q = Q.top(); Q.pop();
		if( done[q.pos][q.mod] ){
			continue;
		}else done[q.pos][q.mod] = true;
		if(q.pos == N-1 && (q.mod % 7 == 0 || q.mod % 4 == 0 ) ){
			cout << q.cost << endl;
			break;
		}
		if( q.pos == N-1 ) continue;
		for(int i = 0 ; i < e[q.pos].size() ; i++){
			Q.push(NODE(e[q.pos][i].pos,(q.mod+e[q.pos][i].cost)%28,q.cost+e[q.pos][i].cost));
		}
	}
}

F

汚い。

vector< pair<int,int> > V;
int sum[1001][1001];
int ex[1001][1001];
int main(){
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	
	for(int i = 0 ; i < N ; i++){
		int x,y;
		cin >> x >> y;
		ex[y][x] = 1;
		sum[y][x] = 1;
		V.push_back(make_pair(x,y));
	}
	for(int i = 0 ; i < 1000 ; i++){
		for(int j = 1 ; j < 1000 ; j++){
			sum[i][j] += sum[i][j-1];
		}
	}
	for(int i = 1 ; i < 1000 ; i++){
		for(int j = 0 ; j < 1000 ; j++){
			sum[i][j] += sum[i-1][j];
		}
	}
	int ans = 0;
	for(int i = 0 ; i < N ; i++){
		for(int j = i+1 ; j < N ; j++){
			int sx = V[i].first , sy = V[i].second , gx = V[j].first, gy =  V[j].second;
			if( sx > gx ) swap(sx,gx);
			if( sy > gy ) swap(sy,gy);
			if( ex[gy][sx] == 0 || ex[sy][gx] == 0 || ex[gy][gx] == 0 || ex[sy][sx] == 0) continue;
			if( gx == 0 || gy == 0 ) continue;
			int g = sum[gy-1][gx-1] - sum[gy-1][sx] - sum[sy][gx-1] + sum[sy][sx];
			
			if( g == 0 ){
				ans = max( ans , (gx - sx) * (gy - sy) ) ;
			}
		}
	}
	cout << ans << endl;
	
	
}