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

本履歴

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

GCJ2012(Google Code Jam 2012)

奥さん!今年も始まりましたよGCJ2012。もっちろん参加、で、D.Large以外なんとか解けて、75点。予選通過できました!
ニックネームuruで参加していますよ。
Scoreboardの画面でFriendタブに行き、右上のボックスにuruと入れて、Add friendボタン押せばOKです。

さて、土曜は休出があったので、午前中問題をざっと読んで考えておいて、帰宅後解こうと思ったけど、AとBが意外に簡単なので会社行く前に解いて20点はゲットしておく方針に。
あと、全部違う言語で解こうとも思っていた・・・のだが、さて。

Problem A. Speaking in Tongues

小文字のアルファベットの集合上のbijectiveな変換を推測してね、ヒントはサンプルに書いてあるよ、という問題。なるほど、それでsmallしかないのねと納得。
方眼紙にaからzまで書いて、サンプルを元にその下に何に対応するか手で書いていった。一つピースが足りないけど一対一だから余った行き先に行くしかない。
Rubyワンライナー。通ってホット一息。

1.upto(gets.to_i){|i|puts"Case ##{i}: "+gets.tr("a-z","yhesocvxduiglbkrztnwjpfmaq")}

Problem B. Dancing With the Googlers

一人が3人の審査員に評価される毎に、差1評価でも評価の最大値がp以上かチェック。超えるならsuprising評価(差が2)にしなくていいよね、
差1評価で評価の最大値がp未満の場合は、suprising評価の場合にp以上かチェック。p以上になれるならこいつは候補として確保。
最後に候補数とsの値を元に最終解答を調整(小さい方を加える)すればOK。でも、pが0と1の場合におかしくなりそうなので、それは別のパターンとして考える。
golangで書いてみた。1.0の新しいバージョンでちゃんとしたプログラム書くのは初めて。go run b.goで動くのは簡単だなあ。
smallが通って、この時点で予選はOK。休出へ。
会社から帰ってこのコードを元にjavaで書きなおした。ほとんど同じだね。セミコロンがうざいw

package main
import."fmt"
func min(x int,y int)int{if x<y{return x};return y}
func main(){
	var t,n,s,p,tp,a,c int
	Scanln(&t)
	for i:=1;i<=t;i++{
		Scan(&n,&s,&p)
		a=0
		c=0
		for j:=1;j<=n;j++{
			Scan(&tp)
			switch tp{
				case 0: if p==0{a++}
				case 1: if p<=1{a++}
				default: if p<=(tp+2)/3{a++} else {if p<=(tp+4)/3{c++}}
			}
		}
		Printf("Case #%d: %d\n",i,a+min(s,c))
	}
}
import java.io.*;
import java.math.*;
class Main{
	public static void main(String[] args)throws Exception{	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String u=br.readLine();
		int i,j,t,n,s,p,tp,a,c;
		t=Integer.valueOf(u);
		for(i=1;i<=t;i++){
			String v=br.readLine();
			String[] vs=v.split(" ");
			n=Integer.valueOf(vs[0]);
			s=Integer.valueOf(vs[1]);
			p=Integer.valueOf(vs[2]);
			a=0;
			c=0;
			for(j=3;j<n+3;j++){
				tp=Integer.valueOf(vs[j]);
				switch(tp){
					case 0: if(p==0){a++;};break;
					case 1: if(p<=1){a++;};break;
					default: if(p<=(tp+2)/3){a++;} else {if(p<=(tp+4)/3){c++;}};
				}
			}
			System.out.printf("Case #%d: %d%n",i,a+Math.min(s,c));
		}
	}
}

Problem C. Recycled Numbers

夕方急いで帰ってきたけど、17時のCodeforcesに出られなくて意気消沈、GCJに全力と神様が言ってらっしゃるんだな。
(n,m)がリサクルペアとはnの10進表示を回転してmにできることをいうそうだ。んで、A,Bがgivenの時にA<=n

#include <stdio.h>

int a,b,t,i,j,k,s,ans;
int p10[9];
int size(int n){
	int ret;
	ret=0;
	while(n>0){
		ret++;
		n/=10;
	}
	return ret;
}

int recycled(int x,int y){
	int l;
	//printf("%d %d %d:\n",x,y,s);
	for(l=1;l<s;l++){
		x=(x%10)*p10[s-1]+(x/10);
		//printf("(%d %d)\n",x,y);
		if(x==y)return 1;
	}
	return 0;
}

main(){
	p10[0]=1;
	for(i=1;i<8;i++)p10[i]=p10[i-1]*10;
	scanf("%d\n",&t);
	for(i=1;i<=t;i++){
		scanf("%d %d\n",&a,&b);
		ans=0;
		s=size(a);
		for(j=a;j<b;j++){
			for(k=j+1;k<=b;k++){
				if(recycled(j,k))ans++;
			}
		}
		printf("Case #%d: %d\n",i,ans);
	}
}
{$R-,S-,Q-,I-,O+}
var t,a,b,i,j,k,ans,s,r:longint;
	p10:array[0..7] of longint;
	cand:array[1..9] of longint;
	cand_i:longint;

procedure init_p10;
var i:longint;
begin
	p10[0]:=1;
	for i:=1 to 7 do p10[i]:=p10[i-1]*10;
end;

procedure init_cand;
begin
	cand_i:=0;
end;

function num_cand:longint;
begin
	num_cand:=cand_i;
end;

