| 2進カウンタをK回進めたとき，下位Nビットが全て1なら"ON"，そうでないなら"OFF"を出力せよ． |
□解法B
ビット演算でクールにキメたかったのですが，あまり自信が無かったため，Kを2進文字列に直した後，下位Nビットが全て1であるか調べました．
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;
}
}
■問題B
長い文章でしたが，問題自体は↓．
| maxy gcd(t1+y, t2+y, …, tN+y)となる最小のyを求めよ． |
□解法B
まず，gcd(t1+y, t2+y, …, tN+y)=mとします．
このとき，
m|ti+y (1≦i≦N)
であるため，
m|(ti+y)-(tj+y) (1≦i, j≦N)
よって，
m|ti-tj (1≦i, j≦N)
ここで，
gcd1≦i, j≦N(ti-tj)=n
とすれば，n=m(のはずです…)．
あとは，m|t1+yとなるようにyを求めて((m-t1)%mを計算する)終わり．
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();
}
}
■問題C
| 1人以上の客から構成されるグループがNグループある．1Euro/人とすると，k人乗りのローラーコースターをR回走らせた時，いくら稼げるか． |
R=4，k=6，N=4として，グループ毎の人数を[1,4,2,1]と表すと，以下のようになります．
| 回数 | 乗っているグループ | 待っているグループ | 儲け |
| 1 | [1, 4] | [2, 1] | 5 |
| 2 | [2, 1, 1] | [4] | 4 |
| 3 | [4, 2] | [1, 1] | 6 |
| 4 | [1, 1 ,4] | [2] | 6 |
□解法C
R>Nであれば，必ず，以前走らせた時と同じパターンが出てくるので，それを記憶しておき…としたのですが，コーディングをミスした模様．largeでエラー連発でした．
■結果
| A | B | C | |
| small | ○ | ○ | ○ |
| large | ○ | ○ | × |
| point | 33 | 33 | 10 |
76Point，2318位．
とりあえずは予選通過，ということで．
