2010年11月20日土曜日

TopCoder 練習 SumsOfPerfectPowers(SRM 350 Div1 Easy)

SumsOfPerfectPowers(SRM 350 Div1 Easy)

■問題
本家参照．

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

view plainprint?
  1. import java.util.*;  
  2.   
  3. public class SumsOfPerfectPowers{  
  4.  public int howMany(int lowerBound, int upperBound){  
  5.   boolean[] dp=new boolean[upperBound+1];  
  6.   TreeSet<Integer> set=new TreeSet<Integer>();  
  7.   set.add(0);  
  8.   set.add(1);  
  9.   for(int a=2;a*a<=upperBound;a++){  
  10.    for(long r=a*a;r<=upperBound;r*=a){  
  11.     set.add((int)r);  
  12.    }  
  13.   }  
  14.   for(int a:set){  
  15.    for(int b:set){  
  16.     if(a+b<=upperBound){  
  17.      dp[a+b]=true;  
  18.     }  
  19.    }  
  20.   }  
  21.   int ret=0;  
  22.   for(int i=lowerBound;i<=upperBound;i++){  
  23.    if(dp[i]){  
  24.     ret++;  
  25.    }  
  26.   }  
  27.   return ret;  
  28.  }  
  29. }  
投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder 練習 KnightsTour(SRM 447 Div1 Easy)

KnightsTour(SRM 447 Div1 Easy)

■問題
本家参照．

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

