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

2010年11月20日土曜日

TopCoder 練習 SumsOfPerfectPowers(SRM 350 Div1 Easy)

SumsOfPerfectPowers(SRM 350 Div1 Easy)

■問題
本家参照.

■解法
chokudaiさんのニコ生を追従して解いた.指数は2以上なので,amまたはbkの候補を先に作っておく.あとは2重ループで条件を満たす数のフラグを立てるだけ.

import java.util.*;

public class SumsOfPerfectPowers{
public int howMany(int lowerBound, int upperBound){
boolean[] dp=new boolean[upperBound+1];
TreeSet<Integer> set=new TreeSet<Integer>();
set.add(0);
set.add(1);
for(int a=2;a*a<=upperBound;a++){
for(long r=a*a;r<=upperBound;r*=a){
set.add((int)r);
}
}
for(int a:set){
for(int b:set){
if(a+b<=upperBound){
dp[a+b]=true;
}
}
}
int ret=0;
for(int i=lowerBound;i<=upperBound;i++){
if(dp[i]){
ret++;
}
}
return ret;
}
}

TopCoder 練習 KnightsTour(SRM 447 Div1 Easy)

KnightsTour(SRM 447 Div1 Easy)

■問題
本家参照.

■解法
組むだけ.特に高速化の必要もありませんでした.

import java.util.*;
import java.lang.*;

public class KnightsTour{
int[] dx={1,-1,2,-2,2,-2,1,-1};
int[] dy={2,2,1,1,-1,-1,-2,-2};
public int visitedPositions(String[] ss){
boolean[][] visited=new boolean[8][8];
int x=0,y=0;
for(int j=0;j<8;j++){
for(int i=0;i<8;i++){
if(ss[j].charAt(i)=='K'){
x=i;
y=j;
}
}
}
visited[y][x]=true;
int[] num=new int[8];
for(int c=1;;c++){
Arrays.fill(num,9);
for(int j=0;j<8;j++){
int nx=x+dx[j];
int ny=y+dy[j];
if(nx<0||nx>=8||ny<0||ny>=8||visited[ny][nx]||ss[ny].charAt(nx)=='*'){
continue;
}
num[j]=0;
visited[ny][nx]=true;
for(int i=0;i<8;i++){
int nnx=nx+dx[i];
int nny=ny+dy[i];
if(nnx<0||nnx>=8||nny<0||nny>=8||visited[nny][nnx]||ss[nny].charAt(nnx)=='*'){
continue;
}
num[j]++;
}
visited[ny][nx]=false;
}
int k=0;
for(int i=0;i<8;i++){
if(num[i]<=num[k]){
k=i;
}
}
if(num[k]>8){
return c;
}
x+=dx[k];
y+=dy[k];
visited[y][x]=true;
// System.out.println(x+","+y);
// System.out.println("num["+k+"]="+num[k]);
}
}
}

2010年11月14日日曜日

TopCoder 練習 CandidateKeys(SRM 386 Div1 Easy)

CandidateKeys(SRM 386 Div1 Easy)

■問題
本家参照.

■解法
ある列群がcandidate superkeyであるかどうかは,以下を判定すれば良い.
・その列群がsuperkeyである
・その列群の真部分集合の全要素がcandidate superkeyでない
superkeyかどうかの判断は,愚直に実装すればOK.
部分集合のビット演算は,「蟻本」の助けを借りました….

public class CandidateKeys{
int n, m;
String[] table;
public int[] getKeys(String[] table){
n=table.length;
m=table[0].length();
this.table=table;
boolean[] candidate=new boolean[1<<m];
int min=-1, max=0;
for(int sup=0;sup<1<<m;sup++){
if(isSuperKey(sup)){
boolean f=true;
for(int sub=(sup-1)&sup;sub!=0;sub=(sub-1)&sup){
f&=!candidate[sub];
}
candidate[sup]=f;
if(f){
int bit=Integer.bitCount(sup);
if(min==-1||bit<min){
min=bit;
}
if(bit>max){
max=bit;
}
}
}
// System.out.println(Integer.toString(sup,2)+":"+isSuperKey(sup)+":"+candidate[sup]);
}
if(min==-1){
return new int[0];
}
else{
return new int[]{min, max};
}
}

boolean isSuperKey(int sup){
if(sup==0) return false;
String[] ss=new String[n];
for(int j=0;j<n;j++){
int s=sup;
ss[j]="";
for(int i=m-1;i>=0;i--){
if((s&1)==1){
ss[j]=table[j].charAt(i)+ss[j];
}
s>>=1;
}
}
for(int j=0;j<n;j++){
for(int i=j+1;i<n;i++){
if(ss[i].equals(ss[j])){
return false;
}
}
}
return true;
}
}

TopCoder 練習 PrimeSequences(Member SRM 471 Div1 Easy)

PrimeSequences(Member SRM 471 Div1 Easy)

■問題
ある自然数nについて,
n,[n/2],[[n/2]/2],[[[n/2]/2]/2],…
を考える.数列の第1項から連続した素数の個数が少なくともDである数の内,N以下で最大のものを計算せよ.

■解法
ほぼやるだけ.Nがそれ程大きくないので,素数全列挙で大丈夫でした.

import java.util.*;
import java.lang.*;

public class PrimeSequences{
public int getLargestGenerator(int N, int D){
int max=10000000;
boolean[] ps=new boolean[max+1];
Arrays.fill(ps,true);
ps[0]=ps[1]=false;
for(int i=2;i<=10000000;i++){
if(ps[i]){
for(int j=2;i*j<=10000000;j++){
ps[i*j]=false;
}
}
}
int[] a=new int[max+1];
for(int i=2;i<=max;i++){
//System.out.println(i+":"+ps[i]);
if(ps[i]&&a[i]==0){
int k=1;
for(int j=i;j<=max&&ps[j];j=j*2+1){
a[j]=k++;
}
}
}
int ret=-1;
for(int i=0;i<=N;i++){
//System.out.println(i+":"+a[i]);
if(a[i]>=D){
ret=i;
}
}
return ret;
}
}

TopCoder 練習 SequenceOfCommands(SRM 473 Div1 Easy)

SequenceOfCommands(SRM 473 Div1 Easy)

■問題
ロボットに命令を与える.命令は,前進,左回転,右回転からなる.与えられた命令列を永遠に実行した場合,ロボットは初期地点から無限に遠ざかるか,そうでないか,を判定せよ.

■解法
ロボットの向きは上下左右の4通りしか無い.よって,命令列を4回実行すれば必ず元の向きを向く.この時初期地点に居なければ,ロボットが無限遠へ行ってしまうのは明らか.

public class SequenceOfCommands{
public String whatHappens(String[] commands){
String ss="";
for(String s:commands){
ss+=s;
}
ss=ss+ss+ss+ss;
int x=0,y=0,d=0;
int[] dx={1,0,-1,0};
int[] dy={0,1,0,-1};
for(char c:ss.toCharArray()){
if(c=='S'){
x+=dx[d];
y+=dy[d];
}
else if(c=='L'){
d=(d+3)%4;
}
else{
d=(d+1)%4;
}
}
return x==0&&y==0?"bounded":"unbounded";
}
}

TopCoder 練習 Islands(SRM 477 Div1 Easy)

Islands(SRM 477 Div1 Easy)

■問題
六角セルのフィールドが与えられる.各セルはWaterかLandである.WaterセルとLandセルに挟まれたBeachの合計長は幾らか.

■解法
あるセルに隣接するセルは6つあるので,各セルの右,右下,左下を調べれば良い.

public class Islands{
public int beachLength(String[] str){
int ret=0;
// j:even (i+1,j), (i,j+1), (i-1,j+1)
// j:odd (i+1,j), (i+1,j+1), (i,j+1)
int n=str.length;
int m=str[0].length();
for(int j=0;j<n;j++){
for(int i=0;i<m;i++){
int[] dx, dy;
if(j%2==0){
dx=new int[]{1,0,-1};
dy=new int[]{0,1,1};
}else{
dx=new int[]{1,1,0};
dy=new int[]{0,1,1};
}
for(int d=0;d<3;d++){
int x=i+dx[d];
int y=j+dy[d];
if(0<=x&x<m&&0<=y&&y<n&&str[j].charAt(i)!=str[y].charAt(x)){
ret++;
}
}
}
}
return ret;
}
}

