ABC293A～Eの解答[Java]

はじめに

今回はAからDまで解けたのでそれと、コンテスト後に解いたEを載せようと思います。

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

A - Swap Odd and Even

問題文はこちら

問題文の通りに実装しましょう。

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 ) {
 
		//Sの受け取り
		char[] S = sc.nextCharArray();

		//問題文の通り、交換する
		for(int i=1;i<=S.length/2;i++){
			char c = S[2*i-2];
			S[2*i-2] = S[2*i-1];
			S[2*i-1] = c;
		}

		//出力
		out.println(S);
 
		out.close();
	}
}

特に難しくは無いですね。

B - Call the ID Number

問題文はこちら

これもシミュレーションしていけば良いですね。

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 ) {
 
		//N、Aの受け取り
		int N = sc.nextInt();
		int[] A = sc.nextInt(N);

		//呼び出されたか管理する用
		boolean[] isCalled = new boolean[N];

		//問題文の行動をシミュレーション
		for(int i=0;i<N;i++){
			if(isCalled[i])
				continue;
			isCalled[A[i]-1] = true;
		}

		//呼ばれていない人を数える
		int count = 0;
		for(int i=0;i<N;i++)
			if(!isCalled[i])
				count++;

		//呼ばれていない人を順に格納する
		int[] ans = new int[count];
		int index = 0;
		for(int i=0;i<N;i++)
			if(!isCalled[i])
				ans[index++] = i+1;

		//人数とそれぞれの番号を出力
		out.println(count);
		out.println(ans," ");
 
		out.close();
	}
}

普段より易しい？

C - Make Takahashi Happy

問題文はこちら

bit全探索で解きました。

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 ) {
 
		//H、W、Aの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		int[][] A = sc.nextInt(H,W);

		//答え用変数
		int ans = 0;

		//bit全探索
		for(int i=0;i<1<<(H+W-2);i++){

			//1の数がH-1個じゃないなら弾く
			if(Integer.bitCount(i)!=H-1)
				continue;

			//座標
			int x = 0;
			int y = 0;

			//重複管理用Set
			HashSet<Integer> set = new HashSet<>();
			set.add(A[0][0]);

			//重複が無かったか確認するようの変数
			boolean isGood = true;
			for(int j=1;j<1<<(H+W-2);j<<=1){

				//遷移
				if((i&j)>0)
					x++;
				else
					y++;

				//移動先の数値をsetに追加
				isGood &= set.add(A[x][y]);
			}

			//重複してなかったら加算
			if(isGood)
				ans++;
		}

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

最初$H$個$1$があると思って実装しちゃって手間取ってしまいました…。

D - Tying Rope

問題文はこちら

ロープ$i$の赤の端を頂点$i$、青の端を頂点$i+N$として、UnionFindを用いて解きました。

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の受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

		//2N個の頂点を持ったUnionFind
		UnionFind uf = new UnionFind(N<<1);

		//同じロープ同士を繋げる
		for(int i=0;i<N;i++)
			uf.unite(i,i+N);

		//わっかになってる個数を数える変数
		int count = 0;
		while(M-->0){

			//A、Bとそれぞれの色の受け取り
			int A = sc.nextInt()-1;
			char cA = sc.nextChar();
			int B = sc.nextInt()-1;
			char cB = sc.nextChar();

			//すでに同じ集合に属している=わっかになったので加算
			if(!uf.unite(cA=='R'?A:A+N,cB=='R'?B:B+N))
				count++;
		}

		//答えの出力
		out.println(count+" "+(uf.groupCount()-count));
 
		out.close();
	}
}

今思えばわざわざ色で頂点を分ける必要は無かったですね。

E - Geometric Progression

問題文はこちら

公式解説の通りです。

E.java

import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//A、X、Mの受け取り
		int A = sc.nextInt();
		long X = sc.nextLong();
		int M = sc.nextInt();

		long[][] mat = {
			{A,1},
			{0,1}
		};

		//行列累乗
		mat = modPow(new long[][]{{0},{1}},mat,X,M);

		//答えの出力
		System.out.println(mat[0][0]);
	}

	//行列累乗メソッド
	private static long[][] modPow(long[][] ans,long[][] mat,long b,long mod){
		long[][] a = new long[mat.length][mat[0].length];
		for(int i=0;i<mat.length;i++)
			System.arraycopy(mat[i],0,a[i],0,mat[i].length);
		while(0<b){
			if((b&1)==1){
				ans = modMultiply(a,ans,mod);
			}
			a = modMultiply(a,a,mod);
			b >>= 1;
		}
		return ans;
	}

	//行列乗算メソッド
	private static long[][] modMultiply(long[][] mat1,long[][] mat2,long mod){
		if(mat1[0].length!=mat2.length)
			throw new IllegalArgumentException("can't multiply mat1(len="+mat1[0].length+")by mat2(len="+mat2.length+")");
		int H = mat1.length;
		int W = mat2[0].length;
		int len = mat2.length;
		long[][] ans = new long[H][W];
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)
				for(int k=0;k<len;k++)
					ans[i][j] = (ans[i][j]+mat1[i][k]*mat2[k][j])%mod;
		return ans;
	}
}

知らなかったので勉強になりました。

感想

A,B:易しい
C:bit全探索でも再帰でもいけそうだな～って思った
D:最近UnionFind使う問題増えた？
E:こんなものが…便利っすねぇ
って感じでした。

レートは上がったけど、やっぱり5完したかったなぁという気持ちが…。