2010年12月31日金曜日

Project Euler

■110
x=n+k
と置くと,
y=n2/k+n
となる.kはn2を割り切る必要があるため,重複を含めてn2の約数の数だけ解があることが分かる.
n=2r13r25r3
のように素因数分解出来たとき,n2の約数の数cは,
c=(2r1+1)(2r2+1)(2r3+1)…
となる.
cが8000000(重複しているので2倍)を超えるような最小のnを探索で見つける.

■135
x=a+2d,y=a+d,z=a
と置くと,
(-a+3d)(a+d)=n
となり,
n=pq
とすれば,
d=(p+q)/4
a=(-p+3q)/4
となる.nについて,a,dがそれぞれ自然数となるような(p,q)の個数が解の個数となる.

■136
135を流用.非常に時間がかかった.

■139
a<b<cとすると,小正方形の面積は,
c2-2ab=(a-b)2
なので,小正方形の辺の長さmは,
m=(b-a)
つまり(b-a)|cであるものを数えれば良い.
ピタゴラス数生成行列で探索するだけ.

2010年12月30日木曜日

Project Euler

■086
3辺をx<y<zとすると,
最短距離は
√[(x+y)2+z2]
となる.
a<b<cであるピタゴラス数
a2+b2=c2
と対比させると,
a=x+y, b=z, c=最短距離
または,
a=z, b=x+y, c=最短距離
と書ける.
ピタゴラス数(a, b, c)を適当に生成した時,前者・後者の組み合わせ数をそれぞれ以下のようになる.
・前者
1辺の最長はbで,b≦Mの時,x/2個.
・後者
1辺の最長はaで,a≦Mの時,max{(2x-y+2)/2, 0}個.

■131
実験的解法になってしまったので省略.

2010年12月29日水曜日

Project Euler

■215
可能なレンガの組み合わせをDFSか何かで予め求めbitで表現しておく.
|---|--|--|--|
ならば,000100100100とする(端は含まない).
[段数][組み合わせの番号]でDP.
i番目の組み合わせとj番目の組み合わせとが伝播亀裂していないならば,
dp[k][j]+=dp[k-1][i]
i番目の組み合わせのbit表現をbits[i]とすると,上の条件式は,
if((bits[i]&bits[j])==0)
と書ける.
intで処理しようとしたため,オーバーフローしていた事に気が付かなかった.

■178
[桁数][0~9のどれが出現したか][一番最下桁]でbitDP.
dp[0][1<<i][i]=1
を初期条件とし,以下の式で更新.
dp[k][j|(1<<(i-1))][i-1]+=dp[k-1][j][i]
dp[k][j|(1<<(i+1))][i+1]+=dp[k-1][j][i]

■190
ラグランジュの未定乗数法を使う.
f=Πk xkk
g=Σk xk-m=0
δ/δxk (f-λg)=0
δ/δλ (f-λg)=0
結果,
xk=2k/(m+1)
となる.あとは計算するだけ.

■207
数式を適当に弄ると,
2t=[1+√(1+4k)]/2
となる.ここで,1+4kは奇数であるため,1+4kが平方数となるならば,
1+4k=(2a+1)2
と書くことができ,これを解くと,
2t=a+1
k=a2+a
となる(a≧1).
となる.
a+1が2のベキ乗である時,完全な分割となるため,aを決定したとき,完全な分割であるものの割合は,
log2(a+1)/a2+a
となる.

■197
恐らく収束するだろうと見込みのもと適当なnまで値を見たところ,周期2の周期解に収束していた.よって,n=1012まで計算する必要はなく,適当なところで打ち切れば正確な答えが出る.

■159
dp[i]=iのMDRS
a[i]=iのDR
とすれば,
dp[n]=max{a[i]+dp[n/i]}
となる(iはnの約数).
但し,
a[1]=0
dp[1]=0
としておく.

2010年12月28日火曜日

Project Euler

