本履歴

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

競技プログラミング

今月のCodeChef(http://www.codechef.com/JULY12)は、5問解けた。

どこかで見たようなのが多かったなあ。

Gift Rift(http://www.codechef.com/JULY12/problems/SAD)

行列が与えられるので、行の中で最小かつ列の中で最大となっている数値を答えろ、な問題。
異なる数値で条件を満たすものが複数あった場合はGUESSと出力。

{$R-,S-,Q-,I-,O+}
var r,c,i,j,min,max,ans:longint;
	matrix,cand:array[1..100,1..100] of longint;
begin
	readln(r,c);
	for j:=1 to r do for i:=1 to c do read(matrix[j,i]);
	for j:=1 to r do begin
		min:=100000000+1;
		for i:=1 to c do if matrix[j,i]<min then min:=matrix[j,i];
		for i:=1 to c do if matrix[j,i]=min then inc(cand[j,i]);
	end;
	
	for i:=1 to c do begin
		max:=0;
		for j:=1 to r do if matrix[j,i]>max then max:=matrix[j,i];
		for j:=1 to r do if (matrix[j,i]=max) and (cand[j,i]=1) then begin
			if (ans>0) and (ans<>matrix[j,i]) then begin
				writeln('GUESS');
				exit;
			end else ans:=matrix[j,i];
		end;
	end;
	
	if ans>0 then writeln(ans) else writeln('GUESS');
end.

Chef's Dream(http://www.codechef.com/JULY12/problems/DREAM)

最初、問題文の意味が全くわからなかったんだけど、質問と回答のやりとりからなんとか判明。こういう場合サンプルが無いと辛いね。
5 3
40 30 30 30 40
の場合は、K=3だから30,30,30は一つでカバーできる。ただ、両端の40を同時にカバーできない(K=5ならできる)ので2つ必要で合計3が解答。
ソートするだけだね。index含めてquicksortした。マージソートが安定だからそっちが速いのかなあ・・・

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

type TMeal=record
		f,i:longint;
	end;

var n,k,j,pre,ans:longint;
	meals:array[0..100005] of TMeal;

procedure rquicksort(l,r:longint);
var
	i,j:longint;
	x,tmp:TMeal;
begin
	i:=l;j:=r;
	x:=meals[l+random(r-l+1)];
	repeat
		while (meals[i].f<x.f) or ((meals[i].f=x.f) and (meals[i].i<x.i)) do inc(i);
		while (x.f<meals[j].f) or ((x.f=meals[j].f) and (x.i<meals[j].i)) do dec(j);
		if i<=j then begin
			tmp:=meals[i];meals[i]:=meals[j];meals[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
	readln(n,k);
	for j:=1 to n do with meals[j] do begin
		read(f);
		i:=j;
	end;
	rquicksort(1,n);
	//sentinel
	meals[n+1].f:=1000000000+1;
	meals[n+1].i:=n+1;
	pre:=0;
	for j:=1 to n+1 do begin
		if meals[pre].f<>meals[j].f then begin
			pre:=j;
			inc(ans);
		end else if meals[j].i-meals[pre].i>=k then begin
			pre:=j;
			inc(ans);
		end;
	end;
	writeln(ans-1);
end.

My Fair Coins(http://www.codechef.com/JULY12/problems/CSUMD)

ごにょごにょ書いてたら漸化式が出てきたので、行列のpowmodでOK。これもよく見るようになった、えへん。
f(n)=2*f(n-1)+2*f(n-2)

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

const MM=1000000007;
type TM2=array[0..1,0..1] of int64;
var t,n,i:longint;
	m:array[0..31] of TM2;
	
procedure init;
var i:longint;a,b,c,d:int64;
begin
	m[1,0,0]:=2;m[1,0,1]:=2;
	m[1,1,0]:=1;m[1,1,1]:=0;
	a:=2;b:=2;c:=1;d:=0;
	for i:=2 to 31 do begin
		m[i,0,0]:=(a*a+b*c) mod MM;
		m[i,0,1]:=(a*b+b*d) mod MM;
		m[i,1,0]:=(c*a+d*c) mod MM;
		m[i,1,1]:=(c*b+d*d) mod MM;
		a:=m[i,0,0];
		b:=m[i,0,1];
		c:=m[i,1,0];
		d:=m[i,1,1];
	end;
end;

function powmod(n:longint):int64;
var res,temp:TM2;j:longint;a,b,c,d:int64;
begin
	res[0,0]:=1;res[0,1]:=0;
	res[1,0]:=0;res[1,1]:=1;
	j:=0;
	while n>0 do begin
		inc(j);
		if n mod 2=1 then begin
			a:=res[0,0];
			b:=res[0,1];
			c:=res[1,0];
			d:=res[1,1];
			res[0,0]:=(m[j,0,0]*a+m[j,0,1]*c) mod MM;
			res[0,1]:=(m[j,0,0]*b+m[j,0,1]*d) mod MM;
			res[1,0]:=(m[j,1,0]*a+m[j,1,1]*c) mod MM;
			res[1,1]:=(m[j,1,0]*b+m[j,1,1]*d) mod MM;
		end;
		n:=n div 2;
	end;
	powmod:=(3*res[0,0]+res[0,1]) mod MM;
end;

begin
	init;
	readln(t);
	for i:=1 to t do begin
		readln(n);
		if n=1 then writeln(1) else
		if n=2 then writeln(3) else
		writeln(powmod(n-2));
	end;
end.

The Gray-Similar Code(http://www.codechef.com/JULY12/problems/GRAYSC)

今月一番簡単だった問題。前後である1ビットだけ異なるグレイコードライクな配列が与えられた時に、4つ選んでxorで0になるものがあるか、という問題。
土曜の夜布団で考えていたらできた。
まず、グレイコードライクな配列という点が重要というのがわかってきた。というのも、任意の配列だとチェックは総当りしかない。
また、与えられたグレイコードライク配列をシャッフルしても答えは全く同じになるが、この場合もグレイコードライクという情報がなくなって総当りしかなくなってしまうね。
ということで、前後でどのポジションのビットが違うかをマークしていくことにした。その情報しか活かすのはないからね。全部で64箇所だね。
ところで、配列の前後の数値でxorすると、その異なる場所(例えば、55bit目)のビットだけ立つことがわかる。配列の後方にも同じ55bit目が異なる2数があれば前の2つと後ろの2つでxorすれば0になるね。
つまり、鳩の巣論法により、ある程度大きいNでは自動的に0になる組み合わせが存在するということだ。では、その上限だが・・・計算してみたところ64+32あれば十分とわかった。キリがいいので100にして、100未満の場合はBruteforceすると
100*99*98*97/4*3*2=400万
なので、十分間に合うでしょう、でsubmit。AC。

{$R-,S-,Q-,I-,O+}
const U=100;
var n,i,j,k,l:longint;
	a:array[1..U] of qword;
	
begin
	readln(n);
	if n>U then begin
		writeln('Yes');
		exit;
	end else begin
		for i:=1 to n do read(a[i]);
		for i:=1 to n-3 do
		for j:=i+1 to n-2 do
		for k:=j+1 to n-1 do
		for l:=k+1 to n do
		if (a[i] xor a[j] xor a[k] xor a[l])=0 then
		begin
			writeln('Yes');
			exit;
		end;
	end;
	writeln('No');
end.

Restaurant Rating(http://www.codechef.com/JULY12/problems/RRATING)

これもどっかで見たことある問題と思ったら、去年の6月の問題Chef Teams(http://www.codechef.com/JUNE11/problems/CTEAMS)とほぼおんなじ。
2つのHeapを管理すればOK。ソート順が最大と最小で管理することになるので、片方マイナスをつけることで一緒に管理♪

{$R-,S-,Q-,I-,O+}
const HMAX=250000;
	SENTINEL=1000000000+1;
type THeap=record
		heap:array[0..HMAX] of longint;
		n:longint;
	end;

var n,i,escalation,operation,x:longint;
	top_review,bottom_review:THeap;

procedure init_heap(var h:THeap);
begin
	h.n:=0;
	FillChar(h.heap,sizeof(h.heap),0);
	h.heap[0]:=SENTINEL;
end;

function size(var h:THeap):longint;
begin
	size:=h.n;
end;

procedure down_heap(var h:THeap;k:longint);
label 0;
var v:longint;j:longint;
begin
	v:=h.heap[k];
	while k<=h.n div 2 do begin
		j:=2*k;
		if j<h.n then if h.heap[j]<h.heap[j+1] then inc(j);
		if v>h.heap[j] then goto 0;
		h.heap[k]:=h.heap[j];
		k:=j;
	end;
0:	h.heap[k]:=v;	
end;
	
function pop(var h:THeap):longint;
begin
	pop:=h.heap[1];
	h.heap[1]:=h.heap[h.n];
	dec(h.n);
	down_heap(h,1);
end;

procedure up_heap(var h:THeap;k:longint);
var v:longint;
begin
	v:=h.heap[k];
	while h.heap[k div 2]<v do begin
		h.heap[k]:=h.heap[k div 2];
		k:=k div 2;
	end;
	h.heap[k]:=v;
end;

procedure push(var h:THeap;score:longint);
begin
	inc(h.n);
	h.heap[h.n]:=score;
	up_heap(h,h.n);
end;

function top(var h:THeap):longint;
begin
	top:=h.heap[1];
end;

begin
	readln(n);
	init_heap(top_review);
	init_heap(bottom_review);
	push(top_review,-SENTINEL);
	for i:=1 to n do begin
		read(operation);
		if operation=2 then begin //output
			if size(top_review)>1 then writeln(-top(top_review)) else writeln('No reviews yet');
		end else begin //add
			read(x);
			if escalation=2 then begin
				if top(bottom_review)<=x then push(top_review,-x) else
				begin
					push(top_review,-pop(bottom_review));
					push(bottom_review,x);
				end;
				escalation:=0;
			end else begin
				if -top(top_review)>x then push(bottom_review,x) else begin
					push(bottom_review,-pop(top_review));
					push(top_review,-x);
				end;
				inc(escalation);
			end;
		end;
	end;
end.

Addition chainsも解きたかったけど、ぱっと思いついた2進表現ではL<501にできなかった。そんなにあまくないなー
来月もがんばろう〜