TopCoder SRM 487

SRM 487(11/14 2:00~4:00)

悪夢再び….

■BunnyComputer(Div1 Easy)

コンピュータのスケジューリングを考える問題.詳細は本家サイトを御参照下さい….

0,…,kのそれぞれはどう選んでも干渉しないので,それぞれにおいて適当に判定すれば大丈夫,とか思いましたが,ちゃんとDPで最大値を計算しないとダメでした….

wataさんのコードを参考にしたコードはこちら.
public class BunnyComputer{
public int getMaximum(int[] pre, int k){
int n=pre.length;
int res=0;
for(int j=0;j<k+1;j++){
int dp1=0, dp2=0;
for(int i=j;i+k+1<n;i+=k+1){
int a1=Math.max(dp1,dp2);
int a2=dp1+pre[i]+pre[i+k+1];
dp1=a1;
dp2=a2;
}
res+=Math.max(dp1,dp2);
}
return res;
}
}

仮にk=0,preference={3,1,4,1,5,9,2,6}とします.
隣り合う2項を足し合わせれば,
a={4,5,5,6,14,11,8}
となります.言い換えれば,「数列aより,隣り合う2項を選ばないように抽出した項の総和を最大にしたい」という事ですので,これはシンプルなDPとなるのです.

■Challenge
撃墜しようとしたらされて….

■Result
××× 0 0
0.0p

■Rating
1399 -> 1348

2連続減少.実に良くないですねえ.

2010年11月9日火曜日

TopCoder 練習 Badgers(SRM 476 Div1 Easy)

Badgers(SRM 476 Div1 Easy)

■問題
まなお君は穴熊を飼うためペットショップにやって来た.ペットショップにはN匹の穴熊がいる.それぞれの穴熊は,hunger[i]だけの餌を一日に食べるが,他の穴熊が餌を食べているのを見てしまうと,更にgreed[i]だけの餌を欲しがる.まなお君は一日にtotalFoodだけの餌しかやることが出来ない.まなお君は最大に何匹の穴熊を育てることが出来るか.

■解法
仮にi匹を飼うとすると,
穴熊kは,
hunger[k]+(i-1)greed[k]
だけの餌を欲しがる.よって,上の値をN匹全てに計算しソートすることで,i匹飼うことが出来るかどうか判定することが出来る.
Nは高々50までなので,i=1,…,Nについて逐一判定すればOK.

import java.lang.*;
import java.util.*;

public class Badgers{
public int feedMost(int[] hunger, int[] greed, int totalFood){
int n=hunger.length;
int ret=0;
int[] a=new int[n];
for(int i=1;i<=n;i++){
for(int k=0;k<n;k++){
a[k]=hunger[k]+(i-1)*greed[k];
}
Arrays.sort(a);
//System.out.println(i+":"+Arrays.toString(a));
int tot=0;
for(int k=0;k<i;k++){
tot+=a[k];
}
//System.out.println("tot:"+tot);
if(tot<=totalFood){
ret=i;
}
}
return ret;
}
}

TopCoder 練習 BuildBridge(SRM 295 Div1 Easy)

BuildBridge(SRM 295 Div1 Easy)

■問題
カードの束がある.束が崩れないようにカードを一枚ずつずらしていって橋を作る.長さがLのカードを使って長さDの橋を作るためには,何枚のカードが必要か.

■解法
L=1の時,n枚のカードを重ねると,最大の全長は,
Total Length(n) = Σ1≦k≦n1/2k
となるため,Total Length(n)≧Dとなるnを求めれば良い.

public class BuildBridge{
public int howManyCards(int d, int l){
double dd=(double)d/l;
double tot=0;
for(int i=1;;i++){
tot+=0.5/i;
if(tot+1e-9>dd) return i;
}
}
}


EPS=1e-9としましたが,もう少し小さい(1e-11位)方が安全だと思いました.

TopCoder 練習 NewAlbum(SRM 296 Div1 Easy)

NewAlbum(SRM 296 Div1 Easy)

■問題
length分/曲である音楽をnSongs曲CDに入れたい.但し,1枚辺りcdCapacity分しかCDに入れることは出来ない.また,CDに詰める曲数が13で割りきれてはいけない.最小何枚のCDで足りるか.

■解法
下のコードはかなり適当ですが,方針は以下の通り.
1. 1枚のCDに最大で何曲詰められるかを計算.
2. 13で割り切れるかどうかを考慮しない状態で,必要なCDの最小枚数を求める.
3. どう分配しても13で割りきれてしまう場合は,CDの枚数を+1する.

public class NewAlbum{
public int leastAmountOfCDs(int nSongs, int length, int cdCapacity){
long oneCd=1;
for(;(oneCd+1)*length+(oneCd)<=cdCapacity;oneCd++)
;
if(oneCd%13==0) oneCd--;
long left=0, right=1000000;
for(int i=0;i<100;i++){
long mid=(left+right)/2;
if(nSongs<=oneCd*mid)
right=mid;
else
left=mid;
}
int ret=(int)right;
if(nSongs%ret==0&(nSongs/ret)%13==0)
ret++;
if((nSongs%oneCd)%13==0&&oneCd*ret==nSongs+1)
ret++;
return ret;
}
}

TopCoder 練習 OptimalQueues(SRM 297 Div1 Easy)

OptimalQueues(SRM 297 Div1 Easy)

■問題
一度の手続きにserviceTime分かかる窓口がtellerCount個ある.
既に入り口でclientArrivals[i]分待っている客がn人いる.全ての客に対して手続きを行うが,待ち時間の最大値を最小化したい.最小化するように客を選んだ時,その最小値はいくらか.

■解法
まずソートする.つまり,待ち時間clientArrivals[i]が大きい客から手続きを行う(この方法が最も待ち時間が少なくなるやり方).この時,i番目の客の総待ち時間は,
clientArrivals[i]+(i/tellerCount+1)serviceTime
となる.i=[1,n]について調べ,最大値を返せば良い.

import java.lang.*;
import java.util.*;

public class OptimalQueues{
public int minWaitingTime(int[] clientArrivals, int tellerCount, int serviceTime){
for(int i=0;i<clientArrivals.length;i++) clientArrivals[i]*=-1;
Arrays.sort(clientArrivals);
for(int i=0;i<clientArrivals.length;i++) clientArrivals[i]*=-1;
int ret=0;
for(int i=0;i<clientArrivals.length;i++){
ret=Math.max(ret,clientArrivals[i]+(i/tellerCount+1)*serviceTime);
}
return ret;
}
}

TopCoder 練習 FibonacciPositioning(SRM298 Div1 Easy)

ニコ生にて,診断人さんがTopCoderの問題を解きまくっていたので,途中から便乗参加.

FibonacciPositioning(SRM298 Div1 Easy)

■問題
Fibonacci positionという値を定義する.n番目のFibonacci数をFn,Fibonacci positionをFPnとする時,FPnは以下の通り.

FP1=2
Fi=nの時,FPn=i
Fi<n<Fi+1の時,FP=i+(n-Fi)/(Fi+1-Fi)

FPnを求めよ.

■解法
問題の通り愚直に実装すればOK.

public class FibonacciPositioning{
public double getFPosition(int n){
if(n==1) return 2.0;
long a=1,b=1;
for(int i=1;;i++){
if(n==a)
return i;
if(a<n&&n<b)
return i+(double)(n-a)/(b-a);
a+=b;
long t=a; a=b; b=t;
}
}
}

2010年11月7日日曜日

Prologの技芸 8.3節の練習問題

(1)
% triangle(N,T) :-
% TはN番目の三角数である.
triangle(N,T) :- triangle(N,0,T).
triangle(N,Temp,T) :-
N<0, Temp1 is Temp+N, N1 is N-1, triangle(N1,Temp1,T).
triangle(0,T,T).