■094
疑正三角形は,(a,a,a+1)又は(a,a+1,a+1)となる.
前者の面積は,
S=(a+1)/4√[(a-1)(3a+1)]
後者については,
S=a/4√[(a+2)(3a+2)]
となるので,根号の中身が平方数になるものを逐一数えていけば良い.

■095
真の約数の和を事前に求めておく.ある数aについて約数の和を再帰的に求めていき循環するかどうかを調べる.

■231
20000000までの素数を列挙しておけば,素因数分解(O(√n))を(おそらく)高速化できる.
150000001~20000000までの数の素因数の出現頻度から,1~50000000までの数の素因数の出現頻度を引き,和を計算する.

■235
s(5000)が容易に発散してしまうため,事前に範囲を狭めておいてから二分探索.doubleでも十分計算可能.閉じた式は使う必要無し.

■265
ビット演算を少し使って,DFSするだけ.

2010年12月27日月曜日

Project Euler

■090
組み合わせが少ない(9C62)ので全探索.9,6は区別するにも関わらず,勘定の際にはひっくり返しても良い,というややこしさがあるので注意.

■093
考えられる数式を全部試した.つまり,1,2,3,4,+,-,*,/を適当に並び替えたものを逆ポーランド記法と解釈し,(可能なものについて)構文解析する.実際には,括弧の付け方が限られるので,式の構造を決め打ちにしたほうが楽.途中計算が分数になっても良いという事に気付かなかった.a,b,c,dは,適当に4重ループを回して,適当に打ち切った時の再良解とした.

2010年12月25日土曜日

Project Euler

■051
実装が少し面倒だったがやるだけ.複数の桁を同じ数で置き換えると8つ以上の素数が出てくるので,0,1,2のどれかが2回以上出現した時のみ検査を入れる.

■066
ペル方程式の解法を実装.
http://www004.upp.so-net.ne.jp/s_honma/pell/pell.htm

2010年12月23日木曜日

Project Euler

■162
[桁数][0,1,Aの各々を1つ以上含んでいるか]でDP.
初期値は以下.
dp[1][1<<1]=1…1桁で1を含む
dp[1][1<<2]=1…1桁でAを含む
dp[1][0]=13…1桁で0,1,Aを除いた13個
最下位に0,1,…E,Fを付加していく形の更新式を作る.
dp[桁数][(1<<3)-1]が答え.
オーバーフローするので,BigIntegerで手抜きした.

■075
ピタゴラス数生成行列を使用.↓参照.
http://www.sci.hyogo-u.ac.jp/matsuyam/undergrad/gakubu07.htm
これを使うと,原始的ピタゴラス数p=[a,b,c]tから,3つの原始的ピタゴラス数qk=1,2,3=[ak,bk,ck]tを生成出来る.また,a+b+c<ak+bk+ckであることは容易に分かる.よって,a+b+c>Lとなるpで枝刈りを行うBFSをすれば良い.

■204
やるだけ.100未満の素数を先に生成し,そこから重複無く効率良く値を計算していく.

■100
青の円盤の枚数をa,赤の円盤の枚数をbとすると,
a/(a+b) * (a-1)/(a+b-1) = 1/2
が成り立つ.
これをaについて解くと,
a=[2b+1±√(8b2+1)]/2
となる.
2b+1<√(8b2+1)
かつ,
a>0であるため,
a=[2b+1+√(8b2+1)]/2
と一意に定まる.
aは自然数であるため,判別式の値8b2+1は平方数で無くてはならない.
8b2+1=k2
とし,これを整理すると,
k2-8b2=1
という形のペル方程式になる.
この最小解は,問題文より,b=1の時であるため,
k=3であると容易に分かる.

ペル方程式について以下が成り立つ.
x-Dy2=±1
について自明でない最小解を(x, y)とする.
α=x+√Dy
に対して,
αn=xn+√Dyn
とすると,(xn, yn)もまた上記方程式の解となる.

このため,α=3+√8とおき,
αn=kn+bn√8
を計算し,そこからanを算出.
an+bn>1012となれば終了.そうでなければ,nを1ずつ増加させていく.

