Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@viral_8

ABC302A～Fの解答[Java]

Posted at

はじめに

今回はFまで解けたのでそれを載せようと思います。

では見ていきましょう。

A - Attack

問題文はこちら

$\lceil \frac{A}{B} \rceil$が答えですね。

A.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//A、Bの受け取り
		long A = sc.nextLong();
		long B = sc.nextLong();

		//切りあげ
		out.println((A+B-1)/B);
 
		out.close();
	}
	
}

A問題で、intで扱えない問題に遭遇した記憶が無かったのでびっくりしました。

B - Find snuke

問題文はこちら

愚直に探しました。

B.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//H、W、Sの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		char[][] S = sc.nextCharArray(H);

		//答えを入れるようの配列
		int[][] ans = new int[5][2];

		String snuke = "snuke";

		Search:for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){

				//右
				if(j<W-4){
					boolean isSnuke = true;
					for(int k=0;k<5;k++)
						isSnuke &= snuke.charAt(k)==S[i][j+k];
					if(isSnuke){
						ans[0] = new int[]{i+1,j+1};
						ans[1] = new int[]{i+1,j+2};
						ans[2] = new int[]{i+1,j+3};
						ans[3] = new int[]{i+1,j+4};
						ans[4] = new int[]{i+1,j+5};
						break Search;
					}
				}

				//下
				if(i<H-4){
					boolean isSnuke = true;
					for(int k=0;k<5;k++)
						isSnuke &= snuke.charAt(k)==S[i+k][j];
					if(isSnuke){
						ans[0] = new int[]{i+1,j+1};
						ans[1] = new int[]{i+2,j+1};
						ans[2] = new int[]{i+3,j+1};
						ans[3] = new int[]{i+4,j+1};
						ans[4] = new int[]{i+5,j+1};
						break Search;
					}
				}

				//右下
				if(i<H-4&&j<W-4){
					boolean isSnuke = true;
					for(int k=0;k<5;k++)
						isSnuke &= snuke.charAt(k)==S[i+k][j+k];
					if(isSnuke){
						ans[0] = new int[]{i+1,j+1};
						ans[1] = new int[]{i+2,j+2};
						ans[2] = new int[]{i+3,j+3};
						ans[3] = new int[]{i+4,j+4};
						ans[4] = new int[]{i+5,j+5};
						break Search;
					}
				}

				//左
				if(3<j){
					boolean isSnuke = true;
					for(int k=0;k<5;k++)
						isSnuke &= snuke.charAt(k)==S[i][j-k];
					if(isSnuke){
						ans[0] = new int[]{i+1,j+1};
						ans[1] = new int[]{i+1,j};
						ans[2] = new int[]{i+1,j-1};
						ans[3] = new int[]{i+1,j-2};
						ans[4] = new int[]{i+1,j-3};
						break Search;
					}
				}

				//上
				if(3<i){
					boolean isSnuke = true;
					for(int k=0;k<5;k++)
						isSnuke &= snuke.charAt(k)==S[i-k][j];
					if(isSnuke){
						ans[0] = new int[]{i+1,j+1};
						ans[1] = new int[]{i,j+1};
						ans[2] = new int[]{i-1,j+1};
						ans[3] = new int[]{i-2,j+1};
						ans[4] = new int[]{i-3,j+1};
						break Search;
					}
				}

				//左上
				if(3<i&&3<j){
					boolean isSnuke = true;
					for(int k=0;k<5;k++)
						isSnuke &= snuke.charAt(k)==S[i-k][j-k];
					if(isSnuke){
						ans[0] = new int[]{i+1,j+1};
						ans[1] = new int[]{i,j};
						ans[2] = new int[]{i-1,j-1};
						ans[3] = new int[]{i-2,j-2};
						ans[4] = new int[]{i-3,j-3};
						break Search;
					}
				}

				//左下
				if(i<H-4&&3<j){
					boolean isSnuke = true;
					for(int k=0;k<5;k++)
						isSnuke &= snuke.charAt(k)==S[i+k][j-k];
					if(isSnuke){
						ans[0] = new int[]{i+1,j+1};
						ans[1] = new int[]{i+2,j};
						ans[2] = new int[]{i+3,j-1};
						ans[3] = new int[]{i+4,j-2};
						ans[4] = new int[]{i+5,j-3};
						break Search;
					}
				}

				//右上
				if(3<i&&j<W-4){
					boolean isSnuke = true;
					for(int k=0;k<5;k++)
						isSnuke &= snuke.charAt(k)==S[i-k][j+k];
					if(isSnuke){
						ans[0] = new int[]{i+1,j+1};
						ans[1] = new int[]{i,j+2};
						ans[2] = new int[]{i-1,j+3};
						ans[3] = new int[]{i-2,j+4};
						ans[4] = new int[]{i-3,j+5};
						break Search;
					}
				}
			}
		}

		//全探索で見つかったものを出力
		out.println(ans);
 
		out.close();
	}
}

8方向全部書くのを忘れてペナルティを頂いてしまいました…。

C - Almost Equal

問題文はこちら

全探索しました。
C++のnext_permutationに相当するものがないのでそれっぽいメソッド作って実装しました。