view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3.   
  4. public class KnightsTour{  
  5.  int[] dx={1,-1,2,-2,2,-2,1,-1};  
  6.  int[] dy={2,2,1,1,-1,-1,-2,-2};  
  7.  public int visitedPositions(String[] ss){  
  8.   boolean[][] visited=new boolean[8][8];  
  9.   int x=0,y=0;  
  10.   for(int j=0;j<8;j++){  
  11.    for(int i=0;i<8;i++){  
  12.     if(ss[j].charAt(i)=='K'){  
  13.      x=i;  
  14.      y=j;  
  15.     }  
  16.    }  
  17.   }  
  18.   visited[y][x]=true;  
  19.   int[] num=new int[8];  
  20.   for(int c=1;;c++){  
  21.    Arrays.fill(num,9);  
  22.    for(int j=0;j<8;j++){  
  23.     int nx=x+dx[j];  
  24.     int ny=y+dy[j];  
  25.     if(nx<0||nx>=8||ny<0||ny>=8||visited[ny][nx]||ss[ny].charAt(nx)=='*'){  
  26.      continue;  
  27.     }  
  28.     num[j]=0;  
  29.     visited[ny][nx]=true;  
  30.     for(int i=0;i<8;i++){   
  31.      int nnx=nx+dx[i];  
  32.      int nny=ny+dy[i];  
  33.      if(nnx<0||nnx>=8||nny<0||nny>=8||visited[nny][nnx]||ss[nny].charAt(nnx)=='*'){  
  34.       continue;  
  35.      }  
  36.      num[j]++;  
  37.     }  
  38.     visited[ny][nx]=false;  
  39.    }  
  40.    int k=0;  
  41.    for(int i=0;i<8;i++){  
  42.     if(num[i]<=num[k]){  
  43.      k=i;  
  44.     }  
  45.    }  
  46.    if(num[k]>8){  
  47.     return c;  
  48.    }  
  49.    x+=dx[k];  
  50.    y+=dy[k];  
  51.    visited[y][x]=true;  
  52.    // System.out.println(x+","+y);  
  53.    // System.out.println("num["+k+"]="+num[k]);  
  54.   }  
  55.  }  
  56. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2010年11月14日日曜日

TopCoder 練習 CandidateKeys(SRM 386 Div1 Easy)

CandidateKeys(SRM 386 Div1 Easy)

■問題
本家参照．

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

view plainprint?
  1. public class CandidateKeys{  
  2.  int n, m;  
  3.  String[] table;  
  4.  public int[] getKeys(String[] table){  
  5.   n=table.length;  
  6.   m=table[0].length();  
  7.   this.table=table;  
  8.   boolean[] candidate=new boolean[1<<m];  
  9.   int min=-1, max=0;  
  10.   for(int sup=0;sup<1<<m;sup++){  
  11.    if(isSuperKey(sup)){  
  12.     boolean f=true;  
  13.     for(int sub=(sup-1)&sup;sub!=0;sub=(sub-1)&sup){  
  14.      f&=!candidate[sub];  
  15.     }  
  16.     candidate[sup]=f;  
  17.     if(f){  
  18.      int bit=Integer.bitCount(sup);  
  19.      if(min==-1||bit<min){  
  20.       min=bit;  
  21.      }  
  22.      if(bit>max){  
  23.       max=bit;  
  24.      }  
  25.     }  
  26.    }  
  27.    // System.out.println(Integer.toString(sup,2)+":"+isSuperKey(sup)+":"+candidate[sup]);  
  28.   }  
  29.   if(min==-1){  
  30.    return new int[0];  
  31.   }  
  32.   else{  
  33.    return new int[]{min, max};  
  34.   }  
  35.  }  
  36.    
  37.  boolean isSuperKey(int sup){  
  38.   if(sup==0) return false;  
  39.   String[] ss=new String[n];  
  40.   for(int j=0;j<n;j++){  
  41.    int s=sup;  
  42.    ss[j]="";  
  43.    for(int i=m-1;i>=0;i--){  
  44.     if((s&1)==1){  
  45.      ss[j]=table[j].charAt(i)+ss[j];  
  46.     }  
  47.     s>>=1;  
  48.    }  
  49.   }  
  50.   for(int j=0;j<n;j++){  
  51.    for(int i=j+1;i<n;i++){  
  52.     if(ss[i].equals(ss[j])){  
  53.      return false;  
  54.     }  
  55.    }  
  56.   }  
  57.   return true;  
  58.  }  
  59. }  
投稿者 時刻: 0 件のコメント:
ラベル:

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がそれ程大きくないので，素数全列挙で大丈夫でした．

view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3.   
  4. public class PrimeSequences{  
  5.  public int getLargestGenerator(int N, int D){  
  6.   int max=10000000;  
  7.   boolean[] ps=new boolean[max+1];  
  8.   Arrays.fill(ps,true);  
  9.   ps[0]=ps[1]=false;  
  10.   for(int i=2;i<=10000000;i++){  
  11.    if(ps[i]){  
  12.     for(int j=2;i*j<=10000000;j++){  
  13.      ps[i*j]=false;  
  14.     }  
  15.    }  
  16.   }  
  17.   int[] a=new int[max+1];  
  18.   for(int i=2;i<=max;i++){  
  19.    //System.out.println(i+":"+ps[i]);  
  20.    if(ps[i]&&a[i]==0){  
  21.     int k=1;  
  22.     for(int j=i;j<=max&&ps[j];j=j*2+1){  
  23.      a[j]=k++;  
  24.     }  
  25.    }  
  26.   }  
  27.   int ret=-1;  
  28.   for(int i=0;i<=N;i++){  
  29.    //System.out.println(i+":"+a[i]);  
  30.    if(a[i]>=D){  
  31.     ret=i;  
  32.    }  
  33.   }  
  34.   return ret;  
  35.  }  
  36. }  
投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder 練習 SequenceOfCommands(SRM 473 Div1 Easy)

SequenceOfCommands(SRM 473 Div1 Easy)

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

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

view plainprint?
  1. public class SequenceOfCommands{  
  2.  public String whatHappens(String[] commands){  
  3.   String ss="";  
  4.   for(String s:commands){  
  5.    ss+=s;  
  6.   }  
  7.   ss=ss+ss+ss+ss;  
  8.   int x=0,y=0,d=0;  
  9.   int[] dx={1,0,-1,0};  
  10.   int[] dy={0,1,0,-1};  
  11.   for(char c:ss.toCharArray()){  
  12.    if(c=='S'){  
  13.     x+=dx[d];  
  14.     y+=dy[d];  
  15.    }  
  16.    else if(c=='L'){  
  17.     d=(d+3)%4;  
  18.    }  
  19.    else{  
  20.     d=(d+1)%4;  
  21.    }  
  22.   }  
  23.   return x==0&&y==0?"bounded":"unbounded";  
  24.  }  
  25. }  
投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder 練習 Islands(SRM 477 Div1 Easy)

Islands(SRM 477 Div1 Easy)

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

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

view plainprint?
  1. public class Islands{  
  2.  public int beachLength(String[] str){  
  3.   int ret=0;  
  4.   // j:even (i+1,j), (i,j+1), (i-1,j+1)  
  5.   // j:odd (i+1,j), (i+1,j+1), (i,j+1)  
  6.   int n=str.length;  
  7.   int m=str[0].length();  
  8.   for(int j=0;j<n;j++){  
  9.    for(int i=0;i<m;i++){  
  10.     int[] dx, dy;  
  11.     if(j%2==0){  
  12.      dx=new int[]{1,0,-1};  
  13.      dy=new int[]{0,1,1};  
  14.     }else{  
  15.      dx=new int[]{1,1,0};  
  16.      dy=new int[]{0,1,1};  
  17.     }  
  18.     for(int d=0;d<3;d++){  
  19.      int x=i+dx[d];  
  20.      int y=j+dy[d];  
  21.      if(0<=x&x<m&&0<=y&&y<n&&str[j].charAt(i)!=str[y].charAt(x)){  
  22.       ret++;  
  23.      }  
  24.     }  
  25.    }  
  26.   }  
  27.   return ret;  
  28.  }  
  29. }  
投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder SRM 487

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

悪夢再び…．

■BunnyComputer(Div1 Easy)

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

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

wataさんのコードを参考にしたコードはこちら．
view plainprint?
  1. public class BunnyComputer{  
  2.  public int getMaximum(int[] pre, int k){  
  3.   int n=pre.length;  
  4.   int res=0;  
  5.   for(int j=0;j<k+1;j++){  
  6.    int dp1=0, dp2=0;  
  7.    for(int i=j;i+k+1<n;i+=k+1){  
  8.     int a1=Math.max(dp1,dp2);  
  9.     int a2=dp1+pre[i]+pre[i+k+1];  
  10.     dp1=a1;  
  11.     dp2=a2;  
  12.    }  
  13.    res+=Math.max(dp1,dp2);  
  14.   }  
  15.   return res;  
  16.  }  
  17. }  

仮に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連続減少．実に良くないですねえ．
投稿者 時刻: 0 件のコメント:
ラベル:

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．

view plainprint?
  1. import java.lang.*;  
  2. import java.util.*;  
  3.   
  4. public class Badgers{  
  5.  public int feedMost(int[] hunger, int[] greed, int totalFood){  
  6.   int n=hunger.length;  
  7.   int ret=0;  
  8.   int[] a=new int[n];  
  9.   for(int i=1;i<=n;i++){  
  10.    for(int k=0;k<n;k++){  
  11.     a[k]=hunger[k]+(i-1)*greed[k];  
  12.    }  
  13.    Arrays.sort(a);  
  14.    //System.out.println(i+":"+Arrays.toString(a));  
  15.    int tot=0;  
  16.    for(int k=0;k<i;k++){  
  17.     tot+=a[k];  
  18.    }  
  19.    //System.out.println("tot:"+tot);  
  20.    if(tot<=totalFood){  
  21.     ret=i;  
  22.    }  
  23.   }  
  24.   return ret;  
  25.  }  
  26. }  
投稿者 時刻: 0 件のコメント:
ラベル:

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を求めれば良い．

view plainprint?
  1. public class BuildBridge{  
  2.  public int howManyCards(int d, int l){  
  3.   double dd=(double)d/l;  
  4.   double tot=0;  
  5.   for(int i=1;;i++){  
  6.    tot+=0.5/i;  
  7.    if(tot+1e-9>dd) return i;  
  8.   }  
  9.  }  
  10. }  


EPS=1e-9としましたが，もう少し小さい(1e-11位)方が安全だと思いました．
投稿者 時刻: 0 件のコメント:
ラベル:

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する．

view plainprint?
  1. public class NewAlbum{  
  2.  public int leastAmountOfCDs(int nSongs, int length, int cdCapacity){  
  3.   long oneCd=1;  
  4.   for(;(oneCd+1)*length+(oneCd)<=cdCapacity;oneCd++)  
  5.    ;  
  6.   if(oneCd%13==0) oneCd--;  
  7.   long left=0, right=1000000;  
  8.   for(int i=0;i<100;i++){  
  9.    long mid=(left+right)/2;  
  10.    if(nSongs<=oneCd*mid)  
  11.     right=mid;  
  12.    else  
  13.     left=mid;  
  14.   }  
  15.   int ret=(int)right;  
  16.   if(nSongs%ret==0&(nSongs/ret)%13==0)  
  17.    ret++;  
  18.   if((nSongs%oneCd)%13==0&&oneCd*ret==nSongs+1)  
  19.    ret++;  
  20.   return ret;  
  21.  }  
  22. }  
投稿者 時刻: 0 件のコメント:
ラベル:

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]について調べ，最大値を返せば良い．