2010年12月22日水曜日

TopCoder SRM 491

SRM 491(12/19 2:00~4:00)

悪夢は続く.

■FoxMakingDice(Div1 Easy)
立方体サイコロの各面に1~nまでの数字を割り振る.ある面とその対になる面の和はどの面についても等しく,かつk以上で開ければならない.
nとkが与えられた時,条件を満たすサイコロは何種類あるか.

問題を読み間違えてたので無理ゲーじゃん,と思っていました.

コンテスト後,他の人の回答を見たら,非常に明快に解けることが分かりました.

1. 和sumはk以上2n-1以下.
2. a<bで,a+b=sumとなる対a-bの数waysを数える.
3. ways個から3個を選択する選び方は,waysC3
4. ↑の値を全てのsumについて和を取る.
5. (a-b, c-d, e-f)という選び方をするサイコロは(同位体みたいな感じを想像すると)2通りある事が分かるので,最後に2をかける.

これを書くだけです.

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class FoxMakingDice {
int INF=1<<28;
double EPS=1e-9;

public long theCount(int n, int k) {
long res=0;
for(int sum=k;sum<=2*n-1;sum++){
long ways=0;
for(int first=1;first<=n&&first<sum-first;first++){
if(sum-first<=n){
ways++;
}
}
res+=ways*(ways-1)*(ways-2)/6;
}
res*=2;
return res;
}

void debug(Object...os){
System.err.println(Arrays.deepToString(os));
}

void print(String s){
System.out.print(s);
}

void println(String s){
System.out.println(s);
}
}


■Result
××× 0 0
0.0p

■Rating
1348 -> 1266

今年の目標は残念ながら達成出来そうに無いです….

2010年12月20日月曜日

Project Euler

■078
蟻本にあったDPを組んで,条件を満たしそうな値まで力づくで計算.

■174
173の流用.愚直にやるとO(n^2)で終わらない.

■188
オイラーの定理
aφ(n)≡1 (mod n)
a=1777は素数であり,
n=100000000で,φ(n)=40000000
となる.
指数の一番上の方から再帰的に適用していく.
意外と時間がかかるので,指数が変わらなくなった時点で計算を打ち切った.

2010年12月19日日曜日

Project Euler

■054
実装ゲー.条件に忠実に組む.
5枚のカードのマークが全て同じかどうかと,どの数字が何枚あるかを先に計算しておくと(少し)楽.

■172 4進数でビットDP
[桁数][どの数字が何回出たか]
でDP.各数字は0~3回までしか出ないので,dp[18][410]とすれば良い.
更新式は頑張る.

■173
全体の大きさをnとすると,最大の穴の大きさはn-2.
よって,使えるタイル数をmaxとすると,nが満たす条件は,
n2-(n-2)2≦max
となる.
最小の穴の大きさをkとすると,
n2-k2≦max
を満たすので,その最小値
k=ceil(√n2-max)
となる.但し,laminaeは上下左右に対称なので,n≡k mod 2を満たすようにkを補正.
n2-max<0
の場合は,k=0とすれば良い.
最後に,k,k+2,k+4,…,n-4,n-2の個数cは,
c=(n-2-k)/2+1
となる.
結構値が大きいため,intで計算したらオーバーフローした.注意注意….

■183
P=(N/k)kが最大となるkを見つける.おそらく上に凸な関数なので,三分探索でも良いが,kの値の範囲は高々Nなので,単純なループでも十分可能.また,(N/k)kを正直に計算すると,doubleでもオーバーフローするので,対数をとった値k*log(N/k)を計算.
(N/k)kが無限小数になるかどうかは,N/kが無限小数になるかどうかを確かめれば良い.そのためには,まずN/kを約分しN/k=n/dとする(各々をgcd(N,k)で割る).
d=2a5bと表す事が出来れば,有限小数,そうでなければ,無限小数.

2010年12月18日土曜日

Project Euler

