ABC284A～Eの解答[Java]

はじめに

今回はEまで解けたのでコンテスト中に提出したコードを載せようと思います。

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

A - Sequence of Strings

問題文はこちら

配列で受け取って逆順に出力しました。

A.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){

		//N、Sの受け取り 
		int N = System.in.nextInt();
		String[] S = System.in.next(N);

		//逆順で出力
		while(N-->0){
			System.out.println(S[N]);
		}
 
		System.out.close();
	}
}

特に難しくは無いですね。最初普通に昇順で出力するのだと誤読して時間をちょっと食ってしまいました…。

B - Multi Test Cases

問題文はこちら

各要素を2で割ったあまりの和が今回求める値なのでそれを求めて出力しました。

B.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//Tの受け取り
		int T = System.in.nextInt();

		//T回繰り返す
		while(T-->0){

			//Nの受け取り
			int N = System.in.nextInt();

			//各要素を2で割ったあまりの総和を求める
			int ans = 0;
			while(N-->0){
				ans += System.in.nextInt()%2;
			}

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

これもそこまで難しくはないですね。

C - Count Connected Components

問題文はこちら

UnionFindを使って解きました。
実装は以下のような感じになってます。

UnionFind.java

class UnionFind{
	private int[] par,rank,size;
	private int N,count;
	public UnionFind(int N){
		this.N = N;
		count = N;
		par = new int[N];
		rank = new int[N];
		size = new int[N];
		Arrays.fill(par,-1);
		Arrays.fill(size,1);
	}
	public int root(int x){
		if(par[x]==-1)
			return x;
		else
			return par[x] = root(par[x]);
	}
	public boolean isSame(int x,int y){
		return root(x)==root(y);
	}
	public boolean unite(int x,int y){
		int rx = root(x);
		int ry = root(y);
		if(rx==ry)
			return false;
		if(rank[rx]<rank[ry]){
			int temp = rx;
			rx = ry;
			ry = temp;
		}
		par[ry] = rx;
		if(rank[rx]==rank[ry])
			++rank[rx];
		size[rx] += size[ry];
		--count;
		return true;
	}
	public int groupCount(){
		return count;
	}
	public int size(int x){
		return size[root(x)];
	}
}

C.java

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

		//UnionFind
		UnionFind uf = new UnionFind(N);

		//各辺の受け取り
		while(M-->0){
			int u = System.in.nextInt()-1;
			int v = System.in.nextInt()-1;
			uf.unite(u,v);
		}

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

DFSでも解けると思います。こんな感じでしょうか。

C.java

import java.util.Scanner;
import java.util.ArrayList;
class Main{

	//dfsメソッド内でも見れるようここで宣言
	static ArrayList<ArrayList<Integer>> route;
	static boolean[] isPassed;

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//N、Mの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

		//辺の受け取り
		route = new ArrayList<>();
		for(int i=0;i<=N;i++)
			route.add(new ArrayList<>());
		while(M-->0){
			int u = sc.nextInt();
			int v = sc.nextInt();
			route.get(u).add(v);
			route.get(v).add(u);
		}

		isPassed = new boolean[N+1];

		//探索してなければansに1加算してdfs(連結している頂点を全部探索済みにする)
		int ans = 0;
		for(int i=1;i<=N;i++){
			if(isPassed[i])
				continue;
			ans++;
			dfs(i);
		}

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

	//dfs
	public static void dfs(int now){

		//探索済みに
		isPassed[now] = true;

		//この頂点と直接繋がっている頂点で未探索な頂点があればdfs
		for(int next:route.get(now)){
			if(isPassed[next])
				continue;
			dfs(next);
		}
	}
}

そこまで難しくは感じなかったです。

D - Happy New Year 2023

問題文はこちら

$N=p^2q$より、$p$か$q$は$\sqrt[3]{9 \times 10^{18}} \simeq 2 \times 10^6$以下なのでそれを探せば良いと思い、それを実装しました。

D.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//Tの受け取り
		int T = System.in.nextInt();

		//Tケース分答える
		while(T-->0){

			//Nの受け取り
			long N = System.in.nextLong();

			//pかqで小さい方を探す
			for(long p=2;;p++){

				//pの方が見つかればN/p/pがqになる
				if(N%(p*p)==0){
					System.out.println(p+" "+N/p/p);
					break;
				}

				//qの方が見つかればBigInteger.valueOf(N/p).sqrt()がpになる
				if(N%p==0){
					System.out.println(BigInteger.valueOf(N/p).sqrt()+" "+p);
					break;
				}
			}
		}
 
		System.out.close();
	}
}

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

E - Count Simple Paths

問題文はこちら

普通にDFSしても間に合うと思い、DFSで解きました。