(2)
% power(X,N,V) :-
% VはXのN乗である.
power(X,N,V) :- power(X,N,1,V).
power(X,N,Temp,V) :-
N>0, Temp1 is Temp*X, N1 is N-1, power(X,N1,Temp1,V).
power(_,0,V,V).

(3)
% between(I,J,K) :-
% Kは,整数IとJの両端を含む区間内の整数である.
between(I,J,J) :- I=<J.
between(I,J,K) :-
I<J, J1 is J-1, between(I,J1,K).

(4)
% timeslist(IntegerList,Product) :-
% Productは整数のリストIntegerListの積である.
timeslist(Is,Pro) :- timeslist(Is,1,Pro).
timeslist([I|Is],Temp,Pro) :-
Temp1 is Temp*I, timeslist(Is,Temp1,Pro).
timeslist([],Pro,Pro).

(5)
% area(Chain,Area) :-
% Areaは,頂点のリストChainで囲まれた多角形の面積である.
% ただし,各頂点の座標は整数の対(X,Y)で表される.
area(XYs,Area) :- area(XYs,0,Area).
area([(X1,Y1),(X2,Y2)|XYs],Temp,Area) :-
Temp1 is Temp+(X1*Y2-Y1*X2)/2,
area([(X2,Y2)|XYs],Temp1,Area).
area([_],Area,Area).

(6)
% minimum(Xs,Min) :-
% Minは,整数のリストXsの要素の最小値である.
minimum([X|Xs],M) :- minimum(Xs,X,M).
minimum([X|Xs],Y,M) :- X=<Y, minimum(Xs,X,M).
minimum([X|Xs],Y,M) :- X >Y, minimum(Xs,Y,M).
minimum([],M,M).

(7)
% my_length(Xs,N) :-
% Nは,リストXsの長さである.
my_length(Xs,N) :- my_length(Xs,0,N).
my_length([_|Xs],Temp,N) :-
Temp1 is Temp+1, my_length(Xs,Temp1,N).
my_length([],N,N).

(8)
% range(M,N,Ns) :-
% Nsは,MとNを含む区間の整数のリストである.
range(M,N,Ns) :- range(M,N,[],Ns).
range(M,N,Xs,Ys) :-
M =< N, N1 is N-1, range(M,N1,[N|Xs],Ys).
range(M,N,Xs,Xs) :-
M > N.

Prologの技芸 8.2節の練習問題

(1)
% triangle(N,T) :-
% TはN番目の三角数である.
triangle(N,T) :-
N>0, N1 is N-1, triangle(N1,T1), T is T1+N.
triangle(0,0).

(2)
% power(X,N,V) :-
% VはXのN乗である.
power(X,N,V) :-
N>0, N1 is N-1, power(X,N1,V1), V is V1*X.
power(_,0,1).

Prologの技芸 7.5節の練習問題

(1)
% no_doubles(Xs,Ys) :-
% Ysは,リストXsから重複した要素を取り除いたリストである.
no_doubles(Xs,Ys) :- no_doubles(Xs,[],Ys).
no_doubles([X|Xs],Ys,Zs) :-
nonmember(X,Ys), no_doubles(Xs,[X|Ys],Zs).
no_doubles([X|Xs],Ys,Zs) :-
member(X,Ys), no_doubles(Xs,Ys,Zs).
no_doubles([],Xs,Xs).

Prologの技芸 7.3節の練習問題

(1)
sublist(Xs,AsXsBs) :-
append(As,XsBs,AsXsBs), append(Xs,Bs,XsBs).
% ゴールの順序を逆にすると,append(Xs,Bs,XsBs)が終わらない.
% sublist(Xs,[a,b,c])?を実行すると,
% append(Xs,Bs,XsBs)の引数は全て不完備リストになる.

(2)
% substitute(X,Y,L1,L2) :-
% L2はL1中に現れるすべてのXをYで置き換えた結果である.
substitute(X,Y,[],[]).
substitute(X,Y,[X|Xs],[Y|Ys]) :-
substitute(X,Y,Xs,Ys).
substitute(X,Y,[Z|Xs],[Z|Ys]) :-
X \= Z, substitute(X,Y,Xs,Ys).
ゴールの順序
%substitute(X,Y,[Z|Xs],[Z|Ys]) :-
X \= Z, substitute(X,Y,Xs,Ys).

%substitute(X,Y,[Z|Xs],[Z|Ys]) :-
substitute(X,Y,Xs,Ys), X \= Z.
とすると左方再帰になるため終わらなくなる.

Prologの技芸 7.2節の練習問題

(1)
prefix(Prefix,List)について
PrefixかListが完備なら停止する
suffix(Suffix,List)について
Listが完備なら停止する

(2)
sublist(Sub,List)について
Listが完備なら停止する

Prologの技芸 7.1節の練習問題

(1)
解の順序
issac,jacob,benjamin
規則の順序を入れ換えたときの解の順序
benjamin,jacob,issac

(2)
解の順序
jacob,terach,abraham,issac
規則の順序を入れ換えたときの解の順序
terach,abraham,issac,jacob

Prologの技芸 6.1節の練習問題

(1)
daughter(X,haran)?
father(haran,X) {X=lot}
male(lot)
true
father(haran,X) {X=milcah}
male(milcah)
fail
father(haran,X) {X=yiscah}
male(yiscah)
fail

(2)
sort([3,1,2],Xs)?
sort([1,2],Zs)
sort([2],Zs1)
sort([],Zs2) {Zs2=[]}
true
isnert(2,[],Zs1) {Zs1=[2]}
true
insert(1,[2],Zs) {Zs=[2,Ys]}
1>2
fail
insert(1,[2],Zs) {Zs=[1,2]}
1 =< 2
true
insert(3,[1,2],Xs) {Xs=[1,Ys]}
3 > 1
insert(3,[2],Ys) {Ys=[2,Ys1]}
3 > 2
insert(3,[],Ys1) {Ys1=[3]}
true

Prologの技芸 5.2節の練習問題

(1)
第1引数と第2引数,または第3引数が完備自然数であるゴール
からなる領域に対して停止する.

2010年11月6日土曜日

TopCoder 練習

TheCoffeeTimeDivOne(SRM 479 Div1 Easy)

■問題
コーヒーと紅茶を乗客に配るのにかかる時間を求める問題.

■解法
全ての乗客に対して調べ上げても44,777,777回のループですので時間的には余裕.
ある乗客にコーヒーor紅茶のどちらを配るか,を調べるには,binarySearchでは間に合わないので,boolean配列を作りました.意外にもメモリが足りました.

public class TheCoffeeTimeDivOne{
public long find(int n, int[] tea){
int max=44777777;
boolean[] f=new boolean[max+1];
for(int t:tea){
f[t]=true;
}
int t=0,c=0;
long ret=(long)n*4;
for(int i=n;i>=1;i--){
if(f[i]){
// tea
if(t==0){
ret+=47+i*2;
}
t=(t+1)%7;
}else{
if(c==0){
ret+=47+i*2;
}
c=(c+1)%7;
}
}
return ret;
}
}

2010年11月5日金曜日

TopCoder 練習

InternetSecurity(SRM 480 Div1 Easy)

■問題
幾つかのサイトのURLとそのサイトに含まれるキーワードと,危険なサイトであることを表すキーワード群が与えられる.どのサイトが危険であるかを判定せよ.

■解法
危険キーワードをリストに取っておく.
n個のサイトについて以下を調べる.
あるサイトが危険キーワードを含む場合,そのサイトを「危険である」とし,そのサイトが含むキーワードを危険キーワードリストに追加.
「危険である」サイトが見つからなくなるまでループ.

import java.lang.*;
import java.util.*;

