ABC274A～Eの解答[Java]

はじめに

今回は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発想すらできなかったり、知識不足というか･･･精進不足というか･･･そんな感じなコンテストでした。