Project Euler

problem 71
problem 79

専門書を買う

Prologの技芸

Codeforces Beta Round #26

Codeforces Beta Round #26 8/17(0:00~2:00)

今回は，TopCoderっぽいルール．
1.問題を解き．コードを提出．
2.Pretestsに通ったら，一先ず得点がもらえる．
3.そのコードに自信があったら"ロック"する．一度ロックしたら，コードを修正する事は出来ないし，ロックを解除する事も出来ない．
4.ロックした問題については，他の人のコードを見ることが出来る．
5.間違ってそうなコードがあったら，バグを誘発する入力を与える．撃墜できたら+100，ミスしたら-50．
これが競技中ずっと行われます．競技終了後，システムテストが行われます．
前回このルールで参加した時は，撃墜祭りでしたが，今回はそれ程でもありませんでした．

■A. Almost Prime
□問題
素因数が2種類の数をAlmost Primeという．n以下のAlmost Primeの個数を答えよ．
□解法
やるだけ．
□コード

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 n=sc.nextInt();
  int[] cnt=new int[3001];
  for(int i=2; i<=3000; i++){
   cnt[i]+=cnt[i-1]+(isAP(i)?1:0);
  }
  println(""+cnt[n]);
 }

 boolean isAP(int n){
  int d=-1, e=-1;
  int m=n;
  for(int i=2; i<n; i++){
   if(m%i==0){
    if(e!=-1){
     return false;
    }else if(d!=-1){
     e=i;
    }else{
     d=i;
    }
    while(m%i==0)
     m/=i;
   }
  }
  return e!=-1;
 }

 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. Regular Bracket Sequence