public class InternetSecurity{
public String[] determineWebsite(String[] address, String[] keyword, String[] d, int threshold){
int n=address.length;
LinkedList<String> dangerous=new LinkedList<String>();
boolean[] flag=new boolean[n];
for(String s:d){
dangerous.add(s);
}
for(;;){
boolean f=false;
for(int i=0;i<n;i++){
if(flag[i]){
continue;
}
int c=0;
for(String s:keyword[i].split(" ")){
if(dangerous.contains(s)){
c++;
}
}
if(c>=threshold){
for(String s:keyword[i].split(" ")){
dangerous.add(s);
}
flag[i]=f=true;
}
}
if(!f){
break;
}
}
LinkedList<String> list=new LinkedList<String>();
for(int i=0;i<n;i++){
if(flag[i]){
list.addLast(address[i]);
}
}

return list.toArray(new String[0]);
}
}

2010年10月30日土曜日

TopCoder 練習

RabbitNumber(SRM 484 Div1 Easy)

■問題
S(x):=xの各桁の総和とする.S(x*x)=S(x)*S(x)となるxをRabbit Numberと呼ぶ.
low以上high以下の数の内,Rabbit Numberはいくつあるか.

■解法
chokudaiさんのニコ生を頼りに解く.
まず,小さい数について実験してみると,各桁は必ず3以下である事が分かる.これは,4*4=16から分かるように,4以上の数の次乗には繰り上がりが発生してしまうから.
よって,各桁が3以下である数について試せば良い.
入力の最大値は1,000,000,000であるが,上記の条件を満たすものは約260000個であり,候補が十分に絞れるので,あとは全探索すればよい.

public class RabbitNumber{
public int theCount(int low, int high){
int res=0;
for(int i=1;;i++){
long n=0;
long r=1;
for(int k=i;k!=0;k>>=2){
n+=(k&3)*r;
r*=10;
}
if(n<low)
continue;
if(n>high)
break;
if(S(n*n)==S(n)*S(n))
res++;
}
return res;
}

long S(long x){
long ret=0;
for(;x!=0;x/=10)
ret+=(x%10);
return ret;
}
}

TopCoder 練習

AfraidOfEven(Member SRM 485 Div1 Easy)

■問題
Sashaはある等差数列{ai}を黒板に書いた.偶数が嫌いなPashaは,数列上の各数aiを偶数でなくなるまで2で割り続け,biとした.Pashaによって書き換えられた数列{bi}から元の数列{ai}を求めよ.候補が複数存在する場合は,辞書式順に最も早いものを答えとせよ.

■解法
1. a0=b02m,a1=b12nと決定する.
2. 公差d=a1-a0が求まるので,ai>=2が実現可能かを調べる.具体的には,ai=a0+di=bi2kであるので,(a0+di)/biが2のべき乗となるかどうか.
3. 全候補の内,辞書式順に最も早いものを答えとする.

計算時間は,a0,a1それぞれの決定に高々32ループ,実現可能かを調べるのに{ai}の長さループなので余裕です.

■コード
import java.util.*;
import java.lang.*;
import java.math.*;

public class AfraidOfEven{
public int[] restoreProgression(int[] seq){
int[] ret=new int[seq.length];
int[] arr=new int[seq.length];
String s1=null;
for(long a0=seq[0];a0<=Integer.MAX_VALUE;a0*=2){
arr[0]=(int)a0;
for(long a1=seq[1];a1<=Integer.MAX_VALUE;a1*=2){
arr[1]=(int)a1;
long d=a1-a0;
long a=a1+d;
boolean f=true;
for(int i=2;i<seq.length;i++){
arr[i]=(int)a;
if(a<0) f=false;
if(a%seq[i]!=0) f=false;
long k=a/seq[i];
if((k&(k-1))!=0) f=false;
a+=d;
}
if(f){
String s2=Arrays.toString(arr);
if(s1==null||s2.length()<s1.length()||(s2.length()==s1.length()&&s2.compareTo(s1)<0)){
System.arraycopy(arr,0,ret,0,seq.length);
s1=s2;
}
}
}
}
return ret;
}
}

2010年10月27日水曜日

TopCoder 練習

OneRegister(SRM 486 Div1 Easy)

wataさんのコードを参考に,というかほぼ丸写ししています.

基本的には,(s,t)と(1,t)を算出して,辞書式順に早いものを返しているようです.
rec(s,t)が非常にすっきりしていて凄い.再帰で書くとTLEするかと思いましたが,余裕だったようです.

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

