ABC044の解答[Java]

はじめに

A～Cは自力AC、Dは解説ACとなります。
昔のコードなので、そのままのも載せますがなるべく見やすく書き換えたものも一緒に載せます。

では、見ていきましょう。

A - 高橋君とホテルイージー

問題文はこちら

特に考えずに場合分けをして解きました。
NがK以下ならNX、Kより大きいならKX+(N-K)*Yって感じです。

A.java

import java.io.*;
class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//各値の受け取り
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		int X = Integer.parseInt(br.readLine());
		int Y = Integer.parseInt(br.readLine());

		//上記の条件にしたがって分岐
		if(N<=K){
			System.out.println(N*X);
		}
		else{
			System.out.println(K*X+(N-K)*Y);
		}
	}
}

一応if～elseを使わなくても解くことはできます。

A改.java

import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//値の受け取り
		int N = sc.nextInt();
		int K = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();

		//minとmaxで上手く実装
		System.out.println(Math.min(N,K)*X+Math.max(0,N-K)*Y);
	}
}

まぁif～elseを使わないってだけなら三項演算子でも使えば良いんですがね。そこは好みで･･･。

B - 美しい文字列

問題文はこちら

このときは文字列を1文字ずつ分割して2i番目と2i+1番目が同じか全部見ていって判定しました。
なお、文字の長さが奇数の場合は最初にはじいてます。

B.java

import java.io.*;
import java.util.*;

//文字分割用(当時はtoCharArrayを知らなかった)
class subMain{
	public static String[] parStr(String someStr){
		String[] str = someStr.split("");
		return str;
	}
}
class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//wの受け取り
		String[] w = subMain.parStr(br.readLine());

		//そもそも偶数文字でない？
		if(w.length%2==1){
			System.out.println("No");
			System.exit(0);
		}

		//ソート
		Arrays.sort(w);

		//奇数番目とその後ろの文字が一致している=偶数個存在している
		for(int i=0;i<w.length;i+=2){
			if(!(w[i].equals(w[i+1]))){
				System.out.println("No");
				System.exit(0);
			}
		}
		System.out.println("Yes");
	}
}

これ書いてて思いついたのは、a～zの出現回数を記録する配列を準備して全部数えて判定する、とかでしょうか。

B改.java

import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//wの受け取り
		char[] w = sc.next().toCharArray();

		//a～zの個数を数える配列
		int[] count = new int['z'-'a'+1];

		//各文字数え上げ
		for(char c:w)count[c-'a']++;

		//各文字の数は偶数か？
		for(int tmp:count){
			if((tmp%2)!=0){
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}
}

こんな感じで十分ですね。

C - 高橋君とカード

問題文はこちら

i枚まででj枚選んだときの合計がkの時の通りをdp[i][j][k]として記録して解きました。
かなり煩雑ですが、やってることは公式解説の満点解法1と同じはずですのでよくわからない場合はそちらも参考にしてください。

C.java

import java.io.*;
class subMain{
	//メモ化再帰用配列(boolでメモったか記録)
	long memo[][][];
	boolean debugMemo[][][];
	int[] x;
	int max;

	//コンストラクタでsubMainに情報を渡す
	public subMain(int N,int[] xx){
		x = new int[xx.length+1];
		int temp = 0;
		for(int i=1;i<x.length;i++){
			x[i] = xx[i-1];
			if(temp<xx[i-1])
				temp = xx[i-1];
		}
		max = temp;
		memo = new long[N+1][N+1][N*max+1];
		debugMemo = new boolean[N+1][N+1][N*max+1];
		memo[0][0][0] = 1;
		debugMemo[0][0][0] = true;
	}

	//空白区切りの整数受け取りメソッド
	public static int[] parIntWithS(String someInt){
		String[] str = someInt.split(" ");
		int[] Intel = new int[str.length];
		for(int i=0;i<str.length;i++){
			Intel[i] = Integer.parseInt(str[i]);
		}
		return Intel;
	}

