ABC258A～Dの解答[Java]

はじめに

今回から自作ライブラリ(テンプレ)が他クラスにまとめられた書き方をしています。ご注意ください。
なお、今回用いたライブラリは別記事にまとめてあります。適宜ご確認ください。

では、コードを見ていきましょう。

A - When?

問題文はこちら

実はprintfの書き方を知らなくて、全部条件分岐しました。

A.java

class Main{
	public static void main(String[] args)throws IOException{
		//テンプレ用オブジェクト
		Library Sys = new Library();
		//Nの受け取り
		int N = Sys.readInt();
		//22時台で0～9分の時用
		if(N>=60&&N>=70){
			Sys.out.println("22:"+(N-60));
		}
		//22時台で10分以降の時用
		else if(N>=60){
			Sys.out.println("22:0"+(N-60));
		}
		//21時台で0～9分の時用
		else if(N<10){
			Sys.out.println("21:0"+N);
		}
		//その他
		else{
			Sys.out.println("21:"+N);
		}
		Sys.out.close();
	}
}

普通に二桁でそろえてやれば超簡潔に書けます。気になる方は調べてみましょう。

B - Number Box

問題文はこちら

二日前ほどにオセロを作っていたということもあり、完全にハマりました。普通に全通り調べてやりましょう。

B.java

class Main{
	public static void main(String[] args)throws IOException{
		//テンプレ用オブジェクト
		Library Sys = new Library();
		//Nの受け取り
		int N = Sys.readInt();
		//Aを3×3に拡張してmodを取る必要を無くす
		int[][] A = new int[N*3][N*3];
		for(int i=0;i<N;i++){
			String[] str = Sys.reads("");
			for(int j=0;j<N;j++){
				A[i][j] = A[i][j+N] = A[i][j+N*2] = 
				A[i+N][j] = A[i+N][j+N] = A[i+N][j+N*2] = 
				A[i+N*2][j] = A[i+N*2][j+N] = A[i+N*2][j+N*2] = Integer.parseInt(str[j]);
			}
		}
		//答え用変数
		long answer = 0;
		for(int i=N;i<N*2;i++){
			//全方向探索
			for(int j=N;j<N*2;j++){
				long temp = A[i][j];
				for(int k=1;k<N;k++){
					temp = temp*10+A[i][j+k];
				}
				long temp2 = A[i][j];
				for(int k=1;k<N;k++){
					temp2 = temp2*10+A[i+k][j];
				}
				temp = Math.max(temp,temp2);
				temp2 = A[i][j];
				for(int k=1;k<N;k++){
					temp2 = temp2*10+A[i-k][j];
				}
				temp = Math.max(temp,temp2);
				temp2 = A[i][j];
				for(int k=1;k<N;k++){
					temp2 = temp2*10+A[i][j-k];
				}
				temp = Math.max(temp,temp2);
				temp2 = A[i][j];
				for(int k=1;k<N;k++){
					temp2 = temp2*10+A[i+k][j+k];
				}
				temp = Math.max(temp,temp2);
				temp2 = A[i][j];
				for(int k=1;k<N;k++){
					temp2 = temp2*10+A[i-k][j-k];
				}
				temp = Math.max(temp,temp2);
				temp2 = A[i][j];
				for(int k=1;k<N;k++){
					temp2 = temp2*10+A[i+k][j-k];
				}
				temp = Math.max(temp,temp2);
				temp2 = A[i][j];
				for(int k=1;k<N;k++){
					temp2 = temp2*10+A[i-k][j+k];
				}
				temp = Math.max(temp,temp2);
				//全方向の中で最高の値はanswer更新に値するか？
				if(temp>answer)
					answer = temp;
			}
		}
		Sys.out.println(answer);
		Sys.out.close();
	}
}

最大値の場所を記憶しておいてそこから始める、という考え方も良いと思います。ネットで見た感じだと全通りを配列に格納して比較みたいなのもあるそうです。なにそれ面白そう…。

C - Rotation

問題文はこちら

クエリを先読みして、1が連続するときは圧縮しました。あとは読み込みの先頭を1に合わせてずらしてやることで十分時間内に終わります。

