0
Help us understand the problem. What are the problem?

posted at

updated at

ABC239A~Dの解答[Java]

はじめに

今回のコンテストはAからDまで全て灰レベルの問題(ちなみにEから緑以上になります)なので、比較的簡単に実装できます。多分。
なお、今回のコードは私が競プロを初めてまだ一週間も経っていない(ratedでコンテスト参加をまだ経験していない)時のコードなので昔提出したものと(書き換えられる場所があれば)ちょっと書き換えたものを載せたいと思います。

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

A - Horizon

問題文はこちら

普通にdouble型で受け取って問題文の数式の通りに計算してやればACが取れます。
このコードでは誤差を恐れてちょっと面倒な処理をしています。

A.java
import java.io.*;
class Main{
  public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //値の取得(大きい数字だとバグると思ってたので10000で割った)
    double H = (double)Integer.parseInt(br.readLine()) / 10000.0;
    //数式の計算
    double ans = Math.sqrt(H*(1280.0+H));
    //元の大きさに戻す
    System.out.println(ans*10000.0);
  }
}

やっぱりかなり面倒なコードだったので以下のように書き換えました。

A改.java
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    //値の取得(sqrt内の計算でオーバーフローしないようにlong)
    long H = sc.nextLong();
    //計算して出力
    System.out.println(Math.sqrt(H*(12800000+H)));
  }
}

こっちの方がすっきりしてますね。

B - Integer Division

問題文はこちら

正の数なら普通に整数型を10で割れば勝手に切り捨ててくれるのでいいんですが、負の数だと0側に丸められてしまう(つまり切り上げされてしまう)ので、その対策をしました。

B.java
import java.io.*;
class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //値の取得
		long num = Long.parseLong(br.readLine());
        //負の値?
		if(num<0){
            //ぴったり10の倍数か調べる
			int num2 = (int)(Math.abs(num) % 10);
			if(num2!=0)
				num-=10; //1の位が0じゃないなら-10して整形
		}
        //10で割って出力
		long ans = num / 10;
		System.out.println(ans);
	}
}

なぜか丁寧にキャストしてますがnum2の右辺はそのままで大丈夫です。
ただ、ifをネストするなら&&でまとめた方が良い気がします。

B改.java
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        //値の取得
		long num = sc.nextLong();
        //普通に割ると値がズレるものか?
        if(num<0&&(num%10)!=0)
            num -= 10;
        //10で割ったものを出力
		System.out.println(num/10);
	}
}

C - Knight Fork

問題文はこちら

それぞれの位置から考えられる場所を探して・・・なんてやっていたら実装がめんどくさいので、他の方法で実装しましょう。(x1,y1)=(0,0)の時に(x2,y2)が取り得る場所を考えると以下の位置しか存在しません。
(0,0)(0,±2)(0,±4)
(±1,±1)(±1,±3)
(±2,0)(±2,±4)
(±3,±1)(±3,±3)
(±4,0)(±4,±2)
(±は任意の符号)
従って、|x1-x2|と|y1-y2|が上記の中にあるか調べれば答えが出ます。

C.java
import java.io.*;
class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //変数の準備
		int x1;
		int x2;
		int y1;
		int y2;
        //一行まるごと取得
		String str1 = br.readLine();
        //まだ慣れていなかったので空白が半角か全角かわからなかった
		String[] str = str1.split(" ");
		if(str.length==1)
			str = str1.split("	");
        //それぞれの値を格納
		x1 = Integer.parseInt(str[0]);
		y1 = Integer.parseInt(str[1]);
		x2 = Integer.parseInt(str[2]);
		y2 = Integer.parseInt(str[3]);
        //x、yの差の絶対値
		int x = Math.abs(x1-x2);
		int y = Math.abs(y1-y2);
        //条件に合ったものか?
		if((x==0&&(y==0||y==2||y==4))||((x==1||x==3)&&(y==1||y==3))||(x==2&&(y==0||y==4))||(x==4&&(y==0||y==2)))
			System.out.println("Yes");
        //条件のもの以外は全てNo
		else
			System.out.println("No");
	}
}

当時はScannerクラスを知らなかったのでよくわからない実装をしていますが、Scannerクラスを使う+ちょっと整形すればこんな感じになります。

C改.java
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        //値の取得
		int x1 = sc.nextInt();
		int x2 = sc.nextInt();
		int y1 = sc.nextInt();
		int y2 = sc.nextInt();
        //x、yの差の絶対値を格納
		int x = Math.abs(x1-x2);
		int y = Math.abs(y1-y2);
        //条件に合っているか?
		if(
           (x==0&&(y==0||y==2||y==4))||  //(0,0)(0,±2)(0,±4)
          ((x==1||x==3)&&(y==1||y==3))|| //(±1,±1)(±1,±3)(±3,±1)(±3,±3)
           (x==2&&(y==0||y==4))||        //(±2,0)(±2,±4)
           (x==4&&(y==0||y==2))          //(±4,0)(±4,±2)
        )
			System.out.println("Yes");
        //条件外はNo
		else
			System.out.println("No");
	}
}

