ABC269A～Eの解答[Java]

はじめに

今回は初の5完でしたので、Eまで載せようと思います。

では、見ていきましょう。

A - Anyway Takahashi

問題文はこちら

問題文そのままですね。

A.java

class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//各値の受け取り
		int a = System.in.nextInt();
		int b = System.in.nextInt();
		int c = System.in.nextInt();
		int d = System.in.nextInt();

		//計算結果の出力
		System.out.println((a+b)*(c-d));

		//Takahashiの出力
		System.out.println("Takahashi");
 
		System.out.close();
	}
}

高橋君･･･。

B - Rectangle Detection

問題文はこちら

Cの場所を全探索してから芋づる的にD、A、Bの場所を探しました。
二重for文で#の始まりを探し、Cを決定したらDを探し、Dが決定したらforを一つだけ抜けてA、Bを探しました。

B.java

class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//Sの受け取り
		char[][] S = System.in.nextCharArray(10);

		//各変数の初期化
		int A=0,B=0,C=0,D=0;

		//Cの場所の探索
		for(int i=0;i<10;i++){
			int temp = -1;
			for(int j=0;j<10;j++){
				//Cの場所を見つけた？
				if(S[i][j]=='#'){
					temp = j;
					C = D = j+1;

					//Dを探す
					while(D<10&&S[i][D]=='#')D++;
					break;
				}
			}

			//Cが見つかった？
			if(temp!=-1){
				A = B = i+1;

				//Bを探す
				while(B<10&&S[B][temp]=='#')B++;
				break;
			}
		}

		//答えの出力
		System.out.println(A+" "+B);
		System.out.println(C+" "+D);
 
		System.out.close();
	}
}

最初バグらせてちょっと余計なことしちゃったなぁ･･･って感じでした。ペナルティが重い･･･。

C - Submask

問題文はこちら

bit全探索みたいに解きました。
まず、1の箇所を下から順に探してArrayListに加えていきます。後はbit全探索の要領で解けば良いです。

C.java

class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//Nの受け取り
		long N = System.in.nextLong();

		//1の箇所を記録するリスト
		ArrayList<Integer> list = new ArrayList<Integer>();

		//各位を調べる
		int temp = 0;
		while(temp<60){
			if((N&(1L<<temp))!=0)
				list.add(temp);
			temp++;
		}

		//bit全探索
		for(int i=0;i<(1<<list.size());i++){
			long tmp = 0;
			int num = 1,index = 0;

			//iを元に値を構成
			while(num<1<<list.size()){
				if((i&num)!=0)
					tmp += 1L<<list.get(index);
				num <<= 1;
				index++;
			}

			//出力
			System.out.println(tmp);
		}
 
		System.out.close();
	}
}

公式解説の解法2に近い解答ですが、解法1の方がとてもわかりやすいんじゃないかなぁと個人的には思います。

D - Do use hexagon grid

問題文はこちら

再帰DFSで解きました。
boolean型配列ですでに調べたかどうかを管理しておき、まだ調べていないマスがあれば答えに1加算してDFSで隣接しているマスを全てtrueにすることで、隣接しているマスを除くことができます。

D.java

class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//N、黒く塗られた箇所の受け取り
		int N = System.in.nextInt();
		int[][] list = System.in.nextInt(N,2);

		//確認済みか管理する配列
		boolean[] checked = new boolean[N];

		//答えを数える変数
		int answer = 0;
		for(int i=0;i<N;i++){

			//すでにDFSで探索済みならスキップ
			if(checked[i])
				continue;

			//dfsで連結している箇所を全てtrueに
			checked[i] = true;
			dfs(i,list,checked);

			//新しい連結成分として加算
			answer++;
		}

		//答えの出力
		System.out.println(answer);
 
		System.out.close();
	}

	//DFS
	public static void dfs(int now,int[][] list,boolean[] checked){

		//今の座標を記録
		int x = list[now][0];
		int y = list[now][1];

		//全探索
		for(int i=0;i<list.length;i++){

			//すでに調べたならスキップ
			if(checked[i])
				continue;

			//差を求める
			int subx = list[i][0]-x;
			int suby = list[i][1]-y;

			//隣接条件に合うならtrueにしてdfs
			if(subx==-1&&(suby==-1||suby==0)){
				checked[i] = true;
				dfs(i,list,checked);
			}else if(subx==0&&(suby==-1||suby==1)){
				checked[i] = true;
				dfs(i,list,checked);
			}else if(subx==1&&(suby==0||suby==1)){
				checked[i] = true;
				dfs(i,list,checked);
			}
		}
	}		
}

比較的易しいかなと感じました。

E - Last Rook

問題文はこちら

二分探索で解きました。
a=1、b=N、c=(a+b)/2として、? 1 N a cを出力し、返ってきた値ansがc-a+1未満だったらa=c+1、違うならb=c-1と更新しながらルークが置ける場所を探しました(? a c 1 Nの時も同様です)。

E.java

class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//Nの受け取り
		int N = System.in.nextInt();

		//各変数初期化
		int aX = 1;
		int bX = N;
		int aY = 1;
		int bY = N;
		int X = 1,Y = 1;

		//x座標の二分探索
		while(aX-bX<=0){
			int c = (aX+bX)/2;
			System.out.println("? "+X+" "+c+" "+1+" "+N);
			System.out.flush();
			int ans = System.in.nextInt();

			//上記の通りに値更新
			if(ans<c-X+1)
				bX = c-1;
			else
				aX = X = c+1;
		}

		//yも同様に
		while(aY-bY<=0){
			int c = (aY+bY)/2;
			System.out.println("? "+1+" "+N+" "+Y+" "+c);
			System.out.flush();
			int ans = System.in.nextInt();
			if(ans<c-Y+1)
				bY = c-1;
			else
				aY = Y = c+1;
		}

		//答えの出力
		System.out.println("! "+X+" "+Y);
 
		System.out.close();
	}
}

最初!を出力し忘れてペナルティを頂いてしまいました･･･悔しい･･･。

感想

A:易しい(Takahashiの意味は･･･？)
B:ちょっとバグらせてしまった･･･。
C:ちょっと身構えてしまったが、そこまで難しくはなかった。いろいろ解法があるそう。
D:そんな難しくはなかったが、実装に時間をかけすぎてしまった。
E:制約と「質問を20回まで行うことができます」から二分探索では？って思えた。良かった･･･。
って感じでした。

実装バグらせたり解法がなかなか思いつかなかったりで、そんなにパフォーマンスは大きくなかったです。悔しい･･･。