■142
明らかに,計算量を減らす必要がある.
x+y=a2
x-y=b2
x+z=c2
x-z=d2
とする.
x=(a2+b2)/2
y=(a2-b2)/2
より,aとbを適当に決めることでxとyを決定できる.
次に,dを適当に決める.
c2=2x-d2
z=(c2-d2)/2
とすれば,
z<yかつc2が平方数である事を確認する事で,条件を満たすかどうかを判定できる.

■144
実装ゲー.
まず,直線と楕円の交点の方程式を解く.
次に,傾きaの直線が傾きmの接線によってどう反射すれば良いかを考える.
要するに,θ=tan-1(m)だけ逆回転→y軸対称に反転→θ回転でよい.
元の光線のベクトルをv=(1, a)する.反射した光線のベクトルをuとすれば,
u=R(θ)SR-1(θ)v
R(θ)は回転行列,Sはy軸対称に反転させる行列.
後は,適当に問題の条件を実装.ビジュアライザを作るのがオススメ.

■149
最大値の計算は全ての縦横斜めについて行う.
a[0],…,a[n-1]の部分総和の最大値の求め方.
dp[k]をa[0],…,a[k]までの部分総和の最大値とすると,
dp[k+1]=max{a[k+1], dp[k]+a[k+1]}
となる.

■150
愚直に計算するとO(n3)だが,n=1000なので現実的時間内に求められる.強いてい言うなら,横方向の総和を先にメモ化しておくと良い.
sum[n]=Σ0≦k≦na[k]
↑こんな感じ.
a[i]+…+a[j]はsum[j]-sum[i-1]で求められる(i=0の時は単純にsum[j]).

■164
dp[桁数][上から1桁目][上から2桁目]=条件を満たす数字の個数
でDP.
初期値は,
dp[0][0][0]=1
更新式は,
i+j+k≦9なるi,j,kについて,
dp[d+1][j][i]+=dp[d][k][j]

■179
約数の数はO(√n)で求められるので,計算量はO(n√n)だが,nの最大値が107と小さいので,特に工夫せず求めた.

■191
条件が変なDP.
・前日=出席,遅刻無
・前々日=出席,前日=欠席,遅刻無
・前々日=欠席,前日=欠席,遅刻無
・前日=出席,遅刻有
・前々日=出席,前日=欠席,遅刻有
・前々日=欠席,前日=欠席,遅刻有
の6変数を用いる.更新式が少し複雑になるので注意.

2010年12月17日金曜日

Project Euler

■118
再帰で全順列を生成し,その順列を適当に分割して条件を満たすか判定するだけ.簡単な枝刈りを入れれば高速.

■120
(a-1)n+(a+1)n mod a2
は結局,
2|n:
⇒2
o.w.:
⇒2an mod a2
になる.
また,2an mod a2の周期は(多分)高々aなので,計算量は一気に減る.というわけで,全探索で間に合う.

■121
[ターン数][青の個数]でDP
初期条件は,[0][0]=1.
jターン目に青(赤)を引く確率をP青(赤)(j)とすると,
P(j)=1/(j+1)
P(j)=j/(j+1)
となり,更新式は,
dp[j][0]=dp[j-1][0]*P(j)
dp[j][i]=dp[j-1][i-1]*P(j)+dp[j-1][i]*P(j) (i>0)

■123
120のaが素数バージョン.エラトステネスの篩で適当に素数を生成しておく.

2010年12月16日木曜日

Project Euler

問題文は,リンクのProject EulerやProject Euler - PukiWikiを参照して下さい.

■101
(xi, yi)の対から,多項式の係数を求める公式があった気がするけど忘れてしまったので,
Ax=y
の形の方程式に変形して(掃き出し法で)解いた.
yi=f(xi)=Σ0≦k≦nakxik
とした時,Aj, iは(j+1)i,xj=aj,yj=f(xj)となる(Aとyが既知).

