2010年8月30日月曜日

Project Euler

problem 71
problem 79

2010年8月28日土曜日

専門書を買う

Prologの技芸

2010年8月18日水曜日

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を狙えるかも….

2010年8月17日火曜日

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.

2010年8月16日月曜日

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が回復しました…
もっと早く提出したいものです…

2010年8月15日日曜日

Aizu Online Judge

0100

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

2010年8月14日土曜日

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の時),
2nx+2n-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;
}
}

2010年8月6日金曜日

Aizu Online Judge

0040
0044
0045
0046
0047
0048
0049

2010年8月2日月曜日

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個の都市がある.
ある都市aiとある都市biの間には,一方通行の道路がある.
一方通行の向きを変えるには,ciのコストがかかる.
ある都市から他の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

□問題
座標M0, A0, …, An-1が与えられる.
Miは,A(i-1)%nに関してMi-1と対称である.
Mjを計算せよ.

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

# 無駄に頑張りましたが,実は,閉じた式なんか要らなくて,周期2nと分かった時点で上の漸化式もどきからM0, …, M2n-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

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

2010年8月1日日曜日