C.java

class Main{
	public static void main(String[] args)throws IOException{
		//テンプレ用オブジェクト
		Library Sys = new Library();
		//N、Q、Sの受け取り
		String[] str = Sys.reads(" ");
		int N = Sys.parseInt(str[0]);
		int Q = Sys.parseInt(str[1]);
		String S = Sys.read();
		ArrayList<Integer[]> query = new ArrayList<Integer[]>();
		int temp = 0;
		//クエリ先読み(queryに圧縮して格納)
		for(int i=0;i<Q;i++){
			//一行読み取り
			str = Sys.reads(" ");
			//1のクエリならtempに格納
			if(str[0].equals("1")){
				temp+=Sys.parseInt(str[1]);
			}
			//2のクエリなら1のクエリの分を%Nして格納後、2を方を格納
			else{
				Integer[] tm = {1,(temp%N)};
				query.add(tm);
				temp = 0;
				Integer[] tm2 = {2,Sys.parseInt(str[1])};
				query.add(tm2);
			}
		}
		//文字の先頭が何番目の文字か管理する変数
		temp = 0;
		//substringだと遅いかなぁと思って、事前に配列に変形
		char[] Ssub = S.toCharArray();
		for(int i=0;i<query.size();i++){
			//1ならtempに反映
			if(query.get(i)[0]==1){
				temp += N-query.get(i)[1];
				temp %= N;
			}
			//2なら出力
			else{
				Sys.out.println(Ssub[(query.get(i)[1]-1+temp)%N]);
			}
		}
		Sys.out.close();
	}
}

今思えば別に先読みしなくても良かったかな…って思い始めてます。どうせその後のfor文で圧縮できたし…。

D - Trophy

問題文はこちら

先頭から
①このステージを周回したとき
②このステージをクリアして次に進む
の二択を再帰関数で実装してやれば良いです。証明はわかりませんが、途中を2回クリアして最後を3回クリアみたいな状況は存在し得ません。最短は必ずどこかまでのステージまでクリアしてそこをX回まで周回クリアになります。

D.java

class Main{
	//AとB、答えはdpにも共有したいのでここに
	static int[][] AB;
	static long answer = Long.MAX_VALUE;
	public static void main(String[] args)throws IOException{
		//テンプレ用オブジェクト
		Library Sys = new Library();
		//N、X、A、Bの格納
		String[] str = Sys.reads(" ");
		int N = Sys.parseInt(str[0]);
		int X = Sys.parseInt(str[1]);
		AB = new int[N][2];
		for(int i=0;i<N;i++){
			AB[i] = Sys.readInt(2);
		}
		//先頭から見ていく(結果はanswerに)
		dp(0,X,0);
		//答えを出力
		Sys.out.println(answer);
		Sys.out.close();
	}
	//動的計画法？のような何か
	public static void dp(int number,long x,long cost){
		//最後の一つなら残量分だけクリアする
		if(number==AB.length-1){
			long temp = x*AB[number][1]+AB[number][0]+cost;
			//更新できそう？
			if(temp<answer)
				answer = temp;
			return;
		}
		//今のところを周回クリアしたときを計算
		long temp =x*AB[number][1]+AB[number][0]+cost;
		//更新すべき？
		if(temp<answer)
			answer = temp;
		//まだクリアすべき回数に達していないなら次を参照
		if(x-1>0){
			dp(number+1,x-1,cost+AB[number][0]+AB[number][1]);
		}
	}
}

私はこれを動的計画法だと思っていたのですが、貪欲法って言うんすか？わからないな…。まぁ貪欲法だろうが「貪欲」の「D」と「Process」の「P」を取ってDPってことで…。

総評

A:printf知っていれば即答。知らなくても早く実装はできるようにしておきたい。
B:バグると地獄。私は2回バグりました。
C:割と簡単…？実装さえ手こずらなければ即答したい。
D:ザ・再帰関数っていう感じの問題。茶なら実装できると心強い。
って感じでした。

コンテスト中、Bをバグらせて速攻Cに行ってCもバグらせて、めちゃくちゃ焦りました。落ち着いて取り組むのは非常に大切ですよ！(戒め)