はじめに
今回はA～Dがコンテスト中のもの、Eは公式解説を見ながら実装したものです。
では、見ていきましょう。
A - Batting Average
問題文はこちら
printfを使えば良さそうですね。
A.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//A、Bの受け取り
int A = System.in.nextInt();
int B = System.in.nextInt();
//小数点第3位まで表示
System.out.printf("%.3f",(double)B/A);
System.out.close();
}
}
四捨五入されるの今回初めて知りました。便利ですね(今更)。
B - Line Sensor
問題文はこちら
普通に配列に加算していけば良いですね。
B.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//H、Wの受け取り
int H = System.in.nextInt();
int W = System.in.nextInt();
//数を数える配列
int[] sum = new int[W];
//#だったら適切な箇所に加算
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
char c = System.in.nextChar();
if(c=='#')
sum[j]++;
}
}
//空白区切りで出力
System.out.println(sum," ");
System.out.close();
}
}
そんなに難しくは無いですね。
C - Ameba
問題文はこちら
for文で回しながら配列に記録していけば良いですね。
C.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//Nの受け取り
int N = System.in.nextInt();
//自分が何代目か記録
int[] parent = new int[2*(N+1)];
//1は初代なので0(初期値が0なのでやらなくても良い)
parent[1] = 0;
//Aの次の世代になるように順に更新
for(int i=1;i<=N;i++){
int A = System.in.nextInt();
parent[2*i] = parent[A]+1;
parent[2*i+1] = parent[A]+1;
}
//改行区切りで出力(1-indexedなので0は出力しないように)
for(int i=1;i<2*(N+1);i++)
System.out.println(parent[i]);
System.out.close();
}
}
問題文を理解するのにちょっと時間がかかってしまいましたが、内容自体はそこまで難しくは無いですね。
D - Robot Arms 2
問題文はこちら
$dp[i]$に「$i$に到達可能か」を記録する形で動的計画法を実装しました。indexに負数が来ちゃうと困るので、原点を$10^4$として実装しました。
遷移は以下の通りです($\mathrm{next}$は$dp$の状態から移動した後の結果を保持する配列です)。
$\mathrm{next}[j] = dp[j+A[i]]\ \ |\ \ dp[j-A[i]]$
なお、$x$座標と$y$座標別々で行なってます。
D.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//N、x、y、Aの受け取り
int N = System.in.nextInt();
int x = System.in.nextInt();
int y = System.in.nextInt();
int[] A = System.in.nextInt(N);
//いちいちキャストして書くのが面倒なので別変数に記録しておく
int max = (int)1e4;
//dp[i]･･･座標iに到達可能か(原点はmax)(最初はx座標から)
boolean[] dp = new boolean[2*max+1];
//A[0]だけは必ず正なので先に記録
dp[A[0]+max] = true;
//遷移(偶数番目のみ参照)
for(int i=2;i<N;i+=2){
boolean[] next = new boolean[2*max+1];
for(int j=0;j<=2*max;j++){
if(j>=A[i])
next[j] |= dp[j-A[i]];
if(j<=2*max-A[i])
next[j] |= dp[j+A[i]];
}
dp = next;
}
//移動可能かを記録する変数(後々yの結果との論理積をとる)
boolean can = dp[x+max];
//y座標についても同じことをやる
dp = new boolean[2*max+1];
dp[max] = true;
for(int i=1;i<N;i+=2){
boolean[] next = new boolean[2*max+1];
for(int j=0;j<=2*max;j++){
if(j>=A[i])
next[j] |= dp[j-A[i]];
if(j<=2*max-A[i])
next[j] |= dp[j+A[i]];
}
dp = next;
}
//x、y共に可能だったかを記録
can &= dp[y+max];
//結果に応じた出力を
System.out.println(can?"Yes":"No");
System.out.close();
}
}
かなり時間をかけてしまいました。悲しい･･･。
ちなみに、$|X|\le10^4$、$N\le10^3$なのでdpの範囲はこれで十分です($A_i$が全部$10$でも$|x|=10^4$までしか移動できないので)。
E - Booster
問題文はこちら
公式解説通りかと思います。
Cの実装例の__builtin_popcountはInteger.bitCountを使いました。
E.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//N、Mの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
//各座標の受け取り(大きさは[N+M][2])
int[][] point = System.in.nextInt(N+M,2);
//dp[i][S]･･･今iで、Sに行ったことがある時の最短
double[][] dp = new double[N+M][1<<N+M];
//初期値代入
for(int i=0;i<dp.length;i++)
Arrays.fill(dp[i],1e18);
//最初は原点からの移動時間を記録
for(int i=0;i<N+M;i++)
dp[i][1<<i] = Math.hypot(point[i][0],point[i][1]);
//遷移
for(int i=1;i<dp[0].length;i++){
//速度計算(速さをsとすると、sp=1/s)
double sp = Math.pow(0.5,Integer.bitCount(i>>N));
//jは移動前、kは移動先
for(int j=0;j<N+M;j++)if(((i>>j)&1)==1){
for(int k=0;k<N+M;k++)if(((i>>k)&1)==0){
//ちょっと長いので変数に突っ込む(jからkへ移動したときの総時間)
double temp = dp[j][i]+Math.hypot(point[j][0]-point[k][0],point[j][1]-point[k][1])*sp;
//今入っている距離とtempのうち、小さい方で上書き
dp[k][i^(1<<k)] = Math.min(dp[k][i^(1<<k)],temp);
}
}
}
//答えを入れる変数(初期値は1e18でやった)
double ans = 1e18;
//forの中に1<<Nって書くのが嫌だったので別変数に
int n = 1<<N;
//全部の町に行った中で最短を探す
for(int i=0;i<N+M;i++)
for(int j=n-1;j<dp[i].length;j+=n)
ans = Math.min(ans,dp[i][j]+Math.hypot(point[i][0],point[i][1])*(Math.pow(0.5,Integer.bitCount(j>>N))));
//誤差が10e-6まで許されるので第7位まで出力しておく
System.out.printf("%.7f",ans);
System.out.close();
}
}
改めて僕が解説するような点は無いですね。純粋に難しかった･･･(知識不足)。
感想
A:printf使えば特に難しくは感じない
B:易しい
C:比較的易しいけど、誤読しそうだった気がする
D:最初試しにDFSぶん投げたことを後悔している･･･(圧倒的時間ロス)
E:何もわからん･･･
って感じでした。
printfの使い方も急いでググったり、E発想すらできなかったり、知識不足というか･･･精進不足というか･･･そんな感じなコンテストでした。