本履歴

購入した古本の履歴と時々プログラミング

GCJ2013(Google Code Jam 2013 Qualification Round)

さあて、今年もやってきたGCJ 2013!
ハンドルuruで参加しています。(http://www.go-hero.net/jam/13/name/uru)
当日は電王戦第四局を観つつ解こうと思っていたら、将棋が大変なことになって、GCJどころではなかった。
それでも問題文はひと通り眺めていて、既に頭のなかでは35点以上取って予選通過していたので余裕。
土曜の夜中にスタート、まずはCから。

C. Fair and Square

問題文が韻を踏んでるのが心憎い。これは昼間に10^8くらいまで力づくで計算させておいたので、Large1までは通ることはわかっていた。
方針は、事前に計算をしてFair and Squareの配列F[i]を求めておいて、A,Bが与えられたら不等式A<=F[i]<=Bがいくつのiで成り立つかを数え出力するだけ。
Fの配列が小さいので、バイナリサーチも必要ない(配列の要素数が10万とかになる場合は、A<=F[i]となる最小のi、F[j]<=Bとなる最大のjをバイナリサーチで求めてj-i+1するほうが断然速い)。
SmallをPythonで通し、Large1をRubyで通す。
Large2は他のコンテストだと、みんながどんな言語で通しているかわかるからヒントになるよなー(JavaPython多めだと多倍長使うのかー)とか思いつつ色々調べていると、どうも各桁は0,1,2しか取らないらしい。総当りで3^25なのでもうちょっと何とかしたい感じ。色々検討して、DPでやったらどうだろうとか(Q*Qがfair and square numberのときに1Q1、2Q2を考えるとn桁のFS numberの個数からn+2桁を計算できるのでは?等)ごちゃごちゃ紙を浪費してギブアップ。

B. Lawnmower

これもいい問題だなあ、と思った。方針は、Greedyに刈っていく。まず、芝生の位置を高さが大きい順にソートしておいて、大きい順に各芝生(x,y)に対し縦・横方向にその高さで刈る。両方向刈れない場合(その方向既にdoneになった芝生がある)は実現不可能を出力し終了。刈れる場合は、実際刈って、(x,y)の場所をdoneにする。これを全部できたら実現可能。Large用にPascalでコーディングしていつでもsubmit可能に。smallは他の言語でと思ったけど、時間も深夜で、高さ1,2の時にできる簡単に解く方法を思いつけなくて、Small、Large共にPascalでsubmit。計算量の計算ができなくて、100x100のケースで時間内に終わることを手元のテストケースで確認した。

{$R-,S-,Q-,I-,O+}

type Point=record
	x,y,l:longint;
end;

var t,tt,i,j,k,l,n,m,xx,yy,ll,mow_num:longint;
	target_lawn,current_lawn:array[0..101,0..101] of longint;
	fixed:array[0..101,0..101] of boolean;
	lawn:array[0..10001] of Point;
	ans:string;
	
function v_mowable(x,y,l:longint):boolean;
var i:longint;ret:boolean;
begin
	ret:=true;
	for i:=1 to n do if fixed[i,y] and (current_lawn[i,y]>l) then begin
		ret:=false;
		break;
	end;
	if ret then for i:=1 to n do current_lawn[i,y]:=l;
	v_mowable:=ret;
end;

function h_mowable(x,y,l:longint):boolean;
var j:longint;ret:boolean;
begin
	ret:=true;
	for j:=1 to m do if fixed[x,j] and (current_lawn[x,j]>l) then begin
		ret:=false;
		break;
	end;
	if ret then for j:=1 to m do current_lawn[x,j]:=l;
	h_mowable:=ret;
end;

procedure rquicksort(l,r:longint);
var
	i,j:longint;
	x,tmp:Point;
begin
	i:=l;j:=r;
	x:=lawn[l+random(r-l+1)];
	repeat
		while lawn[i].l<x.l do inc(i);
		while x.l<lawn[j].l do dec(j);
		if i<=j then begin
			tmp:=lawn[i];lawn[i]:=lawn[j];lawn[j]:=tmp;
			inc(i);dec(j);
		end;
	until i>j;
	if l<j then rquicksort(l,j);
	if i<r then rquicksort(i,r);
end;

begin
	read(tt);
	for t:=1 to tt do begin
		read(n,m);
		k:=0;
		ans:='YES';
		for i:=1 to n do for j:=1 to m do begin
			current_lawn[i,j]:=100;
			read(l);
			target_lawn[i,j]:=l;
			inc(k);
			lawn[k].x:=i;
			lawn[k].y:=j;
			lawn[k].l:=l;
		end;
		fillchar(fixed,sizeof(fixed),0);
		rquicksort(1,k);
		for i:=k downto 1 do begin
			xx:=lawn[i].x;
			yy:=lawn[i].y;
			ll:=lawn[i].l;
			if target_lawn[xx,yy]<current_lawn[xx,yy] then begin
				mow_num:=0;
				if v_mowable(xx,yy,ll) then inc(mow_num);
				if h_mowable(xx,yy,ll) then inc(mow_num);
				if mow_num=0 then begin
					ans:='NO';
					break;
				end;
				fixed[xx,yy]:=true;
			end
			else begin
				fixed[xx,yy]:=true;
			end;
		end;
		writeln('Case #',t,': ',ans);
	end;
end.

A. Tic-Tac-Toe-Tomek

これも簡単な問題。TをXやOにして一列揃ってるか調べれば良い。SmallとLargeの違いはテストケース数のみ。3時くらいでTが必ず出現すると勘違いして1 WAいただく。そこで気づけて、C言語でSmall、Go言語(golang)でLargeを通す。気づかなかったらLarge落としてたんだよなあ。おそロシア。

D. Treasure

DFSで解けそうだったのでごちゃごちゃ書いてみたけど、20分位経ってうんこコードが出来たので、これはダメだと断念。鍵の管理が結構面倒だなーとその時は思っていたけど、単に配列にして個数管理すればいいだけじゃん、キャッスルエクセレントのように。ああ、そうなんだ、これはキャッスルエクセレントなんだ。予選のDが今年は懐ゲー枠か。
面白い問題なので後日解こう。


結局5つの言語でsubmit。
現時点では115点 3261位で予選通過できそうです!
目指すぞ、1000位入りのTシャツ!!