public class OneRegister{
public String getProgram(int s, int t){
String res=rec(1,t);
if(res!=null) res="/"+res;
res=min(res,rec(s,t));
if(res==null) return ":-(";
return res;
}
String rec(long s,long t){
if(s==t) return "";
if(s>t) return null;
String a=rec(s*2,t);
if(a!=null) a="+"+a;
String b=s==1?null:rec(s*s,t);
if(b!=null) b="*"+b;
return min(a,b);
}
String min(String s,String t){
if(s==null) return t;
if(t==null) return s;
if(s.length() if(s.length()>t.length()) return t;
if(s.compareTo(t)<=0) return s;
return t;
}
}

TopCoder SRM 486

SRM 482(10/27 0:00~2:00)

久し振りの参加+悪夢再び….

■OneRegister(DIV1 Easy)

□Problem
値を一つ格納できるレジスタがある.レジスタには,格納されている値の加減乗除を再代入できる.初めにsが格納されている時,0回以上の演算の結果,tに変更出来るか.出来る場合は,命令数が最小となるような命令列を返せ.

解法があまりにも適当だったので落ちました….

■Result
××× 0 -0
0.0p

■Rating
1463 -> 1399
1500への道は遠い….

JAPLJ Contest

japljさん主催のJAPLJ Contestに参加してきました.

今回は久し振りのプログラミングコンテストでしたので散々でした.

問題はImo Judgeより閲覧できます.
解説はjapljさんの以下の記事に譲ります.
JAPLJ Contest まとめと解説

■Result
Rank34 100 0 50 - - -

A問題だけどうにかこうにか出しました.Cは嘘解法な感じだったので,半分の点数しか得られませんでした.無念.

2010年10月4日月曜日

Maximum-Cup 2010

埼玉大学主催のプログラミングコンテストMaximum-Cupに参加して来ました.

Maximum-Cup 2010

問題はM-Judgeから閲覧できます.

■Problem A さいたまトラップ
幾つかのトラップがある.Sくんはトラップを除去する事にしたが,除去には決められた時間がかかる.更に,除去作業を1時間行うごとに10分間の休憩が必要である.Sくんは24時間未満に全てのトラップを除去出来るか.出来る場合は除去終了までの時間を求めよ.

サクサクッと実装したのですがWA.
ずいぶん後になって,1時間丁度で終わる場合の休憩時間の処理を間違えていたことに気付きました….

01:39 AC

■Problem D 北海道のレストラン
幾つかのレストランに社員がいる.勤続年数100年のオーナーは接客研修会を開くため,ある1つのレストランをその会場とし,社員全員をそこに集めたい.
社員一人一人の移動コストは(勤務先のレストランと会場のレストランとの距離)x(勤続年数)で定義される.
移動コストの総和が最も小さくなるのはどのレストランか.

距離はFloyd-Warshallで求められますし,どのレストランを選ぶかも全探索で可能そうでしたのでサクサクッと組みましたがWA.
□トラップその1…オーナーも含む
オーナーは店番号1である,勤続年数100年の社員として計算の考慮に入ればければなりませんでした.
□トラップその2…レストランiとレストランjの距離は複数与えられる
これはコンテスト終了まで気付きませんでした.

■Problem G Arithmetic Geometric Sequence
http://m-judge.maximum.vc/problem.cgi?pid=10174参照.

最初は無理ゲーだと思ったのですが,数列Qにおいて,ある数k以下となる項の個数n(k)は容易に求められることが分かりました.
具体的には,
n(k)=[k/1]+[k/m]+[k/m2]+[k/m3]+[k/m4]+…
ですので,m=0,1の時だけ注意して,n(k)=xとなるkを二分探索で求めれば完了です.

03:22 AC

結局解けたのは,AとGだけという散々な結果でした.
まだまだ詰めが甘く,実装力が高いとは言えない,ということを思い知らされたコンテストでした.

PKU Judge Online 3061 Subsequence

■3061 Subsequence

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p3061;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

int INF=1<<28;
double EPS=1e-9;

int n, s;
int[] a;

void run(){
for(int t=sc.nextInt(); t>0; t--){
n=sc.nextInt();
s=sc.nextInt();
a=new int[n];
for(int i=0; i<n; i++)
a[i]=sc.nextInt();
println(cal()+"");
}
}

int cal(){
int res=n+1;
int p=0, q=0, sum=0;

for(;;){
while(q<n&&sum<s)
sum+=a[q++];
if(sum<s)
break;
res=Math.min(res, q-p);
sum-=a[p++];
}
return res%(n+1);
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2456 Aggressive cows

■2456 Aggressive cows

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p2456;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

int INF=1<<28;
double EPS=1e-9;

int n, c;
int[] a;

void run(){
n=sc.nextInt();
c=sc.nextInt();
a=new int[n];
for(int i=0; i<n; i++)
a[i]=sc.nextInt();
Arrays.sort(a);

int low=0, up=INF;

for(int i=0; i<100; i++){
int mid=(low+up)/2;
if(C(mid))
low=mid;
else
up=mid;
}
println(""+low);
}

boolean C(int x){
int last=0;
for(int i=1; i<c; i++){
int next=last+1;
while(next<n&&a[next]-a[last]<x)
next++;
if(next==n)
return false;
last=next;
}
return true;
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3723 Conscription

■3723 Conscription

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p3723;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

int INF=1<<28;
double EPS=1e-9;

int[] p, rank;

void run(){
int t=Integer.parseInt(sc.next());
for(int k=0; k<t; k++){
int n=Integer.parseInt(sc.next());// girl
int m=Integer.parseInt(sc.next());// boy
int r=Integer.parseInt(sc.next());
E[] es=new E[r];
for(int i=0; i<r; i++){
int x=Integer.parseInt(sc.next());
int y=Integer.parseInt(sc.next())+n;
int d=Integer.parseInt(sc.next());
es[i]=new E(x, y, d);
}
Arrays.sort(es, new Comparator<E>(){
public int compare(E e1, E e2){
return e2.d-e1.d;
}
});

p=new int[n+m];
rank=new int[n+m];
for(int i=0; i<n+m; i++)
p[i]=i;
int sumD=0;
for(E e : es){
// println(e.d+"");
if(find(e.x)!=find(e.y)){
sumD+=e.d;
union(e.x, e.y);
}
}
int ans=10000*(n+m)-sumD;
println(""+ans);
}
}

void union(int x, int y){
x=find(x);
y=find(y);
if(rank[x]<rank[y]){
p[x]=y;
}else{
p[y]=x;
if(rank[x]==rank[y]){
rank[x]++;
}
}
}

int find(int x){
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}

class E{
int x, y;
int d;

E(int x, int y, int d){
this.x=x;
this.y=y;
this.d=d;
}
}
}

PKU Judge Online 1182 食物链

■1182 食物链

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p1182;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

int INF=1<<28;
double EPS=1e-9;

int[] p;
int[] rank;

void run(){
int n=Integer.parseInt(sc.next());
int k=Integer.parseInt(sc.next());
p=new int[3*n];
rank=new int[3*n];
for(int i=0; i<3*n; i++)
p[i]=i;
int ans=0;
for(int i=0; i<k; i++){
int d=Integer.parseInt(sc.next());
int x=Integer.parseInt(sc.next())-1;
int y=Integer.parseInt(sc.next())-1;
if(x<0||x>=n||y<0||y>=n){
ans++;
continue;
}
if(d==1){
// x=y
if(same(x, y+n)||same(x, y+2*n)){
ans++;
}else{
union(x, y);
union(x+n, y+n);
union(x+2*n, y+2*n);
}
}else if(d==2){
// x->y
// x=y+n
if(same(x, y)||same(x, y+2*n)){
ans++;
}else{
union(x, y+n);
union(x+n, y+2*n);
union(x+2*n, y);
}
}
}
println(""+ans);

}

boolean same(int x, int y){
return findSet(x)==findSet(y);
}

void union(int x, int y){
x=findSet(x);
y=findSet(y);
if(rank[x]<rank[y]){
p[x]=y;
}else{
p[y]=x;
if(rank[x]==rank[y])
rank[x]++;
}
}

int findSet(int x){
if(p[x]!=x)
p[x]=findSet(p[x]);
return p[x];
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2431 Expedition

■2431 Expedition

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p2431;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

int INF=1<<28;
double EPS=1e-9;

void run(){
int n=sc.nextInt();
Stop[] stops=new Stop[n+1];
for(int i=n-1; i>=0; i--){
stops[i]=new Stop();
stops[i].pos=sc.nextInt();
stops[i].fuel=sc.nextInt();
}
stops[n]=new Stop();
int l=sc.nextInt();
int p=sc.nextInt();
for(int i=0; i<=n; i++)
stops[i].pos=l-stops[i].pos;
Arrays.sort(stops, new Comparator<Stop>(){
public int compare(Stop p1, Stop p2){
return p1.pos-p2.pos;
}
});
int pos=0;
int ans=0;
PriorityQueue<Integer> q=new PriorityQueue<Integer>();
for(int i=0; i<=n; i++){
int d=stops[i].pos-pos;
while(p-d<0){
if(q.isEmpty()){
println("-1");
return;
}
p-=q.poll();
ans++;
}
p-=d;
pos=stops[i].pos;
q.offer(-stops[i].fuel);
}
println(""+ans);
}

class Stop{
int pos;
int fuel;
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3253 Fence Repair

■3253 Fence Repair

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p3253;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=1<<28;
final double EPS=1e-9;

void run(){
int n=sc.nextInt();
PriorityQueue<Long> queue=new PriorityQueue<Long>();
for(int i=0; i<n; i++)
queue.offer(sc.nextLong());
long ans=0;
for(; queue.size()>1;){
long k1=queue.poll();
long k2=queue.poll();
ans+=k1+k2;
queue.offer(k1+k2);
}
println(""+ans);
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3069 Saruman's Army

■3069 Saruman's Army

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p3069;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=1<<28;
final double EPS=1e-9;

void run(){
for(;;){

int r=sc.nextInt();
int n=sc.nextInt();

if(r==-1&&n==-1)
break;

int[] a=new int[n];
for(int i=0; i<n; i++)
a[i]=sc.nextInt();
Arrays.sort(a);

int ans=0;
for(int i=0; i<n;){
int s=a[i++];
while(i<n&&a[i]<=s+r)
i++;
int p=a[i-1];
while(i<n&&a[i]<=p+r)
i++;
ans++;
}
println(ans+"");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3617 Best Cow Line

■3617 Best Cow Line

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p3617;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=1<<28;
final double EPS=1e-9;

void run(){
int n=sc.nextInt();
char[] cs=new char[n];
for(int i=0; i<n; i++)
cs[i]=sc.next().charAt(0);
int l=0;
int r=n-1;
for(int k=1; k<=n; k++){
boolean left=false;
for(int i=0; l+i<=r-i; i++){
if(cs[l+i]<cs[r-i]){
left=true;
break;
}else if(cs[l+i]>cs[r-i]){
break;
}
}
if(left)
print(cs[l++]+"");
else
print(cs[r--]+"");
if(k%80==0)
println("");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2386 Lake Counting

■2386 Lake Counting

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
package p2386;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=1<<28;
final double EPS=1e-9;

int n, m;
int[][] a;
boolean[][] f;

void run(){
n=sc.nextInt();
m=sc.nextInt();
a=new int[n][m];
f=new boolean[n][m];
for(int j=0; j<n; j++){
String s=sc.next();
for(int i=0; i<m; i++){
a[j][i]=s.charAt(i)=='.'?0:1;
}
}
int ans=0;
for(int j=0; j<n; j++){
for(int i=0; i<m; i++){
if(a[j][i]==1&&!f[j][i]){
ans++;
visit(i, j);
}
}
}
println(ans+"");
}

void visit(int x, int y){
f[y][x]=true;
for(int j=-1; j<=1; j++){
int y2=y+j;
if(y2<0||y2>=n)
continue;
for(int i=-1; i<=1; i++){
int x2=x+i;
if(x2<0||x2>=m)
continue;
if(a[y2][x2]==1&&!f[y2][x2]){
visit(x2, y2);
}
}
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 1852 Ants

■1852 Ants

□Problem
プログラミングコンテストチャレンジブック参照.

□Solution
プログラミングコンテストチャレンジブック参照.

□Code
package p1852;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final double EPS=1e-9;

void run(){
for(int t=sc.nextInt(); t>0; t--){
int length=sc.nextInt();
int n=sc.nextInt();
int earlist=0, latest=0;
for(int i=0; i<n; i++){
int a=sc.nextInt();
int min=Math.min(a, length-a);
int max=Math.max(a, length-a);
earlist=max(earlist,min);
latest=max(latest,max);
}
println(earlist+" "+latest);
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

2010年10月2日土曜日

PKU Judge Online 3085 Quick Change

■3085 Quick Change

□Problem
¢25,¢10,¢5,¢1の硬貨がある.¢nを最も硬貨が少なくなるように表せ.

□Solution
典型的な動的計画法.
dp[i][n]をi-1までの硬貨を使って,¢nを表す最小枚数とすると,
dp[i+1][n]=min{dp[i][n], dp[i][n-centi+1]+1}
ここで,centiは硬貨のiの価値.
dp[i][n]はnに初期化しておく.

□Code
package p3085;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
int[] cents={25, 10, 5, 1};
int n=sc.nextInt();
for(int k=1; k<=n; k++){
int c=sc.nextInt();
int[] a=new int[c+1];
for(int i=0; i<=c; i++)
a[i]=i;
int[] b=new int[c+1];
for(int j=0; j<4; j++){
for(int i=cents[j]; i<=c; i++){
int s=i-cents[j];
if(a[s]+1<=a[i]){
a[i]=a[s]+1;
b[i]=j;
}
}
}
int[] count=new int[4];
for(;;){
count[b[c]]++;
c-=cents[b[c]];
if(c==0)
break;
}
println(k+" "+count[0]+" QUARTER(S), "+count[1]+" DIME(S), "
+count[2]+" NICKEL(S), "+count[3]+" PENNY(S)");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 1028 Web Navigation

■1028 Web Navigation

□Problem
ウェブブラウザのシミュレーションを行え.命令は以下のとおりである.
BACK: 前のページに戻る.
FORWARD: 次のページに進む.
VISIT: 指定されたURLにジャンプ.
QUIT: ブラウザを終了する.

□Solution
閲覧したページをリストに格納しておけばOK.

□Code
package p1028;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
LinkedList<String> backward=new LinkedList<String>();
LinkedList<String> forward=new LinkedList<String>();
String url="http://www.acm.org/";
for(;;){
String[] ss=sc.nextLine().split(" ");
String s=ss[0];
if(s.equals("VISIT")){
backward.addFirst(url);
forward.clear();
url=ss[1];
println(url);
}else if(s.equals("BACK")){
if(backward.size()==0)
println("Ignored");
else{
forward.addFirst(url);
url=backward.removeFirst();
println(url);
}
}else if(s.equals("FORWARD")){
if(forward.size()==0)
println("Ignored");
else{
backward.addFirst(url);
url=forward.removeFirst();
println(url);
}
}else if(s.equals("QUIT")){
break;
}
}
System.out.flush();
}

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

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

public static void main(String[] args){
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 1051 P,MTHBGWB

■1051 P,MTHBGWB

□Problem
省略.

□Solution
省略.

□Code
package p1051;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
HashMap<Character, String> map1=new HashMap<Character, String>();
map1.put('A', ".-");
map1.put('B', "-...");
map1.put('C', "-.-.");
map1.put('D', "-..");
map1.put('E', ".");
map1.put('F', "..-.");
map1.put('G', "--.");

map1.put('H', "....");
map1.put('I', "..");
map1.put('J', ".---");
map1.put('K', "-.-");
map1.put('L', ".-..");
map1.put('M', "--");
map1.put('N', "-.");

map1.put('O', "---");
map1.put('P', ".--.");
map1.put('Q', "--.-");
map1.put('R', ".-.");
map1.put('S', "...");
map1.put('T', "-");
map1.put('U', "..-");

map1.put('V', "...-");
map1.put('W', ".--");
map1.put('X', "-..-");
map1.put('Y', "-.--");
map1.put('Z', "--..");

map1.put('_', "..--");
map1.put(',', ".-.-");
map1.put('.', "---.");
map1.put('?', "----");

HashMap<String, Character> map2=new HashMap<String, Character>();
for(Entry<Character, String> entry : map1.entrySet())
map2.put(entry.getValue(), entry.getKey());

int n=sc.nextInt();
sc.nextLine();
for(int t=1; t<=n; t++){
String s=sc.nextLine();
int len=s.length();
String e="";
int[] a=new int[len];
for(int i=0; i<len; i++){
e+=map1.get(s.charAt(i));
a[i]=map1.get(s.charAt(i)).length();
}
String ans="";
int k=0;
for(int j=0; j<len; j++){
String key="";
for(int i=0; i<a[len-1-j]; i++)
key+=e.charAt(k++);
ans+=map2.get(key);
}
println(t+": "+ans);
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

2010年10月1日金曜日

PKU Judge Online 3173 Parkside's Triangle

■3173 Parkside's Triangle

□Problem
省略.

□Solution
省略.

□Code
package p3173;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
int n=sc.nextInt();
int s=sc.nextInt();
int[][] a=new int[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<=i; j++){
a[j][i]=s++;
if(s==10)
s=1;
}
}
for(int j=0; j<n; j++){
for(int i=0; i<j; i++)
print(" ");
for(int i=j; i<n; i++)
print(a[j][i]+(i==n-1?"":" "));
println("");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3100 Root of the Problem

■3100 Root of the Problem

□Problem
整数b,nが与えられる.anがbと最も近くなるような整数aを求めよ.

□Solution
a=elog(b)/n
なので,上式で近そうな値をとり,その周辺を探す.

□Code
package p3100;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(;;){
int b=sc.nextInt();
int n=sc.nextInt();
if(b==0&&n==0)
break;
int a=(int)Math.exp(Math.log(b)/n);
a--;
int ans=a;
double ansPowN=Math.pow(ans, n);
for(int i=a;; i++){
double iPowN=Math.pow(i, n);
if(Math.abs(b-iPowN)<Math.abs(b-ansPowN)){
ans=i;
ansPowN=iPowN;
}
if(iPowN>b){
break;
}
}
println(ans+"");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3176 Cow Bowling

■3176 Cow Bowling

□Problem
          7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

このようなピラミッドを上から底辺までたどっていく.たどって来た数字を全て足し合わせたた合計の最大値を求めよ.

□Solution
下からDPしていく.

□Code
package p3176;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
int n=sc.nextInt();
int[][] a=new int[n][n];
for(int j=0; j<n; j++)
for(int i=0; i<=j; i++)
a[j][i]=sc.nextInt();
for(int j=n-2; j>=0; j--)
for(int i=0; i<=j; i++)
a[j][i]+=Math.max(a[j+1][i], a[j+1][i+1]);
println(""+a[0][0]);
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3086 Triangular Sums

■3086 Triangular Sums

□Problem
省略.

□Solution
省略.

□Code
package p3086;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
int N=sc.nextInt();
for(int k=1; k<=N; k++){
int n=sc.nextInt();
int ans=0;
for(int i=1; i<=n; i++)
ans+=i*(i+1)*(i+2)/2;
println(k+" "+n+" "+ans);
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3077 Rounders

■3077 Rounders

□Problem
省略.

□Solution
省略.

□Code
package p3077;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(int n=sc.nextInt(); n>0; n--){
int m=sc.nextInt();
int ans=1;
for(; m/10!=0;){
if(m%10>=5)
m+=10;
m/=10;
ans*=10;
}
ans*=m;
println(ans+"");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3030 Nasty Hacks

■3030 Nasty Hacks

□Problem
省略.

□Solution
省略.

□Code
package p3030;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(int n=sc.nextInt(); n>0; n--){
int r=sc.nextInt();
int e=sc.nextInt();
int c=sc.nextInt();
e-=c;
if(e>r)
println("advertise");
else if(e<r)
println("do not advertise");
else
println("does not matter");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 3094 Quicksum

■3094 Quicksum

□Problem
省略.

□Solution
省略.

□Code
package p3094;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(;;){
String s=sc.nextLine();
if(s.equals("#"))
break;
int ans=0;
for(int i=0; i<s.length(); i++)
if(Character.isUpperCase(s.charAt(i)))
ans+=(i+1)*(s.charAt(i)-'A'+1);
println(ans+"");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2136 Vertical Histogram

■2136 Vertical Histogram

□Problem
省略.

□Solution
省略.

□Code
package p2136;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
int n='Z'-'A'+1;
int[] a=new int[n];

for(int i=0; i<4; i++)
for(char c : sc.nextLine().toCharArray())
if(Character.isUpperCase(c))
a[c-'A']++;

int max=0;
for(int e : a)
max=Math.max(max, e);

for(int j=max; j>0; j--){
int last=0;
for(int i=0; i<n; i++)
if(a[i]>=j)
last=i;
for(int i=0; i<=last; i++){
print(a[i]>=j?"*":" ");
print(i==last?"":" ");
}
println("");
}
for(char c='A'; c<='Z'; c++)
print(c+(c=='Z'?"":" "));
println("");
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2140 Herd Sums

■2140 Herd Sums

□Problem
自然数nを連続した自然数の和で表すには何通りのやり方があるか.
15の時は4通り.
15=1+2+3+4+5=4+5+6=7+8

□Solution
昔,考えた方法で解きました.同じようなことが書かれているページがあったので↓参照ということで.
http://www.bun-eido.co.jp/t_math/sjournal/sj28/sj282530.pdf

□Code
package p2140;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
int n=sc.nextInt();
n*=2;
int m=(int)Math.sqrt(n);
int ans=0;
for(int i=1; i<=m+1; i++){
if(n%i==0){
int d=i;
int e=n/i;
if(d>e)
break;
if((d+e)%2==1)
ans++;
}
}
println(ans+"");
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2070 Filling Out the Team

■2070 Filling Out the Team

□Problem
省略.

□Solution
省略.

□Code
package p2070;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
double[] speeds={4.5, 6.0, 5.0};
double[] weights={150, 300, 200};
double[] strengths={200, 500, 300};
String[] ss={"Wide Receiver", "Lineman", "Quarterback"};
for(;;){
double speed=sc.nextDouble();
double weight=sc.nextDouble();
double strength=sc.nextDouble();
if(speed==0&&weight==0&&strength==0)
break;
String ans="";
for(int i=0; i<3; i++){
if(speed<speeds[i]+EPS&&weight+EPS>weights[i]
&&strength+EPS>strengths[i])
ans+=ss[i]+" ";
}
if(ans.equals(""))
println("No positions");
else
println(ans.substring(0, ans.length()-1));
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2039 To and Fro

■2039 To and Fro

□Problem
省略.

□Solution
省略.

□Code
package p2039;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(;;){
int n=sc.nextInt();
if(n==0)
break;
String s=sc.next();
int m=s.length()/n;
for(int j=0; j<n; j++){
for(int i=0; i<m; i++){
int k=j+i*n;
if(i%2==1)
k+=n-1-2*j;
print(""+s.charAt(k));
}
}
println("");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2081 Recaman's Sequence

■2081 Recaman's Sequence

□Problem
Recaman数列とは,以下で定義される.
a0=0
am=am-1-m
(am>0かつ,an=amとなるn<mが存在しない時)
am=am-1+m
(それ以外の時)

akを求めよ.

□Solution
0≦k≦500000であるため,予めakを求めておく.

□Code
package p2081;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
int[] a=new int[500001];
HashSet<Integer> set=new HashSet<Integer>();
for(int m=1; m<500001; m++){
int a2=a[m-1]-m;
if(a2>0&&!set.contains(a2))
a[m]=a2;
else
a[m]=a[m-1]+m;
set.add(a[m]);
}
for(;;){
int k=sc.nextInt();
if(k==-1)
break;
println(a[k]+"");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2013 Symmetric Order

■2013 Symmetric Order

□Problem
省略.

□Solution
省略.

□Code
package p2013;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(int t=1;; t++){
int n=sc.nextInt();
if(n==0)
break;
String[] ss=new String[n];
for(int i=0; i<n; i++)
ss[i]=sc.next();
LinkedList<String> list=new LinkedList<String>();
for(int i=n-1; i>=0; i--)
if(i%2==0)
list.addFirst(ss[i]);
else
list.addLast(ss[i]);
println("SET "+t);
for(String s : list)
println(s);
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2017 Speed Limit

■2017 Speed Limit

□Problem
省略.

□Solution
省略.

□Code
package p2017;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(;;){
int n=sc.nextInt();
if(n==-1)
break;
int ph=0;
int tot=0;
for(int i=0; i<n; i++){
int v=sc.nextInt();
int h=sc.nextInt();
tot+=(h-ph)*v;
ph=h;
}
println(tot+" miles");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 2027 No Brainer

■2027 No Brainer

□Problem
省略.

□Solution
省略.

□Code
package p2027;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(int n=sc.nextInt(); n>0; n--){
int x=sc.nextInt();
int y=sc.nextInt();
println(x<y?"NO BRAINS":"MMM BRAINS");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 1936 All in All

■1936 All in All

□Problem
文字列s,tが与えられる.sがtの部分文字列なら"Yes",そうでなければ"No"を出力せよ.

□Solution
sとtの最長共通部分文字列がsの長さなら"Yes".

□Code
package p1936;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
for(; sc.hasNext();){
String s=sc.next();
String t=sc.next();
int m=s.length();
int n=t.length();
int[][] dp=new int[n+1][m+1];
for(int j=0; j<n; j++){
for(int i=0; i<m; i++){
if(s.charAt(i)==t.charAt(j))
dp[j+1][i+1]=dp[j][i]+1;
else
dp[j+1][i+1]=Math.max(dp[j+1][i], dp[j][i+1]);
}
}
println(dp[n][m]==m?"Yes":"No");
}
}

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

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

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 1256 Anagram

■1256 Anagram

□Problem
与えられた文字列を並び替えて,A<a<B<b<C<c<…という優先順位の元,辞書式順に出力せよ.但し,重複は省く.

□Solution
↑の優先順位でソートし,あとは1731と同じ.

□Code
package p1256;

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

// AC
public class Main{
Scanner sc=new Scanner(System.in);

char[] cs;
int[] order;
int n;

void recursive(int j){
if(j==n){
println(new String(cs));
return;
}
for(int i=j; i<n; i++){
// right rotate [j,i]
char c=cs[i];
int t=order[i];
for(int k=i; k%gt;j; k--){
cs[k]=cs[k-1];
order[k]=order[k-1];
}
cs[j]=c;
order[j]=t;
boolean f=true;
for(int k=j; k<=i; k++){
if(cs[j]==cs[k]&&order[j]%gt;order[k]){
f=false;
break;
}
}
if(f)
recursive(j+1);
// left rotate [j,i]
for(int k=j; k<i; k++){
cs[k]=cs[k+1];
order[k]=order[k+1];
}
cs[i]=c;
order[i]=t;
}
}

void run(){
for(int t=sc.nextInt(); t%gt;0; t--){
cs=sc.next().toCharArray();
n=cs.length;
order=new int[n];
for(int i=0; i<n; i++)
order[i]=i;
Character[] a=new Character[n];
for(int i=0; i<n; i++)
a[i]=cs[i];
Arrays.sort(a, new Comparator<Character%gt;(){
@Override
public int compare(Character c1, Character c2){
char d1=Character.toLowerCase(c1);
char d2=Character.toLowerCase(c2);
if(d1!=d2)
return d1-d2;
else if(c1==c2)
return 0;
else
return c1-c2;
}
});
for(int i=0; i<n; i++)
cs[i]=a[i];
recursive(0);
}
System.out.flush();
}

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

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

public static void main(String[] args){
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

PKU Judge Online 1731 Orders

■1731 Orders

□Problem
文字列sが与えられる.sの順列を辞書式順で生成せよ.但し,重複する文字列は省く.

□Solution
順列生成は再帰で.
重複を省くためには,以下.
まず,
s=c0c1…cn-1
に,
vk=kと数字を割り当てる.
再帰で順列を生成し,
s'=ca0ca1…can-1
となったとする.
cai=caj (i<j)
となるi,jがあった時,
vi<vj
であれば,その順列を出力し,そうでない場合は出力しない.
実際には,この判定を再帰の途中で行い,枝刈りをしている.

出力が遅かったため(TLEした),
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
として,最後にまとめてストリームをフラッシュ.

□Code
package p1731;

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

// AC
public class Main{
Scanner sc=new Scanner(System.in);

char[] cs;
int[] order;
int n;

void recursive(int j){
if(j==n){
println(new String(cs));
return;
}
for(int i=j; i<n; i++){
// right rotate [j,i]
char c=cs[i];
int t=order[i];
for(int k=i; k>j; k--){
cs[k]=cs[k-1];
order[k]=order[k-1];
}
cs[j]=c;
order[j]=t;
boolean f=true;
for(int k=j; k<=i; k++){
if(cs[j]==cs[k]&&order[j]>order[k]){
f=false;
break;
}
}
if(f)
recursive(j+1);
// left rotate [j,i]
for(int k=j; k<i; k++){
cs[k]=cs[k+1];
order[k]=order[k+1];
}
cs[i]=c;
order[i]=t;
}
}

void run(){
cs=sc.next().toCharArray();
n=cs.length;
order=new int[n];
for(int i=0; i<n; i++)
order[i]=i;
Arrays.sort(cs);
recursive(0);
System.out.flush();
}

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

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

public static void main(String[] args){
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

2010年9月27日月曜日

TopCoder SRM 483

SRM 483(9/26 1:00~3:00)

今回は,Easyを出来るだけ正確かつ早く解く事を目標としました.

■BestApproximationDiv1(Div1 Easy)

□問題
"0.dddddd"という形の小数numberが与えられる.分母がmaxDen以下の分数d/nとnumberを比較し,小数点以下何桁目まで一致しているかを数える.一致桁数が最も大きい分数を求めよ.但し,答えが複数存在する場合には,分母が小さいものを,分母が等しい場合は,分子の小さいものを出力せよ.

□解法
全探索するとO(maxDen2)となりますが,1≦maxDen≦1000ですので問題ありませんでした.

□コード
import java.util.*;
import java.lang.*;

public class BestApproximationDiv1{
public String findFraction(int maxDen, String number){
int bestD=1, bestN=0;
int maxDigit=0;
for(int d=maxDen;d>=1;d--){
for(int n=d-1;n>=0;n--){
String s=((double)n/d)+"";
if(s.length()==1)
s+=".";
s+="000000";
int digit=1;
for(int i=2;i<number.length()&&i<s.length();i++){
if(number.charAt(i)!=s.charAt(i))
break;
digit++;
}
if(digit>=maxDigit){
bestD=d;
bestN=n;
maxDigit=digit;
}
}
}
return bestN+"/"+bestD+" has "+maxDigit+" exact digits";
}
}


■Challenge
他の人達の回答が結構長くて,読めませんでした.

■Result
○×× 0 -0
190.00p

今回は,HardがMediumよりも簡単という噂が聞こえてきて,Hardを解かなかった事を後悔していましたが,意外や意外,実は難しい問題だったようで,多くの人がSystem Testで落とされていました.

■Rating
1372 -> 1463

結構上がりました.4回連続Rating上昇です.目標のYellowCoderまであと少し….

2010年9月25日土曜日

Codeforces Beta Round #30

Codeforces Beta Round #30 9/25(0:00~2:00)

1週間振り.

■A. Accounting
□問題
3つの整数A,B,n(|A|,|B|≦1000, 1≦n≦10)が与えられる.
AXn=Bとなる整数Xが存在するか判定し,存在する場合はその内の1つの解を求めよ.

□解法
場合分けをきっちりやればOK.

□コード
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
Scanner sc=new Scanner(System.in);

void run(){
int a=sc.nextInt();
int b=sc.nextInt();
int n=sc.nextInt();
if(a*b>0){
a=Math.abs(a);
b=Math.abs(b);
for(int x=1;; x++){
int c=a*(int)Math.pow(x, n);
if(c==b){
println(""+x);
break;
}else if(c>b){
println("No solution");
break;
}
}
}else if(a*b<0){
if(n%2==0){
println("No solution");
return;
}
a=Math.abs(a);
b=Math.abs(b);
for(int x=1;; x++){
int c=a*(int)Math.pow(x, n);
if(c==b){
println("-"+x);
break;
}else if(c>b){
println("No solution");
break;
}
}
}else{
if(a==0&&b==0){
println("1");
}else if(a==0){
println("No solution");
}else{
println("0");
}
}
}

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

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

public static void main(String[] args){
new A().run();
}
}


■B. Codeforces World Finals
□問題
Bobの生年月日(BD.BM.BY)とコンテストの開催年月日(DD.MM.YY)が与えられる.コンテストの開催年月日にはBobが18才以上となっているようにBobの生年月日を並び替える(BD,BM,BYをそれぞれ並び替える)ことは出来るか.

□解法
6通り全ての並び替えに対し,それが生年月日であるか+18才以上になるかという条件チェックをちゃんとやったつもりでしたが,堕ちました.

□コード
自主規制

■C. Shooting Gallery
□問題
n個のターゲットがある.ターゲットiはそれぞれ座標(xi, yi),出現時刻ti,命中率piを持つ.プレイヤーは,任意の位置からスタートできるが,座標ciからcjへ移動するのには,|cj-ci|だけの時間がかかる.最適な行動をとった時,ターゲットの破壊個数の期待値は最大いくらになるか.

□解法
まず,tiでソートします.ターゲットiを破壊し最適な行動をとった時の最大期待値Eiは,
Ei=pi+MAXj(tj-ti≧|cj-ci|)Ej
となります.
ですので,tiが大きいものからEiを求めていき,全て求め終わった後,最も大きいEiが答えとなります.

□コード
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class C{
Scanner sc=new Scanner(System.in);

int n;
R[] rs;

double EPS=1e-6;

void run(){
n=sc.nextInt();
rs=new R[n];
for(int i=0; i<n; i++){
R r=new R();
r.x=sc.nextInt();
r.y=sc.nextInt();
r.t=sc.nextInt();
r.p=sc.nextDouble();
rs[i]=r;
}
Arrays.sort(rs, new Comparator<R>(){
@Override
public int compare(R r1, R r2){
return r2.t-r1.t;
}
});
for(int j=0; j<n; j++){
R r=rs[j];
r.E+=r.p;
for(int i=j+1; i<n; i++){
R s=rs[i];
double d=Math.sqrt((r.x-s.x)*(r.x-s.x)+(r.y-s.y)*(r.y-s.y));
if(d<r.t-s.t+EPS){
s.E=Math.max(s.E, r.E);
}
}
}
double ans=0;
for(R r : rs){
ans=Math.max(ans, r.E);
}
println(""+ans);
}

class R{
int x, y, t;
double p;
double E;
}

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

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

public static void main(String[] args){
new C().run();
}
}


■Result
○×○××
1636p
151位

■Rating
1759 -> 1709

さらにRatingダウン.Bを落としたのが痛かった….