■102
外積で簡単に解ける.
原点をO,3頂点をA,B,Cとする.この時,
OA×OB,OB×OC,OC×OAの符号が全て一致⇔三角形ABCは原点Oを含む.
(適当な図について,A×B=|A||B|sinθを考えれば分かる)

■104
下9桁と上15桁程度を保存しておき,そこだけを更新し逐一判定.

■113
[桁数][一番左の数字]=増加数or減少数の個数でDP.
初期条件は,
増加数[0][9]=1,減少数[0][0]=1
上で求めた値の和から,増加数かつ減少数の個数を引けば良い.

2010年12月13日月曜日

ACM/ICPCアジア地区予選 Day3

エクスカーション,いわゆる企業見学.

平日の中央線上り,という事をすっかり忘れていたため,危うく遅刻するところだった.服装は,スーツでなくていいので楽だった.DeNA,Google,KLabを回った.詳細は略.非常に申し訳ない事に,寝不足だったため,説明中に少しうたた寝をしてしまった.16:00過ぎに解散.

□全体の感想
今年が(学校としても)初めての参加だったので,分からないことが多かったですが,楽しく過ごせたと思います.私の学校には,競技プログラミングに興味を持っている学生がほぼ居なかったので,こういう場でこういう事に興味を持つ方々と色々話せた事は有益でした.他学校ではICPCの知名度が高いため,今後,東京高専にもICPCを初めとする競技プログラミングに興味をもつ人が増えてくれればと願います.まだ,2~3回は出場できるようなので,意地でも世界大会に出たいと思います.

稚拙な文章ですが読んで下さった方には感謝.

ACM/ICPCアジア地区予選 Day2

いわゆる本選.

8:40-集合
全員集合した後,会場へ移動.後ろテーブルのicp.javaとちょこちょこ話しつつ準備を進める.体調も良く,眠眠打破も服用済み.運営トラブルのため開始が遅れた.
9:49-コンテスト開始
まずは,私がテンプレを打ち込んだ後,Aを解く.BはAndoが解法を考えた(DP).主にそれに沿った組んだが,何か上手く行かないので,一旦ソースを印刷して,後回し.
いくつかの問題を読んでみるが,どれも難しそう….
Andoが修正したBを提出,WA.ちょっとして更に修正し提出,AC.
Cを実装してみるが,探索方法をちょこまか変えてしまった挙句,結局組み終わらなかった.
FはDPかな?と思って組んでみたがO(QN)の解法であったので,見事にTLE.定数倍最適化をちまちまやったが通らなかった.
終了30分前に,コスト最大のエッジから消していきDFSに経路探索という方針でGを組んだが,TLE.経路探索はDijkstraだろうなと思ったが,どう拡張すればいいか思いつかなかった.
14:49-コンテスト終了
2問ACという非常に残念な結果に終わった.12Fに移動.
15:20-問題解説
多くの問題について"easy, but not too easy."とのこと.Cは探索で良かったが,一工夫必要の模様.Fは数論的性質を使う問題だったらしい.Gはおよそ↑の方針で合ってた.急にどっと疲れが出たため,解説中うたた寝をしてしまった.
16:10-Javaチャレンジ対戦
多くのチームはそこまで用意周到ではなかったと見えて(私のチームでは,シミュレータを実装し,事前に組んだAIを持って行った),チームnyamaはどんどん勝ち進めて行き,ベスト4に入ってしまう.結局,チームImoに勝ち,3位になってしまった.1,2位が東大チームであるのに対し,3位が東京高専チームというのは若干(結構)浮いていた.
16:50-表彰式・閉会式
USAGI Codeが全問解答,化物かと思った.ちなみに,今年は(問題が難しかったためか)3問解けたら順位がついていた.
17:30-移動
近くのレストランへ移動.余り広くは無いため,身動きが厳しかった.
18:30-懇親会
食べ物は,昨日と同様主食が多く野菜が少なかった.鈴鹿高専の((^(^(^(^(^o^)^)^)^)^))とエンカウント出来た.
20:30-Sake Challenge
流れ(?)でついて来てみる.酒は強くない&明日が早いため,飲まなかった.誰が誰だか分からないため,(Twitterの)アカウント名を教えてもらうまで,フォローしていた事に気付かなかった人も.
23:20-解散
割と終電ギリギリだった.案の定,竹橋駅ユーザは私だけだった.

