本履歴

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

GCJJ2011

震災で延期していたGCJJ2011。もちろん参加、で2問なんとか解けて、(多分)予選通過できました!
ニックネームuruで参加しています。

問題をざっと読んで(日本語文の競技プログラム初めてかもー)、C,A,Bの順で解くの決定。

問題C. ビット数

まず、10進法でなく、2進法で考える。1111110=111111+111111という等式を見ていたら、与えられた数から11111...1を取り出せばいいんじゃね?と思いつく。
小さい数字で実験すると、まさにその通りなので、あとはプログラムして、small通った。golangで提出したので、largeがちょっと不安だったのは内緒。
今考えると、与えられた数字が1111..11の場合で場合分けしてるけど意味無いじゃん。

package main
import ."fmt"
func pop(n int64)int{
	result:=0
	for n>0{
		result+=int(n%2)
		n/=2
	}
	return result
}
func size(n int64)int{
	result:=0
	for n>0{
		result+=1
		n/=2
	}
	return result
}

func main(){
	var t,i,ans,s,p int
	var n int64
	Scanln(&t)
	for i=1;i<=t;i++{
		Scanln(&n)
		s=size(n)
		p=pop(n)
		if s==p{ans=s}else{ans=s-1+pop(n-int64((1<<(uint(s)-1))-1))}
		Printf("Case #%d: %d\n",i,ans)//Case #1: 1
	}
}

問題A. カードシャッフル

最初一読したときは、range管理をすればよさげと思い付く。一回シャッフルする毎に、MAXで2つrangeが増えていくから。シャッフル数も100なので時間的にも十分OKそう。
でも、もっといい方法あるかなと考えていたら、一回シャッフルする毎に、Wの値をupdateしていく方がプログラム簡単そう--->WA。あれ?なんでだろ?
問題文を読み間違えていて、初期位置Wが最終的にどこに行くか?と問われていると勘違い。日本語でも英語でもこの辺は変わりないなーと自分のアホさに呆れた。
シャッフルの位置を全部取得し、逆順にupdateしていくことで同じようにできること判明。pascalで提出してsmallはOK。続けてlargeもsubmit。

var t,i,j,m,c,w:longint;
	a,b:array[1..150] of longint;
begin
	readln(t);
	for i:=1 to t do begin
		readln(m,c,w);
		for j:=1 to c do readln(a[j],b[j]);
		for j:=c downto 1 do begin
			if w<=b[j] then w:=a[j]+w-1 else
			if a[j]+b[j]<=w then else w:=w-b[j];
		end;
		writeln('Case #',i,': ',w);
	end;
	dec(t);
end.

問題B. 最高のコーヒー

残るはB。こういう問題よく見かける感じだけど、いつも解けないよなーと思いつつ、紙の上で試行錯誤。んで分かったのは、貪欲でやればよさそう。
まず、幸福度が一番高いコーヒーをpopし賞味期限ギリギリで飲み終わるように飲み続け、飲み終わったら残りのコーヒーの賞味期限情報をupdate。次に幸福度が高いコーヒーをpopして・・・という方針でコーディング開始。
コーヒー数が100だからOKでしょ。んでSort処理があるのでRubyで書く。書いてるうちに、時間が残り1時間になり、どんどん汚いうんこコードがモリモリ出来上がって、タイムアップ。
嗚呼、いつものことだなーと反省しつつ、36点、295位でなんとか予選通過できました!