E.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	//dfs側でも見れるようここで宣言
	static boolean[] isPassed;
	static ArrayList<HashSet<Integer>> route;
	static int ans = 0;
 
	public static void main(String[] args){
 
		//N、Mの受け取り
		int N = System.in.nextInt();
		int M = System.in.nextInt();

		//各辺の受け取り
		route = new ArrayList<>();
		for(int i=0;i<=N;i++)
			route.add(new HashSet<>());
		while(M-->0){
			int u = System.in.nextInt();
			int v = System.in.nextInt();
			route.get(u).add(v);
			route.get(v).add(u);
		}

		//1のみ探索済みに
		isPassed = new boolean[N+1];
		isPassed[1] = true;

		//dfs
		dfs(1);

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

	//dfs
	public static void dfs(int now){

		//1からnowまでのパスをansに加算
		ans++;

		//最大値以上は探索する必要が無いのでreturn
		if(ans==1_000_000)
			return;

		//nowから直接行ける頂点を探索
		for(int next:route.get(now)){

			//今のパスにあれば調べない
			if(isPassed[next])
				continue;

			//探索済みに
			isPassed[next] = true;

			//dfs
			dfs(next);

			//探索済みを解除
			isPassed[next] = false;

			//最大値に達した？
			if(ans==1_000_000)
				return;
		}
	}
}

最初dfsのところでans==1e6って書いたんですがWA出たので1_000_000にしました。

感想

A,B:易しめ
C:Cにしては易しい(ここ最近いつもこう感じてる気がする)
D:制約的に立方根くらいに落とせるんだろうなぁって思ったらすぐ思いついた。
E:結構易しく感じた。慣れ？
って感じでした。

今回でやっと水色です。やっとだよ…。

追記(F - ABCBAC)

問題文はこちら

rolling hashを用いて解きました。
ちょっと見づらいですけど、差を更新して行く感じで求めてます。なお、modは二つ用意して、衝突することを考慮して衝突したときは実際に比較することで判定しました。

F.java

class Main{

	//底
	static int base = 100;

	//mod二つ
	static final int mod1 = (int)1e9+7;
	static final int mod2 = (int)1e9-1755647;

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

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

		//Tの受け取り
		String T = sc.next();

		//先頭x文字と末尾N-x文字を連結したときのハッシュ値(mod1)
		long S11 = 0;
		//先頭x文字と末尾N-x文字を連結したときのハッシュ値(mod2)
		long S12 = 0;
		//x文字目から末尾N+x-1文字目までを連結して反転した時のハッシュ値(mod1)
		long S21 = 0;
		//x文字目から末尾N+x-1文字目までを連結して反転した時のハッシュ値(mod2)
		long S22 = 0;

		//ハッシュ値の計算(i=N)
		for(int i=0;i<N;i++){
			S11 = (S11*base+T.charAt(i))%mod1;
			S12 = (S12*base+T.charAt(i))%mod2;
			S21 = (S21*base+T.charAt(2*N-i-1))%mod1;
			S22 = (S22*base+T.charAt(2*N-i-1))%mod2;
		}

		//これは条件を満たす？
		if(S11==S21&&S12==S22)
			if(check(T,N,N))
				return;

		//問題文のiはこのiに対するN-iに対応する
		for(int i=1;i<N;i++){

			//差分計算
			//S1はN-i文字目を2N-i文字目に置き換えている
			S11 += mod1-modPow(base,i-1,mod1)*T.charAt(N-i)%mod1;
			S11 %= mod1;
			S11 += modPow(base,i-1,mod1)*T.charAt(2*N-i)%mod1;
			S11 %= mod1;
			S12 += mod2-modPow(base,i-1,mod2)*T.charAt(N-i)%mod2;
			S12 %= mod2;
			S12 += modPow(base,i-1,mod2)*T.charAt(2*N-i)%mod2;
			S12 %= mod2;

			//S2は先頭を消して末尾にN-i文字目を追加する
			S21 = (mod1+S21-modPow(base,N-1,mod1)*T.charAt(2*N-i)%mod1)*base%mod1;
			S21 += T.charAt(N-i);
			S21 %= mod1;
			S22 = (mod2+S22-modPow(base,N-1,mod2)*T.charAt(2*N-i)%mod2)*base%mod2;
			S22 += T.charAt(N-i);
			S22 %= mod2;

			//条件を満たしている？
			if(S11==S21&&S12==S22)
				if(check(T,N,N-i))
					return;
		}

		//一つも条件を満たさなかった=解無し
		System.out.println(-1);
	}

	//a^bをmodで割ったあまりを返す
	public static long modPow(long a,long b,int mod){
		long ans = 1;
		a %= mod;
		b %= mod-1;
		while(b>0){
			if((b&1)==1){
				ans *= a;
				ans %= mod;
			}
			a *= a;
			a %= mod;
			b >>= 1;
		}
		return ans;
	}

	//文字列が等しいか調べるメソッド
	public static boolean check(String s,int n,int i){

		//条件の通りに文字列を整形
		String S = s.substring(0,i)+s.substring(n+i,2*n);
		String T = s.substring(i,n+i);

		//Tを反転させると等しくなるか見る
		boolean isSame = true;
		for(int j=0;j<n;j++)
			isSame &= S.charAt(j)==T.charAt(n-1-j);

		//めんどくさかったのでこっちでそのまま出力
		if(isSame){
			System.out.println(S);
			System.out.println(i);
		}

		//合致(出力)したか返す
		return isSame;
	}
}

知らない知識だったので勉強になりました。