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

本履歴

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

GCJJ2011決勝

前日深夜のCodeforces#89 (Div. 2)に参加し練習はOK(といってもA,Bしか解けなかったが)。いざ決勝。


問題をA,B,Cと読んで、Bから解くの決定。Aは出力の精度が曖昧だったので保留。

問題B. バクテリアの増殖

まず、powmodメソッドを書いてデバッグOK。b.times{a=powmod(a,a,c)}なんてプログラムを書いてみるが、サンプル最後のものに合わない。
紙の上で考えてみると、累乗の数をmod cしてはいかんだろ、ということに気付く。累乗を減らすのはオイラーの定理でできるから、
オイラー関数phiとそれを求めるためのgcdを書く。デバッグ、OK。
次にa^phi(c) mod c=1はa,cがcoprimeの場合だけど、両辺a倍したのはいつでも成り立つよねーとトンデモ理論を構築し、いろいろ紙上で実験。
でも、どうしてもサンプルに合わないんだな。こういう時の絶望感はすごいよね。オレ才能なさすぎーみたいな。
んで、累乗をb回するときにおかしくなるのかも、と考え始め、smallの制限を見ると、b<=2だったので、small通すことに集中。
999**999がirbで表示できたので、サクっとsubmit->WA。最終的にa**aとすべきところをa*aとしていたのを発見し、small通った!

#!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

#return a^b mod c
def powmod(a,b,c)
        ans=1
        while b>0
                ans=(ans*a)%c if b%2==1
                a=(a*a)%c
                b/=2
        end
        ans
end

def gcd(a,b)
        b==0 ? a : gcd(b,a%b)
end

def phi(n)
        1.upto(n-1).map{|i|gcd(n,i)==1 ? 1 : 0}.inject(:+)
end

memoize(:phi)
#a=NArray.int(5,2)
gets.to_i.times{
        a,b,c=gets.split.map(&:to_i)
        if c==1
                ans=0
        elsif b==1
                ans=powmod(a,a,c)
        else
                p=a**a
                a=powmod(a,a,c);
                ans=powmod(a,p,c)
        end
        #b.times{a=powmod(a,p,c);p=a/(phi(c)+1)+a%(phi(c)+1)}
        write(ans)
}

問題A. アンテナ修復

この時点で誤差に対する質問と解答があったのでAに行く。
面積は0.5*a*b*sin(theta)だったような、いずれにせよ、与えられた数を円状に並べ直して、隣との積をとった和を最大にすればいいのか・・・こういうのどっかで見かけた気がするんだよな
とりあえずsmallを通すため、与えられた数をpermutationして全場合をチェック、最大を出力してsmallはOK。
Largeはsmallの結果を分析したら一目瞭然。与えられた数を小さい順にソートし、真ん中を一番小さい数にし、それ以降は左、右と交互に置いていけばOK。
こうすることで、小さい数が大きい数と掛け合わされなくなって損はしないというのはなんとなくわかるが、証明はすぐ出てこない。が、まあいい。large submit。

#mainのところのみ記載
gets.to_i.times{
	k=gets.to_f
	e=gets.split.map(&:to_i).sort.reverse
	a=[]
	flag=true
	e.each{|n|
		if flag
			a.push n
		else
			a.unshift n
		end
		flag=!flag
	}
	ans=0
	0.upto(a.size-1){|i|ans+=a[i-1]*a[i]}
	write("%f"%(0.5*Math.sin(2*Math::PI/k)*ans))
}
}

問題C. ワイルドカード

これに1時間ちょっとかけた。正規表現でマッチさせれば、smallは通りそうなんだけど、そもそも全探索のbruteforceプログラムが書けない。
Rubyがもっとも得意そうなのに、すごく無念な気持ちだ。個人的にもゴルフっぽいので解きたかった。ぐすん

問題D. クローゼットルーム

読んだ瞬間解けない子と判断して一切手を付けず。こういうのどうやって解くのか、解ける人は本当にすごいと思う。
部屋の周囲に配置してとか考えたけど、入り口から必ず辿りつけなくてはいけない、という条件がわけわかめ

問題E. 無限庭園

与えられたところから更に十数ターン紙上で進めてみると、明らかにフラクタルヒルベルト曲線っぽい。けど正確なところは不明。
んで、ロボットの通過するコースをsmallサイズでシミュレーションするプログラムを書く。デバッグ、OK。
さて、これで問題解けたかなと思ってよく読むと、ロボットは迷路の壁を作って、求めるのは迷路の2点の最短距離、
ロボットの通過した跡の2点の距離だと思っていたので、もうだめですね、はい。


あとはCとEの間を行き来していたらタイムアップ。AのSL、BのSといういつもの回答数でした。
順位はなぜか57位で、Tシャツゲット(のハズ)。Googleはきっと数を読み間違えたに違いない、と思うのであった。
まあ、日本語でできるのはうれしいので、毎年恒例となって頂ければ幸いです!>GCJJ