ABC253A～Dの解答[Java]

※2022/10/17 E追記しました

はじめに

A、Bはコンテスト中に解いたコードなのでちょっと汚いかもしれませんがご了承ください(C、Dも多分汚いですが…)。

それでは解説していきます。

A - Median?

問題文はこちら

コンテスト中はなんだかよくわからなかったのですが、とりあえず間にあるか判断すれば良いと思ったのでそれに合った条件文を書きました。

A.java

import java.io.*;
class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw = new PrintWriter(System.out);

	public static void main(String[] args)throws IOException{
        //A、B、C取得
		String[] str = reads();
		int A = Integer.parseInt(str[0]),B = Integer.parseInt(str[1]),C = Integer.parseInt(str[2]);
        //Bはちょうど真ん中？
		if(A>=B&&C<=B||A<=B&&C>=B)
			println("Yes");
		else
			println("No");
		exit();
	}
	/*テンプレ一覧
		・String[] reads()  ：一行分を空白区切りで取得(String型配列)
		・void println(何か)：改行あり出力(引数無しも可)
		・void exit()       ：出力のflush
	*/
	public static String[] reads()throws IOException{return br.readLine().split(" ");}
	public static void println(Object T){pw.println(T);}
	public static void exit(){pw.flush();}
}

あとから思いましたが、Bだけ他の変数に突っ込んでおいてABCで構成された配列をソート、Bが最初と同じ位置かを調べるってのが良さそうですね…。

B - Distance Between Tokens

問題文はこちら

oを探して、見つかったらx、yに座標を格納、もう一回見つかったらxに|x-x'|、yに|y-y'|を格納してx+yを出力してやれば良いですね。

B.java

import java.io.*;
class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw = new PrintWriter(System.out);

	public static void main(String[] args)throws IOException{
        //H、Wの取得
		String[] temp = reads();
		int H = Integer.parseInt(temp[0]);
		int W = Integer.parseInt(temp[1]);
        //盤面の準備
		String[][] map = new String[H][W];
		for(int i=0;i<H;i++){
			map[i] = readSplit();
		}
        //初期値
		int x = 0;
		int y = 0;
        //盤面全探索
		for(int i=0;i<map.length;i++){
			for(int j=0;j<map[i].length;j++){
                //駒があるところ？
				if(map[i][j].equals("o")){
                    //差を格納
					x = Math.abs(x-i);
					y = Math.abs(y-j);
				}
			}
		}
        //合計を出力
		println(x+y);
		exit();
	}
	/*テンプレ一覧
		・String[] readSplit()：一行分を一文字ずつ取得(String型配列)
		・String[] reads()    ：一行分を空白区切りで取得(String型配列)
		・void println(何か)  ：改行あり出力(引数無しも可)
		・void exit()         ：出力のflush
	*/
	public static String[] readSplit()throws IOException{return br.readLine().split("");}
	public static String[] reads()throws IOException{return br.readLine().split(" ");}
	public static void println(Object T){pw.println(T);}
	public static void exit(){pw.flush();}
}

この距離をマンハッタン距離とか言うらしいですね。初耳でした。

C - Max - Min Query

問題文はこちら

単純に一番大きいのを～とかソートして～なんてやってたらTLEです。ということで、Javaのmapの中にあるTreeMapを使ってやりましょう。

C.java

import java.io.*;
import java.util.*;
class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw = new PrintWriter(System.out);

	public static void main(String[] args)throws IOException{
        //情報格納用map
		TreeMap<Integer,Integer> S = new TreeMap<Integer,Integer>();
        //Qの取得
		int Q = readInt();
        //順に見ていく
		for(int i=0;i<Q;i++){
            //値の取得(一列分まるごと)
			String[] temp = reads();
            //情報二つ(1)？
			if(temp.length==2){
                //xを格納
				int x = Integer.parseInt(temp[1]);
                //初めて入れる数字なら新しく登録
				if(S.get(x)==null)
					S.put(x,1);
                //すでに入ってるなら情報更新
				else
					S.replace(x,S.get(x)+1);
			}
            //情報三つ(2)？
			else if(temp.length==3){
                //xを格納
				int x = Integer.parseInt(temp[1]);
                //無いけど、一応xが見つからなかったとき用
				if(S.get(x)==null)
					continue;
                //xの個数からcを引く
				int subtract = S.get(x)-Integer.parseInt(temp[2]);
                //cが現在の個数より大きかったか？
				if(subtract<=0)
					S.remove(x);
                //現在の個数がcより大きいなら情報更新
				else
					S.replace(x,subtract);
			}
            //3？
			else
				println(S.lastKey()-S.firstKey()); //最初と最後が最小最大なのでその差を出力
		}
		exit();
	}
	/*テンプレ一覧
		・int readInt()     ：int型取得(行まるごと)
		・String[] reads()  ：一行分を空白区切りで取得(String型配列)
		・void println(何か)：改行あり出力(引数無しも可)
		・void exit()       ：出力のflush
	*/
	public static int readInt()throws IOException{return Integer.parseInt(br.readLine());}
	public static String[] reads()throws IOException{return br.readLine().split(" ");}
	public static void println(Object T){pw.println(T);}
	public static void exit(){pw.flush();}
}