C.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、M、Sの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		String[] S = sc.next(N);

		//順列の準備
		int[] perm = new int[N];
		Arrays.setAll(perm,i->i);

		//良い並べ替えが存在するか
		boolean canSort = false;

		//全探索
		do{
			boolean allGood = true;
			for(int i=1;i<N;i++){
				int count = 0;
				for(int j=0;j<M;j++)
					if(S[perm[i]].charAt(j)!=S[perm[i-1]].charAt(j))
						count++;
				allGood &= count<2;
			}
			canSort |= allGood;
		}while(nextP(perm));

		//見つかった？
		out.println(canSort?"Yes":"No");
 
		out.close();
	}

	//next_permutation相当のメソッド
	private static boolean nextP(int[] array){
		int index = -1;
		for(int i=1;i<array.length;i++){
			if(array[i-1]<array[i])
				index = i-1;
		}
		if(index==-1)
			return false;
		int[] arr = new int[array.length-index];
		System.arraycopy(array,index,arr,0,arr.length);
		ArrayFunction.sort(arr);
		int index2 = Searcher.overSearch(arr,array[index]);
		array[index] = arr[index2];
		int index3 = index+1;
		for(int i=0;i<arr.length;i++){
			if(i==index2)
				continue;
			array[index3++] = arr[i];
		}
		return true;
	}
}

ミスってないか不安でしたが通って良かったです。

D - Impartial Gift

問題文はこちら

$A$、$B$共にソートして大きい方から見て答えを探しました。

D.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、M、D、A、Bの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		long D = sc.nextLong();
		long[] A = sc.nextLong(N);
		long[] B = sc.nextLong(M);

		//ソート
		ArrayFunction.sort(A);
		ArrayFunction.sort(B);

		//後ろから見ていく
		int indexA = N-1;
		int indexB = M-1;
		while(0<=indexA&&0<=indexB&&Math.abs(A[indexA]-B[indexB])>D){
			if(A[indexA]>B[indexB])
				indexA--;
			else
				indexB--;
		}

		//解があったらそれを、無ければ-1
		out.println(0<=indexA&&0<=indexB?A[indexA]+B[indexB]:-1);
 
		out.close();
	}
	
}

これは比較的速く解けました。

E - Isolation

問題文はこちら

直接結ばれている頂点のみを保持していれば良いので、ArrayList<TreeSet<Integer>>で保持してシミュレーションしました。

E.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、Qの受け取り
		int N = sc.nextInt();
		int Q = sc.nextInt();

		//直接結ばれている頂点を管理する用
		ArrayList<TreeSet<Integer>> list = new ArrayList<>();
		for(int i=0;i<=N;i++)
			list.add(new TreeSet<>());

		//現状の答え
		int ans = N;

		while(Q-->0){

			int q = sc.nextInt();

			//クエリ1
			if(q==1){

				//u、vの受け取り
				int u = sc.nextInt();
				int v = sc.nextInt();

				//答えから引く
				if(list.get(u).size()==0)
					ans--;
				list.get(u).add(v);
				if(list.get(v).size()==0)
					ans--;
				list.get(v).add(u);
			}

			//クエリ2
			else{

				//vの受け取り
				int v = sc.nextInt();

				//各辺を取り除く
				for(int p:list.get(v)){
					list.get(p).remove(v);
					if(list.get(p).size()==0)
						ans++;
				}

				//辺が元々あったら答えに加算する
				if(list.get(v).size()>0)
					ans++;
				list.get(v).clear();
			}

			//現状の答えを出力
			out.println(ans);
		}
 
		out.close();
	}
	
}

Eにしては簡単…？

F - Merge Set

問題文はこちら

数字と集合それぞれを頂点としてみて、集合とその集合に含まれている要素に対して辺を貼ってDijkstra法で答えを求めました。

F.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、Mの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

		//隣接リストの構築
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for(int i=0;i<=M;i++)
			list.add(new ArrayList<>());
		for(int i=0;i<N;i++){
			int A = sc.nextInt();
			ArrayList<Integer> temp = new ArrayList<>();
			while(A-->0)
				temp.add(sc.nextInt());
			for(int num:temp)
				list.get(num).add(i+M+1);
			list.add(temp);
		}

		//Dijkstra
		PriorityQueue<Pair<Integer,Integer>> queue = new PriorityQueue<>(
			(p1,p2)->Integer.compare(p1.getValue(),p2.getValue()));
		queue.add(new Pair<>(1,0));
		int[] costs = new int[N+M+2];
		Arrays.fill(costs,Integer.MAX_VALUE);
		costs[1] = 0;
		while(queue.size()>0){
			Pair<Integer,Integer> pair = queue.poll();
			int now = pair.getKey();
			int cost = pair.getValue();
			if(now==M){
				//途中で答えが見つかれば出力して終了
				System.out.println(cost-1);
				return;
			}
			for(int nextP:list.get(now)){
				int nextC = cost;
				if(nextP>M)
					nextC++;
				if(costs[nextP]>nextC){
					costs[nextP] = nextC;
					queue.add(new Pair<>(nextP,nextC));
				}
			}
		}

		//答えが見つからなかったのなら1->Mは不可
		out.println(-1);
 
		out.close();
	}
}

思っていたよりもサクッと解けました。

感想

A:易しい
B:結構沼った…
C:ちょっと重いなと思ったけど比較的簡単
D,E:比較的易しい
F:最初UnionFindとかを考えたおかげでグラフ問題だと早めに気づけた
って感じでした。

普段もFまで解ければ苦労しないんですけどね…維持できるよう頑張ります。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?