ABC249A～Dの解答[Java]

はじめに

このコンテスト中に提出したコードは煩雑なので、基本方針はそのままで訂正・改良したものを解説します。

では、解説していきます。

A - Jogging

問題文はこちら

素直に二人の移動距離を計算して大小を比較しましょう。

A.java

import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        //値の取得
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();
		int E = sc.nextInt();
		int F = sc.nextInt();
		int X = sc.nextInt();
        //歩いて休むを１セット(以下この一連の動作をセットとする)として割ったあまりの時間
		int modT = X%(A+C);
		int modA = X%(D+F);
        //セットの分だけ進んでいるから代入しておく
		int Takahashi = (X/(A+C))*(A*B);
		int Aoki = (X/(D+F))*(D*E);
        //セットにかかる時間で割ったあまりは歩いている時間より短い？
		if(modT<A)
			Takahashi += modT*B; //短いなら単純に速度×時間
		else
			Takahashi += A*B;    //長いなら歩ける時間×速度
        //同様に青木君の方も加算
		if(modA<D)
			Aoki += modA*E;
		else
			Aoki += D*E;
        //比較して出力
		if(Takahashi>Aoki)
			System.out.println("Takahashi");
		else if(Takahashi<Aoki)
			System.out.println("Aoki");
		else
			System.out.println("Draw");
	}
}

実は最初1秒ずつforループと条件文で処理しようとしてバグらせてWA量産しました…。

B - Perfect String

問題文はこちら

大文字と小文字が出現したかをboolean型で管理しましょう。後は順にforループで被っていないか見ていけば十分終わります。

B.java

import java.io.*;
import java.util.*;
import java.util.regex.*;
class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //文字列の取得(splitしてます)
		String[] str = br.readLine().split("");
        //大文字小文字の出現管理用変数
		boolean big = false;
		boolean small = false;
        //先頭から順に全探索
		for(int i=0;i<str.length;i++){
            //大文字？
			if(isAlphabetLarge(str[i]))
				big = true;
            //小文字ならsmall=true
			else
				small = true;
            //自分より後ろに重複した文字があるか探索
			for(int j=i+1;j<str.length;j++){
                //同じ？
				if(str[i].equals(str[j])){
                    //同じなら終了
					System.out.println("No");
					System.exit(0);
				}
			}
		}
        //大文字も小文字も出た？
		if(big&&small)
			System.out.println("Yes");
		else
			System.out.println("No");
	}
    //大文字判定用メソッド(ネットで探して拝借)
    public static boolean isAlphabetLarge(String value) {
        boolean result = false;
        if (value != null) {
            Pattern pattern = Pattern.compile("^[A-Z]+$");
            result = pattern.matcher(value).matches();
        }
        return result;
    }
}

大文字判定をどうすれば良いかわからなくてネット検索しましたが、今思えば普通に
str[i]-'A'<27&&str[i]-'A'>=0
みたいに書けば良かったですね…。

C - Just K

問題文はこちら

DFSみたいな感じの実装ですが、やっていることは全探索です。BFSに今の位置の文字を入れるときと入れないときの二パターンで再帰させるようにして全パターンを調べているのですが、終点にだけ気をつければそんなに実装には苦しみません。

C.java

import java.util.*;
class Main{
    //K、文字列はprocessでも見たいのでクラス変数に
	static int K;
    static boolean[][] str;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        //N、Kの取得
		int N = sc.nextInt();
		K = sc.nextInt();
        //文字列を管理するboolean型配列(a～zが出現するか)
		str = new boolean[26][N];
		for(int i=0;i<N;i++){
            //文字列をchar型として格納
			char[] temp = sc.next().toCharArray();
            //順に出現した文字に対応した箇所をtrueに
			for(int j=0;j<temp.length;j++){
				str[temp[j]-'a'][i] = true;
			}
		}
        //DFSに投げ込む
		int answer = process(0,new int[26]);
        //答えの出力
		System.out.println(answer);
	}
    //DFS用
	public static int process(int pick,int[] now){
        //return用変数
		int ans = 0;
        //文字列を最後まで見終わった？
		if(pick==str[0].length){
            //出現回数がK回の物を探してansに加算
			for(int i=0;i<26;i++){
				if(now[i]==K)
					ans++;
			}
		}
		else{
            //今選んでいる文字列を含まなかった場合
			ans = process(pick+1,now);
            //出現回数管理用配列
			int[] s = new int[26];
			for(int j=0;j<26;j++){
                //文字が出現するなら+1、出てこないならそのままコピー
				s[j] += str[j][pick] ? now[j]+1 : now[j];
			}
            //今を選ばなかったときと選んだときでansが大きい方を格納
			ans = Math.max(process(pick+1,s),ans);
		}
		return ans;
	}
}

本当はbit全探索ってやつを使った方が良いらしいんですが、知識が無かったのでこんな実装です。

D - Index Trio

問題文はこちら

割り算をした結果が整数になる場合なんて考えてたら実装が大変なので、$A_i$、$A_j$を探索するのではなく$A_j$、$A_k$を決めて、それを満たす$A_i$を探しましょう。

D.java

import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        //Nの取得
		int N = sc.nextInt();
        //Aの最大値を格納する変数
		int max = 0;
        //事前に存在し得る数字分の配列を準備(indexにAiをそのまま使いたいので最大値+1の大きさ)
		int[] A = new int[200001];
        //一応0で初期化(やらなくても0にはなっている)
		Arrays.fill(A, 0);
        //数列の取得&最大値を求める
		for(int i=0;i<N;i++){
			int temp = sc.nextInt();
			A[temp]++;
			if(max<temp)
				max = temp;
		}
        //答え用変数
		long answer = 0;
        //Ajに、1から数列にある最大値まで順に格納(変数i)
		for(int i=1;i<=max;i++){
            //最大値/iまでしか調べなくて良いのでそこまで(Aj*Akがmaxを超える場合は存在しない)
			for(int j=1;j<=(max/i);j++){
				answer += (long)A[i]*A[j]*A[i*j]; //出現回数の乗算が可能な組合せの数になる
			}
		}
        //出力
		System.out.println(answer);
	}
}

コンテスト中は気付かなかったです…。indexにそのまま数列の値を突っ込めると-1しなくて良いので楽ですね。

総評

A：簡単ではあるが、実装に注意。
B：大文字小文字の判断に若干戸惑った。
C：全然思いつかなかった。ちょっと難易度高め。
D：実装が上手くいくと気持ち良い問題。楽しい。
って感じでした。

企業コンはやっぱり難しいな…。