□問題
(()))()(()(のような括弧列から，矛盾が無くなる様に括弧を取り除いた時，最大で何括弧残るか．
↑の場合(())()()となり答えは8．
□解法
左括弧が来たらカウンタ++，右括弧が来たらカウンタ--．カウンタが負になったらその分左括弧を取り除き，最終的にカウンタが正になったらその分右括弧を取り除く．
□コード

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

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

 void run(){
  char[]cs =sc.nextLine().toCharArray();
  int cnt=0;
  int stack=0;
  for(char c:cs){
   if(c=='(')
    stack++;
   else{
    if(stack==0)
     cnt++;
    else
     stack--;
   }
  }
  cnt+=stack;
  int length=cs.length-cnt;
  println(""+length);
 }

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

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

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

■C. Parquet
□問題
mxnの領域に1x2，2x1，2x2のタイルを敷き詰める問題．
□解法
m，nで場合わけして敷き詰めるだけ．実装ゲー．
□コード(適当でごめんなさい)

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, m, a, b, c;
 char[][] map;

 void run(){
  n=sc.nextInt();
  m=sc.nextInt();
  a=sc.nextInt();
  b=sc.nextInt();
  c=sc.nextInt();
  map=new char[n][m];
  if((m*n)%2!=0){
   println("IMPOSSIBLE");
   return;
  }
  if(n%2==0&&m%2==0){
   for(int j=0; j<n; j+=2){
    for(int i=0; i<m; i+=2){
     if(c>0){
      c--;
      char s=getDifferent(new int[]{i, i+1, i, i+1},
        new int[]{j, j, j+1, j+1});
      map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
     }else if(a>=2){
      char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
      map[j][i]=map[j][i+1]=s;
      char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
      map[j+1][i]=map[j+1][i+1]=t;
      a-=2;
     }else if(b>=2){
      char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
      map[j][i]=map[j+1][i]=s;
      char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
      map[j][i+1]=map[j+1][i+1]=t;
      b-=2;
     }else{
      println("IMPOSSIBLE");
      return;
     }
    }
   }
  }
  if(m%2==1){
   for(int j=0; j<n; j+=2){
    for(int i=0; i<m-1; i+=2){
     if(c>0){
      c--;
      char s=getDifferent(new int[]{i, i+1, i, i+1},
        new int[]{j, j, j+1, j+1});
      map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
     }else if(a>=2){
      char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
      map[j][i]=map[j][i+1]=s;
      char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
      map[j+1][i]=map[j+1][i+1]=t;
      a-=2;
     }else if(b>=2){
      char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
      map[j][i]=map[j+1][i]=s;
      char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
      map[j][i+1]=map[j+1][i+1]=t;
      b-=2;
     }else{
      println("IMPOSSIBLE");
      return;
     }
    }
   }
   for(int j=0; j<n; j+=2){
    if(b>0){
     char s=getDifferent(new int[]{m-1, m-1}, new int[]{j, j+1});
     map[j][m-1]=map[j+1][m-1]=s;
     b--;
    }else{
     println("IMPOSSIBLE");
     return;
    }
   }
  }
  if(n%2==1){
   for(int j=0; j<n-1; j+=2){
    for(int i=0; i<m; i+=2){
     if(c>0){
      c--;
      char s=getDifferent(new int[]{i, i+1, i, i+1},
        new int[]{j, j, j+1, j+1});
      map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
     }else if(b>=2){
      char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
      map[j][i]=map[j+1][i]=s;
      char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
      map[j][i+1]=map[j+1][i+1]=t;
      b-=2;
     }else if(a>=2){
      char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
      map[j][i]=map[j][i+1]=s;
      char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
      map[j+1][i]=map[j+1][i+1]=t;
      a-=2;
     }else{
      println("IMPOSSIBLE");
      return;
     }
    }
   }
   for(int i=0; i<m; i+=2){
    if(a>0){
     char s=getDifferent(new int[]{i, i+1}, new int[]{n-1, n-1});
     map[n-1][i]=map[n-1][i+1]=s;
     a--;
    }else{
     println("IMPOSSIBLE");
     return;
    }
   }
  }
  for(int j=0;j<n;j++){
   for(int i=0;i<m;i++){
    System.out.print(map[j][i]);
   }
   println("");
  }

 }

 char getDifferent(int[] xs, int[] ys){
  boolean[] exist=new boolean[256];
  for(int i=0; i<xs.length; i++){
   int x=xs[i];
   int y=ys[i];
   if(x>0)
    exist[map[y][x-1]]=true;
   if(x<m-1)
    exist[map[y][x+1]]=true;
   if(y>0)
    exist[map[y-1][x]]=true;
   if(y<n-1)
    exist[map[y+1][x]]=true;
  }
  for(int i=0; i<exist.length; i++)
   if(!exist[i]&&Character.isLowerCase(i))
    return (char)i;
  return '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();
 }
}

■D. Tickets
確率問題は苦手…

■Result
○○○××
2626p
51位

■Rating
1744 -> 1851

現時点で92位．CodeforcesでならRedCoderを狙えるかも…．

Prologの技芸 3.1節の練習問題

(1)

:- op(40,xfx,lt).
0 lt s(X) :- natural_number(X).
s(X) lt s(Y) :- X < Y.

:- op(40,xfx,gt).
s(X) gt 0 :- natural_number(X).
s(X) gt s(Y) :- X gt Y.

:- op(40,xfx,gteq).
X gteq 0 :- natural_number(X).
s(X) gteq s(Y) :- X gteq Y.

(3)

sn(0) =< sm(0)
sn-1(0) =< sm-1(0)
…
s(0) =< sm-n+1(0)
ここまででn個の節点
0 =< sm-n(0)
ここまででn+1個の節点
natural_number(sm-n(0))
natural_number(sm-n-1(0))
…
natural_number(s(0))
natural_number(0)
ここまででn+1+(m-n+1)=m+2個の節点

(4)

even(0).
even(s(s(X))) :- even(X).
odd(s(0)).
odd(s(s(X))) :- odd(X).

(5)

% fib(N,F) :-
% FはN番目のフィボナッチ数である．
fib(0,0).
fib(s(0),s(0)).
fib(s(s(N)),F) :- fib(N,F1), fib(s(N),F2), plus(F1,F2,F).

(6)

% divide(X,Y,Z) :-
%  Zは整数Xを整数Yで割った除数である．
divide(X,Y,s(Z)) :-
 X gteq Y, plus(Y,X1,X), divide(X1,Y,Z).
divide(X,Y,0) :- X lt Y.

(7)

% gcd(X,Y,Gcd) :-
%  GcdはXとYの最大公約数である．
gcd(0,X,X).
gcd(X,0,X).
gcd(X,Y,Gcd) :- X gteq Y, Y gt 0, plus(Y,Z,X), gcd(Y,Z,Gcd).
gcd(X,Y,Gcd) :- X lt Y, X gt 0, plus(X,Z,Y), gcd(X,Z,Gcd).

Prologの技芸 2.3節の練習問題

サンプルデータベース

on(block1,block2).
on(block2,block3).
on(block3,block4).
on(block5,block6).
on(block6,block7).

(1)

above(Block1,Block2) :- on(Block1,Block2).
above(Block1,Block2) :-
 on(Block1,Block), above(Block,Block2).

Prologの技芸 2.2節の練習問題

サンプルデータベース

day(complexity,monday).
start_time(complexity,9).
finish_time(complexity,11).
lecturer(complexity,harel).
building(complexity,feinberg).
room(complexity,a).

(1)

location(Course,Building) :-
 building(Course,Building).
busy(Lecturer,Time) :-
 lecturer(Course,Lecturer),
 start_time(Course,Start), finish_time(Course,Finish), 
 Start =< Time, Time =< Finish.
cannot_meet(Lecturer1,Lecturer2) :-
 lecturer(Course1,Lecturer1), lecturer(Course2,Lecturer2),
 Course1 \= Course2.

(2)

schedule_conflict(Time,Place,Course1,Course2) :-
 building(Course1,Building), building(Course2,Building),
 room(Course1,Room), room(Course2,Room),
 start_time(Course1,Start1), finish_time(Course1,Finish1), 
 start_time(Course2,Start2), finish_time(Course2,Finish2).
 Start1 =< Finish2, Start2 =< Finish1,
 Start1 =< Time, Time =< Finish1,
 Start2 =< Time, Time =< Finish2.

TopCoder SRM 479

SRM 479(8/15 1:00~3:00)

今日こそはRatingを上昇させると意気込みましたが…

■TheCoffeeTimeDivOne(Div1 Easy)
コーヒーと紅茶を乗客に配るのにかかる時間を求める問題．
最初はシンプルに求められるのかと思いましたが，無理そうだったので，44,777,777回のループに．
何とか強引に書き上げ，提出．しかし，最大ケースを投げるとTLEすることが判明．
ループ内の探索をboolean配列によるテーブルに直した所，無事通ったので再提出．
この再提出のせいで，得点は最低点の75.0p．もっと冷静に実装すれば一発で解けた問題だったと思います．

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

public class TheCoffeeTimeDivOne{
  public long find(int n, int[] tea){
    long cost=0;
    for(int i=0;i<tea.length;i++) tea[i]=-tea[i];
    Arrays.sort(tea);
    for(int i=0;i<tea.length;i++) tea[i]=-tea[i];
    for(int i=0;i<tea.length;i++){
      if(i%7==0){
        cost+=47;
        cost+=tea[i];
      }else{
        cost+=tea[i-1]-tea[i];
      }
      if(i%7==6 || i==tea.length-1){
        cost+=tea[i];
      }
      cost+=4;
    }
    long cost2=0;
    int px=0;
    Arrays.sort(tea);
    int lastX=0;
    int lastI=0;
    boolean[] has=new boolean[n+1];
    for(int i=0;i<tea.length;i++)
      has[tea[i]]=true;
    for(int x=n,i=0;x>=1;x--){
      if(has[x])
        continue;
      if(i%7==0){
        cost2+=47;
        cost2+=x;
      }else{
        cost2+=px-x;
      }
      if(i%7==6){
        cost2+=x;
      }
      cost2+=4;
      lastI=i;
      lastX=x;
      px=x;
      i++;
//      System.out.println("i="+i);
//      System.out.println("x="+x);
//      System.out.println(""+cost2);
    }
    if(lastI%7!=6)
      cost2+=lastX;
//    System.out.println("cost="+cost);
//    System.out.println("cost2="+cost2);
    return cost+cost2;
  }
}

■Challenge
流石に怖くて出来ませんでした…

■Result
○×× 0 0
75.0p

■Rating
1207 -> 1282

土壇場でRatingが回復しました…
もっと早く提出したいものです…

Aizu Online Judge

0100

まさかint*intでオーバーフローしてたなんて…言えない…．

TopCoder Member SRM 478

Member SRM 478(8/4 20:00~22:00)

■CarrotJumping(Div1 Easy)
初期座標xにいるウサギは1回ジャンプすると座標xから4*x+3 or 8*x+7に移動する．ウサギは最大100000回までしかジャンプできない．今いる座標が1000000007で割り切れるときウサギはニンジンを獲得することが出来る．初期座標xが与えられたもとで，ニンジンを獲得するまでにかかる最小のジャンプ回数を返せ，100000回以内でニンジンを獲得することが出来ない場合は-1を返せ．

ウサギは(初期座標xの時)，
2ⁿx+2ⁿ-1 (n≧2)
の地点に行くことが可能で，この時ジャンプの最小回数が(n+2)/3回になる事まで分かりましたが，見事コーディングでミスしました(n≧3としてしまった)．
そこさえ直せば通ったので尚更ショック…．

■Challenges
0p

■Result
××× 0 0

■Rating
1233 -> 1207

（　＾ω＾）＜Div2へようこそ

Aizu Online Judge

8/7から8/8にかけて24時間(8時間仮眠)AOJをして来ました．
トータルで53問しか解けませんでしたが，中々アグレッシブだったと思います．

20:28 0051
20:33 0052
20:43 0053
20:46 0055
20:52 0057
20:55 0058
21:12 0056
21:36 0061
21:40 0062
21:42 0063
21:51 0064
21:59 0066
22:31 0067
23:00 0065
23:16 0071
23:35 0074
23:39 0075
23:46 0076
23:56 0077
00:11 0078
00:19 0079
00:30 0080
00:44 0083
01:29 0085
02:04 0088
02:20 0089
02:49 0093
03:24 0101
03:30 0102
03:36 0103
03:43 0104
03:50 0105
04:03 0107
04:11 0108
14:52 0114
14:58 0112
51:01 0111
16:03 0021
16:16 0026
16:27 0050
16:29 0113
16:33 0054
16:48 0042
16:57 0059
17:22 0073
18:26 0004
18:54 0081
19:04 0082
19:13 0123
19:39 0124
19:58 0126
20:09 0127
20:15 0128

TopCoder 練習

CarrotJumping(Member SRM 478 Div1 Easy)

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

public class CarrotJumping{
 public int theJump(int init){
  long r=4;
  int n;
  for(n=2;n<=300000;n++){
   if((r*init+r-1)%1000000007L==0)
    break;
   r*=2;
   r%=1000000007L;
  }
  int ans=(n+2)/3;
  if(ans>100000)
   return -1;
  else return ans;
 }
}

Aizu Online Judge

0040
0044
0045
0046
0047
0048
0049

Aizu Online Judge

0027
0028
0029
0031
0032
0033
0034
0035
0036

専門書を買う

物理学とは何だろうか
コンパイラ (新コンピュータサイエンス講座)

Codeforces Beta Round #24

Codeforces Beta Round #24 7/26(22:00~24:00)

■A. Ring road

□問題
n個の都市がある．
ある都市a_iとある都市b_iの間には，一方通行の道路がある．
一方通行の向きを変えるには，c_iのコストがかかる．
ある都市から他のn-1都市全てに辿れるよう一方通行の向きを変えたい．
最小コストはいくらか．

□解法
グラフが環になっているので，一方通行の流れを時計回り/反時計回りとする時のそれぞれのコストを計算し，小さい方を出力するだけ．一発AC．

# 実は反時計回りでのコストは，総コストから時計回りのコストを引くだけで計算できます．

□コード

import java.util.Scanner;

public class A{

 Scanner sc=new Scanner(System.in);

 int n;
 int[] a, b, c;

 public void run(){
  n=sc.nextInt();
  a=new int[n];
  b=new int[n];
  c=new int[n];
  for(int i=0; i<n; i++){
   a[i]=sc.nextInt();
   b[i]=sc.nextInt();
   c[i]=sc.nextInt();
  }
  int cost1=0;
  boolean[] visited=new boolean[n];
  visited[0]=true;
  int p=b[0];
  for(int k=1; k<n; k++){
   for(int i=0; i<n; i++){
    if(visited[i])
     continue;
    if(a[i]==p){
     p=b[i];
     visited[i]=true;
     break;
    }else if(b[i]==p){
     cost1+=c[i];
     p=a[i];
     visited[i]=true;
     break;
    }
   }
  }
  int cost=0;
  for(int x : c)
   cost+=x;
  int cost2=cost-cost1;
  println(""+Math.min(cost1, cost2));
 }

 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. F1 Champions

□問題
F1のレースがt回行われた．
最終順位のつけ方は以下の2種類の以下の優先度順に決める．
Original
勝ち点が大きい->1位になった回数が多い->2位になった回数が多い->…
Alternative rule
1位になった回数が多い->勝ち点が大きい->2位になった回数が多い->…
勝ち点は，1位から順に，25, 18, 15, 12, 10, 8, 6, 4, 2, 1, 0, …．
それぞれのルールでの最終順位が1位のドライバーの名前を出力せよ．

□解法
ソートするだけ．一発AC．

□コード

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class B{

 Scanner sc=new Scanner(System.in);

 int m, n;
 HashMap<String, R> map=new HashMap<String, R>();
 int[] ps={25, 18, 15, 12, 10, 8, 6, 4, 2, 1};

 public void run(){
  m=sc.nextInt();
  for(int i=0; i<m; i++){
   n=sc.nextInt();
   for(int k=0; k<n; k++){
    String s=sc.next();
    if(!map.containsKey(s))
     map.put(s, new R(s));
    R r=map.get(s);
    if(k<ps.length)
     r.score+=ps[k];
    r.rank[k]++;
   }
  }

  R[] rs=map.values().toArray(new R[0]);

  Arrays.sort(rs, new Comparator<R>(){
   @Override
   public int compare(R r1, R r2){
    if(r1.score!=r2.score)
     return r2.score-r1.score;
    for(int i=0; i<50; i++)
     if(r1.rank[i]!=r2.rank[i])
      return r2.rank[i]-r1.rank[i];
    return 0;
   }
  });
  println(rs[0].name);

  Arrays.sort(rs, new Comparator<R>(){
   @Override
   public int compare(R r1, R r2){
    if(r1.rank[0]!=r2.rank[0])
     return r2.rank[0]-r1.rank[0];
    if(r1.score!=r2.score)
     return r2.score-r1.score;
    for(int i=1; i<50; i++){
     if(r1.rank[i]!=r2.rank[i])
      return r2.rank[i]-r1.rank[i];
    }
    return 0;
   }
  });
  println(rs[0].name);
 }

 final class R{
  int score=0;
  int[] rank=new int[50];
  String name;

  R(String name){
   this.name=name;
  }
 }

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

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

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

}

■C. Sequence of points

□問題
座標M₀, A₀, …, A_n-1が与えられる．
M_iは，A_(i-1)%nに関してM_i-1と対称である．
M_jを計算せよ．

□解法
1≦j≦10¹⁸だと…?!
これは漸化式みたいにして解くのかな?
問題より，
M_i=2A_(i-1)%n-M_i-1
だから…(弄る
周期2nになった．j%2nでOKではないですか．
ついでにi=0~2n-1についての(一応)閉じた式が計算できたの実装．
一発AC．

# 無駄に頑張りましたが，実は，閉じた式なんか要らなくて，周期2nと分かった時点で上の漸化式もどきからM₀, …, M_2n-1を生成すれば良かったのでした．

□コード

import java.util.Scanner;

public class C{

 Scanner sc=new Scanner(System.in);

 int n;
 long j;

 public void run(){
  n=sc.nextInt();
  j=sc.nextLong();
  int[] mx=new int[2*n];
  int[] my=new int[2*n];
  mx[0]=sc.nextInt();
  my[0]=sc.nextInt();
  int[] ax=new int[n];
  int[] ay=new int[n];
  for(int i=0; i<n; i++){
   ax[i]=sc.nextInt();
   ay[i]=sc.nextInt();
  }
  for(int i=1; i<2*n; i++){
   mx[i]=2*ax[(i-1)%n]-mx[i-1];
   my[i]=2*ay[(i-1)%n]-my[i-1];
  }
  int k=(int)(j%(2*n));
  println(mx[k]+" "+my[k]);
 }

 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
○○○××

■Rating
1633 -> 1744

大幅に上昇．今回は割と調子が良かったです．

Aizu Online Judge

22
24
25