procedure add_cand(c:longint);
var i:longint;addable:boolean;
begin
	addable:=true;
	for i:=1 to cand_i do
		if cand[i]=c then begin
			addable:=false;
			break;
		end;
	if addable then begin
		inc(cand_i);
		cand[cand_i]:=c;
	end;
end;

function digits_num(x:longint):longint;
var ret:longint;
begin
	ret:=0;
	while x>0 do begin
		inc(ret);
		x:=x div 10;
	end;
	digits_num:=ret;
end;

begin
	init_p10;
	readln(t);
	for i:=1 to t do begin
		readln(a,b);
		ans:=0;
		s:=digits_num(a);
		for j:=a to b-1 do begin
			init_cand;
			for k:=1 to s-1 do begin
				r:=(j mod p10[k])*p10[s-k]+(j div p10[k]);
				if (j<r) and (r<=b) then add_cand(r);
			end;
			inc(ans,num_cand);
		end;
		writeln('Case #',i,': ',ans);
	end;
end.

Problem D. Hall of Mirrors

光線の鏡反射の問題は、洋の東西を問わず、部屋を鏡像で拡張していき、直線のまま考えられるようにするのが定跡、ですよね?
smallの制限が2W+2H-4というパッと見変なものだったので、すぐに部屋の内部に鏡がないこと判明。定跡でいけることに気づく。
ただ本当に正しいかどうか、サンプル3の場合に方眼紙とコンパスで数えてみると・・・数がぴったり一致。
また、同じ方向に複数の自分がいる場合に、最初の自分一人だけカウントしないといけない、ということも分かった。
どうやって重複を数えないようにするか?だけど、色々考えて鏡に写った自分のいる方向ベクタを最大公約数で割ってそれをキーにハッシュに登録することで判定。


サンプル3の例
初期状態

X
.

右に鏡像をつける

XX
..

下に鏡像をつける

XX
..
..
XX

これを1ユニットとしてDの値に合わせて部屋を拡張(追加するだけ、鏡像はもう考慮しなくてOK)していく(自分のいる場所から上下左右D以上離れるように)。

部屋拡張ー

XXXXXXXXXXXXXXXXXXXXXXXX
........................
........................
XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX
........................
........................
XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX
........................
........................
XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX
........................
........................
XXXXXXXXXXXXXXXXXXXXXXXX

最後に、この部屋のすべてのマス(自分がいるマス以外)に対してiterate、Xかつ距離D以内なら自分が見える可能性があるので、手前に(自分という)障害物がないかハッシュでチェックしカウントしていけばOK!
いろいろ迷ったが、このプログラム書ける自信のある言語が自分にはないので、結局Rubyで(ただしあとでPascalにしておけば良かったと後悔、配列操作めんどくせ)

#!ruby1.9

#require "memoize"
#include Memoize
require "narray"

def write(s)
	@@n||=0
	@@n+=1
	s="Case \#%d: "%@@n+s.to_s
	puts s
	#$stderr.puts(s) 
end

def debug(s)
	$stderr.puts(s)
end

#memoize(:func)
#a=NArray.int(5,2)

def count(pattern,d)
	dd=d*d
	hash={}
	cell=NArray.int(19*d+19,19*d+19)#w,h
	h=pattern.size
	w=pattern.first.size
	x=y=0
	0.upto(h-1){|i|0.upto(w-1){|j|x,y=j,i if pattern[i][j]==1}}
	
	0.upto(h-1){|i|0.upto(w-1){|j|cell[j,i]=pattern[i][j]}}
	0.upto(h-1){|i|0.upto(w-1){|j|cell[j+w,i]=pattern[i][w-j-1]}}
	0.upto(h-1){|i|0.upto(2*w-1){|j|cell[j,i+h]=cell[j,h-i-1]}}
	h*=2
	w*=2
	t=0
	while x<d
		t+=1
		0.upto(h-1){|i|0.upto(w-1){|j|cell[t*w+j,i]=cell[j,i]}}
		x+=w
	end
	w=w*t+w
	s=0
	while y<d
		s+=1
		0.upto(h-1){|i|0.upto(w-1){|j|cell[j,s*h+i]=cell[j,i]}}
		y+=h
	end
	h=h*s+h
	0.upto(h-1){|i|0.upto(w-1){|j|cell[w+j,i]=cell[j,i]}}
	w*=2
	0.upto(h-1){|i|0.upto(w-1){|j|cell[j,h+i]=cell[j,i]}}
	h*=2
	0.upto(h-1){|i|0.upto(w-1){|j|
		if cell[j,i]==1
			_dd=(x-j)**2+(y-i)**2
			next if _dd==0
			if _dd<=dd #interior point
				g=(x-j).abs.gcd((y-i).abs)
				_x=(x-j)/g
				_y=(y-i)/g
				unless hash[[_x,_y]]
					hash[[_x,_y]]=1
				end
			end
		end
	}}
	hash.size
end

gets.to_i.times{
	h,w,d=gets.split.map(&:to_i)
	gets
	pattern=(h-2).times.map{gets.chomp.each_char.map{|c|c==?X ? 1 : 0}[1..-2]}
	gets
	write(count(pattern,d))
}

最後に、D smallはいろいろ苦戦して汚いコードになったけど、解けて本当に良かった。
前なら解けない子と判断してたと思うけど、ちょっとは成長してるかな。D large解ける人は本当にすごい。
予選通過された皆さんもおめでとうございます!!
GWという結構恵まれた期間にRound 1がありますので、頑張っていきましょうー