正直「自分天才か???」って思ってしまいました。E以降が解けていないのだから凡人ですね・・・。

D - Prime Sum Game

問題文はこちら

高橋君も青木君も選べる数値は100以下なので、200までの素数表を事前に作りました。高橋君が選べる整数iに対して、青木君が選べる整数jを順に見ていってi+jが素数になり得る場合を全て探索して、一つでも青木君が素数にできない箇所があれば高橋君が、全てにおいて青木君が素数を作れるなら青木君が勝てると出力するように実装しました。

D.java
import java.io.*;
import java.util.*;
//文字列を数値に変換するだけのクラス
class SubMain{
	public int[] parsingInt(String someInt){
		int[] fourInt = new int[4];
		String[] str = someInt.split(" ");
		fourInt[0] = Integer.parseInt(str[0]);
		fourInt[1] = Integer.parseInt(str[1]);
		fourInt[2] = Integer.parseInt(str[2]);
		fourInt[3] = Integer.parseInt(str[3]);
		return fourInt;
	}
}
class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //値の取得
		SubMain sm = new SubMain();
		int[] ABCD = sm.parsingInt(br.readLine());
        //素数表の準備
		int[] PrimeTable = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
				    43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
				    101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
				    151, 157, 163, 167, 173, 179, 181, 191, 193, 197};
        //高橋君が選べる値の種類
		int TakahashiCanSelect = ABCD[1] - ABCD[0] + 1;
        //青木君が素数を作れる数値が選べるパターンの数
		int AokiCanSelect = 0;
        //1から順に見ていく
		for(int i=1;i<=100;i++){
            //高橋君が選び得る数値を超えたか?
			if(i>ABCD[1])
				break;
            //高橋君が選び得る数値ではない?
			else if(i<ABCD[0])
				continue;
            //青木君の選べる値を順に試行
			for(int j=ABCD[2];j<=ABCD[3];j++){
				int check = i + j;
				boolean breaker = false;
                //i+jが素数表にあるか?
				for(int k=0;k<PrimeTable.length;k++){
					if(PrimeTable[k]==check){
                        //素数表にあったなら青木君が選べるパターンに1を加算
						AokiCanSelect++;
						breaker = true;
						break;
					}
				}
                //あったなら高橋君の次の数の試行へ
				if(breaker)
					break;
			}
		}
        //一個でも選べないパターンがあったか?
		if(TakahashiCanSelect>AokiCanSelect)
			System.out.println("Takahashi");
        //全整数で対応可能なら青木君の勝ち
		else
			System.out.println("Aoki");
	}
}

見苦しいコードですね・・・。方針そのままでも大幅に記述を変えられそうです。

D改.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[] PrimeTable = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
				    43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
				    101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
				    151, 157, 163, 167, 173, 179, 181, 191, 193, 197};
        //Aから順に見ていく
		for(int i=A;i<=B;i++){
            //素数にならないケースがあるかbooleanで管理
            boolean cannotSelect = true;
            //青木君の選べる値を順に試行
			for(int j=C;j<=D;j++){
				int check = i + j;
                //i+jが素数表にあるか?
				for(int k=0;k<PrimeTable.length;k++){
					if(PrimeTable[k]==check){
                        //素数表にあったなら試行続行
						cannotSelect = false;
						break;
					}
				}
			}
            //上手く選べないなら高橋君の方が勝つ
			if(cannotSelect){
				System.out.println("Takahashi");
                System.exit(0);
            }
		}
        //全整数で対応可能なら青木君の勝ち
		System.out.println("Aoki");
	}
}

ScannerクラスよりもBufferedReaderクラスを利用した方が速いんですが、これくらいの数値ならScannerクラスでも特に問題はありません。JavaでFastest目指すなら話は別ですが。

総評

A:小数の誤差に気をつけたい
B:仕様さえわかっていれば特に悩まない
C:正統法がいまいち理解できていないけど、下手に計算するよりは比較だけで済むのでこっちの解法の方が好き
D:数値が小さいのでこの方法をとったが、ある程度大きい数字ならエラトステネスのふるいで素数判定した方が良さそう
って感じでした。
Eから聞き馴染みのない単語(根付き木とか)が出てくるので避けていますが、解けそうになったら順次載せていきます。

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
0
Help us understand the problem. What are the problem?