クラス2
時刻tでの状態 | ■■■ | ■■□ | ■□■ | ■□□ | □■■ | □■□ | □□■ | □□□ |
時刻t+1での状態 | □ | □ | □ | ■ | ■ | □ | ■ | ■ |
Fig.1 rule27
ビルとビルの間に複数のロープを張っていく.双方のビルに張るロープの位置が与えられた時,何箇所が交差するか. |
import java.io.*;
import java.util.*;
public class A {
int cal(int n,int[] a,int[] b){
int res=0;
for(int j=0;j<n-1;j++)
for(int i=j+1;i<n;i++)
if((a[j]-a[i])*(b[j]-b[i])<0)
res++;
return res;
}
void a() throws Exception{
Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.in"));
BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.out"));
int T=sc.nextInt();
for(int k=0;k<T;k++){
int N=sc.nextInt();
int[] a=new int[N];
int[] b=new int[N];
for(int i=0;i<N;i++){
a[i]=sc.nextInt();
b[i]=sc.nextInt();
}
int ans=cal(N,a,b);
System.out.println("Case #"+(k+1)+": "+ans);
bw.write("Case #"+(k+1)+": "+ans);
bw.newLine();
}
bw.close();
}
}
白と黒のタイルで構成されたボードからチェスボード(白と黒の市松模様)を切り出していく.出来るだけ大きいチェスボードから切り出していった時,どの大きさのものが幾つ出来るか. |
A | B | C | |
small | ○(9) | ×(14) | ○(18) |
large | ○(13) | ×(22) | ×(24) |
point | 22 | 0 | 18 |
既に作られているディレクトリ構造と,これから作ろうとしているディレクトリ構造が与えられる.mkdirコマンドは何回実行する必要があるか. |
import java.io.*;
import java.util.*;
public class A {
class Node{
HashMap<String, Node> children=new HashMap<String, Node>();
}
long cal(int N, int M, String[] exist, String[] create){
Node root=new Node();
for(int i=0;i<N;i++){
String[] s=exist[i].split("/");
Node node=root;
for(int k=1;k<s.length;k++){
if(!node.children.containsKey(s[k]))
node.children.put(s[k], new Node());
node=node.children.get(s[k]);
}
}
long ret=0;
for(int i=0;i<M;i++){
String[] s=create[i].split("/");
Node node=root;
for(int k=1;k<s.length;k++){
if(!node.children.containsKey(s[k])){
ret++;
node.children.put(s[k], new Node());
}
node=node.children.get(s[k]);
}
}
return ret;
}
void a() throws Exception{
Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.in"));
BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.out"));
int T=sc.nextInt();
for(int k=0;k<T;k++){
int N=sc.nextInt();
int M=sc.nextInt();
sc.nextLine();
String[] exist=new String[N];
for(int i=0;i<N;i++)
exist[i]=sc.nextLine();
String[] create=new String[M];
for(int i=0;i<M;i++)
create[i]=sc.nextLine();
long ans=cal(N,M,exist,create);
System.out.println("Case #"+(k+1)+": "+ans);
bw.write("Case #"+(k+1)+": "+ans);
bw.newLine();
}
bw.close();
}
}
沢山のヒヨコちゃんがレール上にいる.それぞれのヒヨコはある方向に走っており,後方のヒヨコちゃんは,前方のヒヨコちゃんに追いついてしまったら,前方のヒヨコちゃんと同じ速度に減速する.また,クレーンを使って隣り合う2匹のヒヨコちゃんを交換することが出来る.N匹のヒヨコに対し,初期位置xi[m]と速度vi[m/s]が与えられる.K(≦N)匹のヒヨコがT[s]以内でB[m]の地点に到達するように,クレーンでヒヨコを移動させた時,その最小回数はいくらか. |
import java.io.*;
import java.util.*;
public class B {
String cal(int N,int K,long B,int T,int[] x,int[] v){
boolean[] barn=new boolean[N];
int nBarn=0;
for(int i=0;i<N;i++){
int p=x[i]+v[i]*T;
if(p>=B)
nBarn++;
barn[i]=p>=B;
}
if(nBarn<K)
return "IMPOSSIBLE";
int pick=0;
int j=N;
for(int k=0;k<K;k++){
while(!barn[--j]);
for(int i=j;i+1<N&&!barn[i+1];i++){
boolean f=barn[i];
barn[i]=barn[i+1];
barn[i+1]=f;
pick++;
}
}
return ""+pick;
}
void a() throws Exception{
Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.in"));
BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.out"));
int C=sc.nextInt();
for(int k=0;k<C;k++){
int N=sc.nextInt();
int K=sc.nextInt();
long B=sc.nextLong();
int T=sc.nextInt();
int[] x=new int[N];
int[] v=new int[N];
for(int i=0;i<N;i++)
x[i]=sc.nextInt();
for(int i=0;i<N;i++)
v[i]=sc.nextInt();
String ans=cal(N,K,B,T,x,v);
System.out.println("Case #"+(k+1)+": "+ans);
bw.write("Case #"+(k+1)+": "+ans);
bw.newLine();
}
bw.close();
}
}
a1, …, ak=nという数列がある.nはk番目,kはi番目,iはj番目,…という操作の結果,最終的にa1は1番目,となるような数列はいくつあるか.与えられる数はnのみ. |
A | B | C | |
small | ○(12) | ○(13) | ×(14) |
large | ○(14) | ○(17) | ×(30) |
point | 26 | 30 | 0 |
/** Marge sort(マージソート) */
public void margeSort(int[] a){
int n=a.length;
if(n==1) return;
// b.length+c.length=a.length
int[] b=new int[n/2];
int[] c=new int[n-n/2];
System.arraycopy(a, 0, b, 0, b.length);
System.arraycopy(a, n/2, c, 0, c.length);
margeSort(b);
margeSort(c);
// ソートされたbとcをaにマージ
for(int i=0, j=0, k=0;i<n;i++)
if(k==c.length)
a[i]=b[j++];
else if(j==b.length)
a[i]=c[k++];
else if(b[j]<c[k])
a[i]=b[j++];
else
a[i]=c[k++];
}
a1, …, am
b1, …, bnこの時,
ai<=ai+1
bj<=bj+1とすれば,つまり,aもbもソートされているとすれば,それらをマージした以下の配列(数列)cが作れる.
c1, …, cm+nこれを再帰的に適用します.
8 | 3 | 4 | 6 | 2 | 5 | 7 | 1 |
8 | 3 | 4 | 6 | 2 | 5 | 7 | 1 |
8 | 3 | 4 | 6 | 2 | 5 | 7 | 1 |
8 | 3 | 4 | 6 | 2 | 5 | 7 | 1 |
3 | 8 | 4 | 6 | 2 | 5 | 1 | 7 |
3 | 4 | 6 | 8 | 1 | 2 | 5 | 7 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
q: 700
2 2 5 5 7
2 q: 700
2 0
10 q: 700
2 0 2 1 0 0 0 0 0 0
_ q: 700
2 0 2 1
__ q: 700
2 5 7
2 2 1
totient=: * -.@%@~.&.q:
totient 700
240
定義 x y (動詞への)引数 m n 名詞 u v 動詞 f g h 動詞
動詞 x * y x*y Times 乗算(二項演算) -. y 1-y Complement 補数(単項演算) % y 1/y Reciprocal 逆数(単項演算) ~. y - Nub 重複要素削除(単項演算) q: y - Prime Factors 素因数分解(単項演算)
副詞 @ u@v y ⇔ u v y Atop &. u&.v y ⇔ vi u v y (viはvの逆演算) Under
-.@%@~.
は,(厳密には演算の順序が)以下のようになります.-. % ~.
また,-.@%@~.&.q: y
は,以下のようになります.q:の逆演算 -. % ~. q: y
結果として,(* -.@%@~.&.q:) y
は,(Hookが適用され)以下のようになります.y * (q:の逆演算 -. % ~. q:) y
2進カウンタをK回進めたとき,下位Nビットが全て1なら"ON",そうでないなら"OFF"を出力せよ. |
import java.io.*;
public class A {
public void a() throws Exception{
BufferedReader br=new BufferedReader(new FileReader("C:\\A-large.in"));
BufferedWriter bw=new BufferedWriter(new FileWriter("C:\\A-large.out"));
int T=Integer.parseInt(br.readLine());
for(int i=0;i<T;i++){
String[] s=br.readLine().split(" ");
int N=Integer.parseInt(s[0]);
int K=Integer.parseInt(s[1]);
String t=toBS(K);
boolean f=true;
for(int j=t.length()-N;j<t.length();j++){
if(j<0||t.charAt(j)!='1'){
f=false;
break;
}
}
String ans="Case #"+(i+1)+": "+(f?"ON":"OFF");
bw.write(ans);
bw.newLine();
}
bw.close();
}
String toBS(int n){
if(n==0)
return "0";
String s="";
while(n!=0){
s=n%2+s;
n/=2;
}
return s;
}
}
maxy gcd(t1+y, t2+y, …, tN+y)となる最小のyを求めよ. |
import java.io.*;
import java.math.*;
import java.util.*;
public class B {
BigInteger calcY(int N,BigInteger[] t){
Arrays.sort(t);
LinkedList<BigInteger> list=new LinkedList<BigInteger>();
for(int j=0;j<N-1;j++)
for(int i=j+1;i<N;i++)
list.add(t[j].subtract(t[i]));
BigInteger gcd=list.get(0);
for(BigInteger bi:list)
gcd=bi.gcd(gcd);
return gcd.subtract(t[0]).mod(gcd);
}
public void b() throws Exception{
BufferedReader br=new BufferedReader(new FileReader("C:\\B-large.in"));
BufferedWriter bw=new BufferedWriter(new FileWriter("C:\\B-large.out"));
int C=Integer.parseInt(br.readLine());
for(int i=0;i<C;i++){
String[] s=br.readLine().split(" ");
int N=Integer.parseInt(s[0]);
BigInteger[] t=new BigInteger[N];
for(int j=0;j<N;j++)
t[j]=new BigInteger(s[j+1]);
BigInteger y=calcY(N,t);
String ans="Case #"+(i+1)+": "+y;
bw.write(ans);
bw.newLine();
}
bw.close();
}
}
1人以上の客から構成されるグループがNグループある.1Euro/人とすると,k人乗りのローラーコースターをR回走らせた時,いくら稼げるか. |
回数 | 乗っているグループ | 待っているグループ | 儲け |
1 | [1, 4] | [2, 1] | 5 |
2 | [2, 1, 1] | [4] | 4 |
3 | [4, 2] | [1, 1] | 6 |
4 | [1, 1 ,4] | [2] | 6 |
A | B | C | |
small | ○ | ○ | ○ |
large | ○ | ○ | × |
point | 33 | 33 | 10 |
import java.util.*;
import java.lang.*;
import java.math.*;
public class TheMoviesLevelOneDivOne {
public long find(int n, int m, int[] row, int[] seat) {
long ret=(long)(m-1)*n;
int len=row.length;
for(int j=0;j<len;j++){
if(seat[j]>1)
ret--;
if(seat[j]<m)
ret--;
for(int i=0;i<len;i++)
if((i!=j) && (row[i]==row[j]) && (seat[i]==seat[j]+1))
ret++;
}
return ret;
}
}
import java.util.*;
import java.lang.*;
import java.math.*;
public class TheMoviesLevelOneDivOne {
public long find(int n, int m, int[] row, int[] seat) {
int len=seat.length;
for (int i = 0; i < len - 1; i++) {
for (int j = len - 1; j < i; j--) {
if(row[j-1]>row[j]||(row[j-1]==row[i]&&seat[j-1]>seat[j])){
int t=row[j-1];
row[j-1]=row[j];
row[j]=t;
t=seat[j-1];
seat[j-1]=seat[j];
seat[j]=t;
}
}
}
long ret=(long)(m-1)*n;
for(int j=0;j<len;){
int i;
for(i=0;j+i<len&&row[j+i]==row[j]&&seat[j+i]==seat[j]+i;i++)
;
ret-=i+1;
if(seat[j]==1)
ret++;
if(seat[j+i-1]==m)
ret++;
j+=i;
}
return ret;
}
}
// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
SRM | Easy | Normal | Hard |
295 | o | - | - |
296 | o | - | - |
297 | o | - | - |
298 | o | - | - |
350 | o | - | - |
386 | o | - | - |
447 | o | - | - |
451 | o | - | - |
462 | o | - | - |
463 | o | - | - |
464 | o | - | - |
465 | o | - | - |
466 | o | - | - |
469 | o | - | - |
471 | o | - | - |
472 | o | - | - |
473 | o | - | - |
474 | o | - | - |
475 | o | - | - |
476 | o | - | - |
477 | o | - | - |
478 | o | - | - |
479 | o | - | - |
480 | o | - | - |
481 | o | - | - |
482 | o | o | - |
483 | o | - | - |
484 | o | - | - |
485 | o | - | - |
486 | o | - | - |
487 | o | - | - |
503 | - | o | - |
511 | - | o | - |
1 | hello world | 30B |
2 | echo | 31B |
3 | 99 shinichiroes of hamaji | 258B |
4 | example com | 451B |
5 | Smileys Triangle | 63B |
8 | delete blank lines | 37B |
14 | ultimate problem | 19B |
16 | even lines | 40B |
19 | Fibonacci Numbers | 46B |
34 | FizzBuzz | 84B |
48 | 67B |