ABC250A～Dの解答[Java]

はじめに

コンテスト中に提出したコード(A～C)はかなり見辛いので一応解説はしますが書き換えられる点を探して書き直した物も載せます。

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

A - Adjacent Squares

問題文はこちら

単純に上下左右にマスが存在するか見ても良いですが、初期値を4にして、a==1,Hを満たすなら-1、b==1,Wを満たすなら-1みたいな感じで絞っていくと範囲外参照とか気にしなくて楽そうです。
※このコードは訂正箇所が特にないのでそのままにします

A.java

import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        ///値の取得
		int H = sc.nextInt();
		int W = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
        //初期値設定
		int answer = 4;
        //条件を満たした分だけ減らす
		if(a==1||a==H)
			answer--;
		if(b==1||b==W)
			answer--;
		if(H==1)
			answer--;
		if(W==1)
			answer--;
        //出力
		System.out.println(answer);
	}
}

ちょっと実装してて楽しかったです。

B - Enlarged Checker Board

問題文はこちら

ちょっと実装に悩みましたが、とりあえず条件文とfor文で処理しました。最初はAで割ったときに奇数か偶数か判断し(下の実装ではA*2で割ったあまりがAより大きいか小さいかで判断している)、同様にBも判断してそれにあった出力をしています。

B.java

import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        //値の取得
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
        //一文字ずつ出力
		for(int i=0;i<N*A;i++){
			for(int j=0;j<N*B;j++){
                //各条件にあった出力をする
				if((i%(A*2))>=A){
					if((j%(B*2))>=B){
						System.out.print(".");
					}
					else{
						System.out.print("#");
					}
				}
				else{
					if((j%(B*2))>=B){
						System.out.print("#");
					}
					else{
						System.out.print(".");
					}
				}
			}
            //改行
			System.out.println();
		}			
	}
}

さすがにこれは書き直したいですね。こんな感じでどうでしょうか。

B.java

import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        //値の取得
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
        //一文字ずつ出力
		for(int i=0;i<N*A;i++){
			for(int j=0;j<N*B;j++){
                //各条件にあった出力をする(商の偶奇をXORで処理)
				if(((i/A%2)^(j/B%2))==1){
						System.out.print("#");
				}
				else{
						System.out.print(".");
				}
			}
            //改行
			System.out.println();
		}			
	}
}

実は初めてXORなるものを使いました。

C - Adjacent Swaps

問題文はこちら

普通にやるとTLEをくらうので、今どこにあるかを他の配列で管理してやれば良いですね。
以下のコードは非常に煩雑なので正直見なくてもいいです。

C.java

import java.util.*;
class Main{
	public static void main(String[] args){
        //値の受け取り
		int N = sc.nextInt();
		int[] A = new int[N+1];
		int[] place = new int[N+1];
        //配列準備
		for(int i=1;i<=N;i++){
			A[i] = i;
			place[i] = i;
		}
        //入れ替える数字の情報の取得
		int Q = sc.nextInt();
		int[] X = new int[Q];
		for(int i=0;i<Q;i++){
			X[i] = sc.nextInt();
		}
        //順に動かしていく
		for(int i=0;i<X.length;i++){
            //端っこ？
			if(place[X[i]-1]+1==A.length){
				int temp = A[place[X[i]-1]];
				A[place[X[i]-1]] = A[place[X[i]-1]-1];
				A[place[X[i]-1]-1] = temp;
				int temp2 = place[A[place[X[i]-1]]-1];
				place[A[place[X[i]-1]]-1] = place[A[place[X[i]-1]-1]-1];
				place[A[place[X[i]-1]-1]-1] = temp2;
			}
            //端じゃないなら普通に
			else{
				int temp = A[place[X[i]-1]];
				A[place[X[i]-1]] = A[place[X[i]-1]+1];
				A[place[X[i]-1]+1] = temp;
				int temp2 = place[A[place[X[i]-1]]-1];
				place[A[place[X[i]-1]]-1] = place[A[place[X[i]-1]+1]-1];
				place[A[place[X[i]-1]+1]-1] = temp2;
			}
		}
        //最終段階を順に出力
		for(int i=0;i<A.length;i++){
			System.out.print(A[i]+" ");
		}
	}
}

汚いコードですね…。変数を使ってまとめましょう。

C.java

import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        //値の受け取り
		int N = sc.nextInt();
		int[] A = new int[N+1];
		int[] place = new int[N+1];
        //配列準備
		for(int i=1;i<=N;i++){
			A[i] = i;
			place[i] = i;
		}
        //入れ替える数字の情報の取得
		int Q = sc.nextInt();
		int[] X = new int[Q];
		for(int i=0;i<Q;i++){
			X[i] = sc.nextInt();
		}
        //順に動かしていく
		for(int i=0;i<X.length;i++){
            //今動かしたいボールがどこにあるかを格納
			int num = X[i];
            int m = place[num];
            //端っこ？
			if(m+1==A.length){
				place[num]--;
				place[A[m-1]]++;
				A[m] = A[m-1];
				A[m-1] = num;
			}
            //端じゃないなら普通に
			else{
				place[num]++;
				place[A[m+1]]--;
				A[m] = A[m+1];
				A[m+1] = num;
			}
		}
        //最終段階を順に出力
		for(int s=1;s<A.length;s++){
			System.out.print(A[s]+" ");
		}
		System.out.println();
	}
}

ちょっとだけすっきりしましたね。

D - 250-like Number

問題文はこちら

単純に探索すると地獄と化します。そこで、p,qが10^6以下の素数であることを利用して事前に素数を求めておいて、とりあえずその範囲内で全探索です。これでいけます。

D.java

import java.io.*;
import java.util.*;
class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args)throws IOException{
        //Nの取得
		long N = Long.parseLong(br.readLine());
        //計算する必要がないならさっさと終了させてしまう
		if(N<54){System.out.println(0);System.exit(0);}
        //素数表を作る
		int[] primes = prime(1000000);
        //答え用変数
		long count = 0;
        //素数の数-1まで探索(p<qより、最後の一個は調べなくて良い)
		for(int i=0;i<primes.length-1;i++){
            //とりあえず格納
			long s = primes[i];
            //sより大きい素数を全探索
			for(int j=i+1;j<primes.length;j++){
                //とりあえず格納
				long t = primes[j];
                //もう探索しなくていい値？
				if(s*Math.pow(t,3)>N) break;
                //条件を満たしてるなら加算
				count++;
			}
		}
        //答えの出力
		System.out.println(count);
	}
    //以下テンプレ(エラトステネスのふるい)
	public static int[] prime(int num){BitSet nums=new BitSet(num+1);nums.set(2,num+1);for(int i=2;i<=Math.sqrt(num);i++)if(nums.get(i))for(int j=i*i;j<=num;j+=i)nums.clear(j);int[] answer=new int[nums.cardinality()];int i=2,index=0;while(true){i=nums.nextSetBit(i);answer[index++]=i++;if(index==answer.length)break;}return answer;}
}

いやぁ…エラトステネスのふるいを改悪してしまっていたせいでコンテスト中は実行時間が長くてTLE出してしまいました。まぁ…テンプレが改良できたから良いか…。

総評

A：C++とかだとtrue,falseの数値変換が簡単なのでより短く書けるそうです。
B：実装にかなり手間取りました。
C：Indexにそのまま番号を使うという考えが無かったのでコンテスト中は解けなかった…。良い勉強になりました。
D：テンプレを改良する良い機会になりました…
って感じでした。

なんかこのコンテスト難しく感じました…。また似たような難易度のがきたらレートを根こそぎ奪われそうです…。