□反省
一番の反省点は,1つの問題に固執してしまった事にあります.また,最初はとりあえず全部の問題を読むという基本的な事が出来ませんでした.これは,別に各人がどうこうというよりも,3人チームでいかに効率良く作業を分担するか,ということに関する経験の不足から来たものだと思います.
来年は,3人とも違う学校にいるため,このメンバでの参加は最初で最後となりましたが,普段の授業などでは決して得られない経験になったと思います.
これからは,安定した実力を身に付け,様々なタイプの問題に対処できるようにしたいです.

2010年12月11日土曜日

ACM/ICPCアジア地区予選 Day1

というわけで,1日目.

■1日目

□12:45-集合
Ando,nyama,私todo,コーチが到着.2Fで受付開始まで待機.
□13:00-受付
適当に済ませ,会場に入る.チームのテーブルがUstreamのカメラに一番近くてビビる.ちなみに後ろのテーブルは,chokudaiさん率いるicp.java.後ろの方に飲み物とお菓子があったので適当に補充した.
□14:00-開会式
□15:00-トライアルユース
PCの使い方にとりあえずヒヨる,というかパスワードを知らなかった時点であばばばば.さらに,PC2の設定を間違って弄ったような気がしたようなしないようなで動かなかったのでスタッフさんを呼んだ.正常に起動するまで結構時間を取られた.適当にA,B,Cを出してみる.通った事が確認出来たので安心.キーボードがちょっと使いづらかった,Page Up, Page Downキーが無い & Delteキーが変な位置にあった.
□16:15-Javaチャレンジ
事前にシミュレータは組んだ(私が).で,作ったAIを前日に印刷しておいたので,それをひたすら打ち込んだ.作ったシミュレータが実際の物と違ったため,最初は正しく動作しなかったが,コードを微調整したらちゃんと動くようになった.あとは,Andoが少し修正を加えて提出.やはり,これをその場で考えて組むのは無理だと思った.
□17:45-Javaチャレンジ終了
3Fのホールに集まる.
□18:00-ウェルカムパーティ
とりあえず,お腹が減ってたので適当に食べる.ほとんど主食の部類に入るものだった.「これナンですか?」「ナンなんでしょう」
チーム紹介は,スライドが全てpdfに変換されることを知らなかったので,アニメーションが動かなった,残念.
津山高専や広島大学,chokudaiさんとも少し話せたので良かった.
□20:00-解散
予定より30分程早まった.この後は,さくさくっと帰宅した.最寄り駅が竹橋なのが私のみだったので悲しかった….

明日が本選….

2010年12月10日金曜日

ACM/ICPCアジア地区予選 Day0

ブログの書き方を忘れてしまっている位にご無沙汰しておりますが,私は生きております.

明日からICPCアジア地区予選です.主に↓のようなスケジュールで行われます.

12/11(土):Javaチャレンジ
12/12(日):本選
12/13(月):企業見学

Javaチャレンジは,1週間前にゲームの内容が公開されるがコーディングはその場で行う,という方式です.昨日に仲間が考えたAIで勝負します.
本選は,5時間に約10問の問題を解きます.何回かの練習の結果,4~5問は解けそうに思います.
ちなみに,今年から地元民は(委員会が用意した)ホテルに泊まることが出来ないようです,残念.

模擬地区予選や以前の地区予選の問題をここ最近何問か解きましたが,何れコードをアップします.

国内予選から約5ヶ月.ついに,というよりは,あっという間に時間は過ぎてしまい,十分な練習を行ったとは言い難いです.しかし,国内予選という公的な試合で初めて結果を残せたという事もあり,自分にとっては今年の集大成の一つなので,良い結果を残したいと思います.