view plainprint?
  1. import java.lang.*;  
  2. import java.util.*;  
  3.   
  4. public class OptimalQueues{  
  5.  public int minWaitingTime(int[] clientArrivals, int tellerCount, int serviceTime){  
  6.   for(int i=0;i<clientArrivals.length;i++) clientArrivals[i]*=-1;  
  7.   Arrays.sort(clientArrivals);  
  8.   for(int i=0;i<clientArrivals.length;i++) clientArrivals[i]*=-1;  
  9.   int ret=0;  
  10.   for(int i=0;i<clientArrivals.length;i++){  
  11.    ret=Math.max(ret,clientArrivals[i]+(i/tellerCount+1)*serviceTime);  
  12.   }  
  13.   return ret;  
  14.  }  
  15. }  
投稿者 時刻: 0 件のコメント:
ラベル:

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．

view plainprint?
  1. public class FibonacciPositioning{  
  2.  public double getFPosition(int n){  
  3.   if(n==1) return 2.0;  
  4.   long a=1,b=1;  
  5.   for(int i=1;;i++){  
  6.    if(n==a)  
  7.     return i;  
  8.    if(a<n&&n<b)  
  9.     return i+(double)(n-a)/(b-a);  
  10.    a+=b;  
  11.    long t=a; a=b; b=t;  
  12.   }  
  13.  }  
  14. }  