初めてTreeMap使いました。勝手に昇順にしてくれてるのはありがたいですね。

D - FizzBuzz Sum Hard

問題文はこちら

がっつり数学的な問題ですが、
Nの総和 - Aの倍数の総和 - Bの倍数の総和 + lcm(A,B)の倍数の総和
で答えが出ます。

D.java

import java.io.*;
class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw = new PrintWriter(System.out);
 
	public static void main(String[] args)throws IOException{
        //N、A、Bを取得
		String[] str = reads();
		long N = Long.parseLong(str[0]);
		long A = Long.parseLong(str[1]);
		long B = Long.parseLong(str[2]);
        //NよりAかBが大きいとき用の専用対策
		if(N<B){
			if(N<A){
				println((N*(N+1))/2);
			}
			else{
				long Asum = A*(((N/A)*(N/A+1))/2);
				println((N*(N+1))/2-Asum);
			}
		}
		else if(N<A){
			long Bsum = B*(((N/B)*(N/B+1))/2);
			println((N*(N+1))/2-Bsum);
		}
        //AとBが違くてA、B<Nのとき
		else if(A!=B){
			long Asum = A*(((N/A)*(N/A+1))/2);
			long Bsum = B*(((N/B)*(N/B+1))/2);
			long AB = lcm(A,B);
			long ABsum = AB*(((N/(AB))*(N/(AB)+1))/2);
			long removes = Asum+Bsum-ABsum;
			println((N*(N+1))/2-removes);
		}
        //A=Bのとき
		else{
			long Asum = A*(((N/A)*(N/A+1))/2);
			println((N*(N+1))/2-Asum);
		}
		exit();
	}

	/*テンプレ一覧
		・String[] reads()  ：一行分を空白区切りで取得(String型配列)
		・void println(何か)：改行あり出力(引数無しも可)
		・void exit()       ：出力のflush
		・long lcm(整数二つ)：最小公倍数
	*/
	public static String[] reads()throws IOException{return br.readLine().split(" ");}
	public static void println(Object T){pw.println(T);}
	public static void exit(){pw.flush();}
	public static long lcm(long a,long b){return a*b/gcd(a,b);}
}

コンテスト中は最小公倍数という頭にならなくてずっとA*Bをしてました…。悲しい…。

総評

A：簡単。
B：個人的にMath.abs(x-i)は上手かったなとちょっと思ってる(自惚れかもしれないけど…)。
C：気を抜くとTLEになる。新しく機能が知れて良かった。
D：ドツボにハマると抜け出せない。注意深く確認する必要がある。
って感じでした。

案外いけそうで一筋縄ではいかない、良い問題ばかりでしたね。

追記(E - Distance Sequence)

問題文はこちら

特に工夫せず$i$個目に$j$を選んだ時の条件を満たす総数を$dp[i][j]$として保持すると、$dp[i][j]$を求めるのに$O(M)$かかりますので全体として$O(NM^2)$となり間に合いません。そこで、$i$個目に$j$以下を選んだ時の条件を満たす総数(つまり累積和)を$sum[i][j]$として保持すれば$sum[i][j]$をO(1)で求めることができ、高速に解を求めることが出来ます。

E.java

class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	//何となくここに書いた
	final private static int mod = 998244353;
 
	public static void main(String[] args){
 
		//N、M、Kの受け取り
		int N = System.in.nextInt();
		int M = System.in.nextInt();
		int K = System.in.nextInt();
 
		//sum[i]:i以下を選んだ時の個数
		long[] sum = new long[M+1];

		//最初はどの数字を選んでも良いのでsum[i]=iにしておく
		for(int i=1;i<=M;i++){
			sum[i] = sum[i-1]+1;
		}

		//N個目まで順に見ていく
		for(int i=1;i<N;i++){

			//遷移用
			long[] next = new long[M+1];

			//遷移
			for(int j=1;j<=M;j++){

				//A_i-A_(i+1)が-K以下の個数
				int index1 = Math.max(0,j-K);
				long temp1 = sum[index1];

				//A_i-A_(i+1)がK以上の個数
				int index2 = Math.min(M,j+Math.max(1,K)-1);
				long temp2 = sum[M]-sum[index2];

				//総和と一個下の値の和を代入
				next[j] = temp1+temp2;
				next[j] += next[j-1];
				next[j] %= mod;
			}

			//sumに移す
			sum = next;
		}

		//引き算が遷移にあるので負数になる場合がある
		System.out.println(sum[M]<0?sum[M]+mod:sum[M]);
 
		System.out.close();
	}
}

気づきさえすれば悩まなそうです。気付けば、ですが･･･。