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]);
}
}