投稿者 時刻: 0 件のコメント:
ラベル:

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.
投稿者 時刻: 0 件のコメント:
ラベル: ,

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).
投稿者 時刻: 0 件のコメント:
ラベル: ,

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).
投稿者 時刻: 0 件のコメント:
ラベル: ,

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.
とすると左方再帰になるため終わらなくなる．
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 7.2節の練習問題

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

(2)
sublist(Sub,List)について
Listが完備なら停止する
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 7.1節の練習問題

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

(2)
解の順序
jacob,terach,abraham,issac
規則の順序を入れ換えたときの解の順序
terach,abraham,issac,jacob
投稿者 時刻: 0 件のコメント:
ラベル: ,

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
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 5.2節の練習問題

(1)
第1引数と第2引数，または第3引数が完備自然数であるゴール
からなる領域に対して停止する．
投稿者 時刻: 0 件のコメント:
ラベル: ,

2010年11月6日土曜日

TopCoder 練習

TheCoffeeTimeDivOne(SRM 479 Div1 Easy)

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

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

view plainprint?
  1. public class TheCoffeeTimeDivOne{  
  2.  public long find(int n, int[] tea){  
  3.   int max=44777777;  
  4.   boolean[] f=new boolean[max+1];  
  5.   for(int t:tea){  
  6.    f[t]=true;  
  7.   }  
  8.   int t=0,c=0;  
  9.   long ret=(long)n*4;  
  10.   for(int i=n;i>=1;i--){  
  11.    if(f[i]){  
  12.     // tea  
  13.     if(t==0){  
  14.      ret+=47+i*2;  
  15.     }  
  16.     t=(t+1)%7;  
  17.    }else{  
  18.     if(c==0){  
  19.      ret+=47+i*2;  
  20.     }  
  21.     c=(c+1)%7;  
  22.    }  
  23.   }  
  24.   return ret;  
  25.  }  
  26. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2010年11月5日金曜日

TopCoder 練習

InternetSecurity(SRM 480 Div1 Easy)

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

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

view plainprint?
  1. import java.lang.*;  
  2. import java.util.*;  
  3.   
  4. public class InternetSecurity{  
  5.  public String[] determineWebsite(String[] address, String[] keyword, String[] d, int threshold){  
  6.   int n=address.length;  
  7.   LinkedList<String> dangerous=new LinkedList<String>();  
  8.   boolean[] flag=new boolean[n];  
  9.   for(String s:d){  
  10.    dangerous.add(s);  
  11.   }  
  12.   for(;;){  
  13.    boolean f=false;  
  14.    for(int i=0;i<n;i++){  
  15.     if(flag[i]){  
  16.      continue;  
  17.     }  
  18.     int c=0;  
  19.     for(String s:keyword[i].split(" ")){  
  20.      if(dangerous.contains(s)){  
  21.       c++;  
  22.      }  
  23.     }  
  24.     if(c>=threshold){  
  25.      for(String s:keyword[i].split(" ")){  
  26.       dangerous.add(s);  
  27.      }  
  28.      flag[i]=f=true;  
  29.     }  
  30.    }  
  31.    if(!f){  
  32.     break;  
  33.    }  
  34.   }  
  35.   LinkedList<String> list=new LinkedList<String>();  
  36.   for(int i=0;i<n;i++){  
  37.    if(flag[i]){  
  38.     list.addLast(address[i]);  
  39.    }  
  40.   }  
  41.   
  42.   return list.toArray(new String[0]);  
  43.  }  
  44. }  
投稿者 時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)