	//再帰
	public long dp(int j,int k,int s){

		//答え用変数
		long ans = 0;

		//解説通りの分岐を
		if(j==0&&k==0&&s==0)
			ans = 1;
		else if(debugMemo[j][k][s])
			return memo[j][k][s];
		else if(j>0&&s<x[j])
			ans = dp(j-1,k,s);
		else if(j>0&&k>0&&s>=x[j])
			ans = dp(j-1,k,s)+dp(j-1,k-1,s-x[j]);

		//答えをメモってから返却
		memo[j][k][s] = ans;
		debugMemo[j][k][s] = true;
		return ans;
	}
}
class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//各値の受け取り
		int[] NA = subMain.parIntWithS(br.readLine());
		int[] x = subMain.parIntWithS(br.readLine());

		//事前準備
		subMain sm = new subMain(NA[0],x);

		//i枚選んだ時の合計がi*Aになるようなものを数え上げ
		long answer = 0;
		for(int i=1;i<=NA[0];i++){
			if(i*NA[1]>sm.max*NA[0]+1)
				break;
			answer += sm.dp(NA[0],i,i*NA[1]);
		}

		//答えの出力
		System.out.println(answer);
	}
}

基本方針はそのままで簡素にまとめるとこんな感じでしょうか。

C改.java

import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//各値の受け取り
		int N = sc.nextInt();
		int A = sc.nextInt();
		int[] x = new int[N];
		for(int i=0;i<N;i++)x[i] = sc.nextInt();

		//dp[i][j][k]:i枚目まででj枚選んだ時の合計がkである組合せの数
		long[][][] dp = new long[N+1][N+1][50*N+1];

		//初期値セット
		dp[0][0][0] = 1;

		//遷移
		for(int i=1;i<=N;i++){
			for(int j=0;j<=i;j++){
				for(int k=0;k<=N*A;k++){
					dp[i][j][k] = dp[i-1][j][k];
					dp[i][j][k] += (j>0&&k>=x[i-1])?dp[i-1][j-1][k-x[i-1]]:0;
				}
			}
		}

		//平均がAであるものを数え上げ
		long answer = 0;
		for(int i=1;i<=N;i++)answer += dp[N][i][i*A];

		//答えの出力
		System.out.println(answer);
	}
}

カードを選んだ時と選ばなかったときを上手く遷移するって考えれば特に難しくはないですね。

D - 桁和

問題文はこちら

公式解説通りですね。
ただ、まぁ言われればそうなんですが･･･私には思いつかないや･･･って感じです。
とりあえず解説通りの式をコードに落とし込みました。

D.java

import java.io.*;
class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//各値の受け取り
		long n = Long.parseLong(br.readLine());
		long s = Long.parseLong(br.readLine());

		//n==sの時は答えがすぐ決まる
		if(n==s){
			System.out.println(n+1);
			System.exit(0);
		}

		//√nまでは全探索
		long check = (long)Math.sqrt(n);
		for(long i=2;i<=check;i++){
			if(func(i,n)==s){
				System.out.println(i);
				System.exit(0);
			}
		}

		//√n以降はb進数で表すと二桁なので二桁目を決めてbを求め
		//そこからf(b,n)=sが成り立つか調べる、という方針で
		for(long i=check;i>0;i--){
			long b= (n - s) / i + 1;
			if(b<2)
				continue;
			if(func(b,n)==s){
				System.out.println(b);
				System.exit(0);
			}
		}

		//見つからなかった=存在しないので-1を出力
		System.out.println(-1);
	}

	//定義通りの再帰関数
	public static long func(long b,long n){
		if(b>n)
			return n;
		return func(b,n/b)+(n%b);
	}
}

大変申し訳ないんですが理解をしているかと言われると微妙なのでコメントアウトだけで許してください･･･。

感想

A:易しい。
B:まぁまぁ易しい。
C:dpに慣れていないとかなり厳しい。
D:難 し い 。
って感じでした。

4問体制の時のD超難しいですね･･･。勉強しがいがあるけど、理解するのが大変だなぁ･･･。