ABC303A～Eの解答[Java]

## はじめに
今回はEまで解けたのでそのままそれを載せようと思います。

では、見ていきましょう。
なお、ライブラリは[提出結果](https://atcoder.jp/contests/abc303/submissions?f.Task=&f.LanguageName=&f.Status=AC&f.User=viral)からご確認下さい。

## A - Similar String
問題文は[こちら](https://atcoder.jp/contests/abc303/tasks/abc303_a)

$S$と$T$が異なるときに、異なる箇所が$0$と$o$の組み合わせ、$1$と$l$の組み合わせかを判定することで解きました。
```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 ) {
 
		//N、S、Tの受け取り
		int N = sc.nextInt();
		String S = sc.next();
		String T = sc.next();

		//先頭から一致してるか見る
		for(int i=0;i<N;i++){
			if(S.charAt(i)!=T.charAt(i)){

				//似てる場合ではないときで不一致ならNoを出力して終了する
				if(S.charAt(i)=='1'||S.charAt(i)=='l'){
					if(T.charAt(i)!='1'&&T.charAt(i)!='l'){
						System.out.println("No");
						return;
					}
				}
				else if(S.charAt(i)=='0'||S.charAt(i)=='o'){
					if(T.charAt(i)!='0'&&T.charAt(i)!='o'){
						System.out.println("No");
						return;
					}
				}
				else{
					System.out.println("No");
					return;
				}
			}
		}

		//ループを抜けた=似てるからYes
		out.println("Yes");
 
		out.close();
	}
}
```
B解いてるあたりで[ユーザー解説](https://atcoder.jp/contests/abc303/editorial/6466)にあるような解き方をすればサクッと解けたなぁと思いました。もっと早く気づけるようになりたい…。

## B - Discord
問題文は[こちら](https://atcoder.jp/contests/abc303/tasks/abc303_b)

自分よりも番号が大きくて不仲である可能性がある人を`HashSet<Integer>`で管理して、隣り合っている人をそこから消すことで求めました。
```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、M、aの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] a = sc.nextInt(M,N);

		//不仲な可能性のある人として全組を入れておく
		ArrayList<HashSet<Integer>> list = new ArrayList<>();
		list.add(new HashSet<>());
		for(int i=1;i<=N;i++){
			HashSet<Integer> set = new HashSet<>();
			for(int j=i+1;j<=N;j++)
				set.add(j);
			list.add(set);
		}

		//隣り合う組を不仲候補から消す
		for(int[] A:a){
			for(int i=1;i<N;i++){
				list.get(Math.min(A[i-1],A[i])).remove(Math.max(A[i-1],A[i]));
			}
		}

		//不仲候補の数え上げ
		int ans = 0;
		for(HashSet<Integer> set:list)
			ans += set.size();

		//答えの出力
		out.println(ans);
 
		out.close();
	}
}
```
[公式解説](https://atcoder.jp/contests/abc303/editorial/6441)の全探索のやり方の方が良かったかな…どうだろ…。

## C - Dash
問題文は[こちら](https://atcoder.jp/contests/abc303/tasks/abc303_c)

シミュレーションで解きました。
```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、H、K、Sの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		int H = sc.nextInt();
		int K = sc.nextInt();
		String S = sc.next();

		//アイテムのあるマスをHashSetに入れる
		HashSet<Point> set = new HashSet<>();
		for(Point p:sc.nextPoint(M))
			set.add(p);

		//シミュレーション
		boolean canMove = true;
		int x = 0;
		int y = 0;
		for(char c:S.toCharArray()){
			if(c=='L')
				x--;
			if(c=='R')
				x++;
			if(c=='U')
				y++;
			if(c=='D')
				y--;
			H--;
			canMove &= 0<=H; //負になったかどうかを記録しておく
			if(set.contains(new Point(x,y))){
				if(H<K){
					set.remove(new Point(x,y)); //アイテムを取ったら消す
					H = K;
				}
			}
		}

		//一度も負にならなかった？
		out.println(canMove?"Yes":"No");
 
		out.close();
	}
}
```
最初アイテムを使用したときにremoveするのを忘れててペナルティを頂いてしまいました。
問題文は、ちゃんと読もう(自戒)。

## D - Shift vs. CapsLock
問題文は[こちら](https://atcoder.jp/contests/abc303/tasks/abc303_d)

動的計画法で解きました。
[公式解説](https://atcoder.jp/contests/abc303/editorial/6442)の遷移と大体同じです。
```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 ) {
 
		//X、Y、Z、Sの受け取り
		int X = sc.nextInt();
		int Y = sc.nextInt();
		int Z = sc.nextInt();
		String S = sc.next();

		//dp[i][j]:i文字目までにかかる時間(j=0ならCapsLockがoff、j=1ならon)
		long[][] dp = new long[S.length()+1][2];
		dp[0][1] = Z;

		//遷移
		for(int i=0;i<S.length();i++){
			char c = S.charAt(i);
			dp[i+1][0] = Math.min(dp[i][0]+(c=='a'?X:Y),Z+dp[i][1]+(c=='a'?X:Y));
			dp[i+1][1] = Math.min(Z+dp[i][0]+(c=='A'?X:Y),dp[i][1]+(c=='A'?X:Y));
		}

		//小さい方を出力
		out.println(Math.min(dp[S.length()][0],dp[S.length()][1]));
 
		out.close();
	}
}
```
ちょっと不安でしたが通ったので良かったです。

## E - A Gift From the Stars
問題文は[こちら](https://atcoder.jp/contests/abc303/tasks/abc303_e)

ちょっと実装が汚いですけど、BFSで解きました。
適当に次数が1の頂点を見つけて、そこから次数が2以上の頂点を辿って探しました。
スターグラフ同士を結ぶ頂点かどうかを識別するための数字もArrayDequeに入れてます。
```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の受け取り
		int N = sc.nextInt();

		//隣接リストの構築
		ArrayList<HashSet<Integer>> list = new ArrayList<>();
		for(int i=0;i<=N;i++)
			list.add(new HashSet<>());
		for(int i=1;i<N;i++){
			int u = sc.nextInt();
			int v = sc.nextInt();
			list.get(u).add(v);
			list.get(v).add(u);
		}

		//次数が1のところを記録
		ArrayList<Integer> one = new ArrayList<>();
		for(int i=1;i<=N;i++){
			if(list.get(i).size()==1)
				one.add(i);
		}

		//答えを入れとく用のArrayList
		ArrayList<Integer> answer = new ArrayList<>();

		//適当に次数1のところから行ける頂点(=どっかのスターグラフの中心)
		int node = list.get(one.get(0)).iterator().next();

		//BFSをする
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		boolean[] checked = new boolean[N+1];
		checked[node] = true;
		deq.add(node);
		deq.add(0); //0なら中心、1なら接続部として区別
		while(deq.size()>0){
			int now = deq.pollFirst();
			int id = deq.pollFirst();
			if(id==1){
				for(int next:list.get(now)){
					if(!checked[next]){
						checked[next] = true;

						//接続部から移動すると他のスターグラフとの接続部に移動するので、
						//さらに一個進めてArrayDequeに入れる
						Iterator<Integer> iter = list.get(next).iterator();
						int num = iter.next();
						if(num==now)
							num = iter.next();
						checked[num] = true;
						deq.add(num);
						deq.add(0);
					}
				}
			}
			else{

				//中心ならレベルをArrayListに記録
				answer.add(list.get(now).size());

				//接続部を見つけたらそこに移動
				for(int next:list.get(now)){
					if(!checked[next]&&list.get(next).size()>1){
						checked[next] = true;
						deq.add(next);
						deq.add(1);
					}
				}
			}
		}

		//ライブラリ的に出力がしやすいのでint[]に変換
		int[] ans = new int[answer.size()];
		for(int i=0;i<answer.size();i++)
			ans[i] = answer.get(i);
		//ソート
		ArrayFunction.sort(ans);
		//出力
		out.println(ans);
 
		out.close();
	}
}
```
コンテスト後に書いたものですが、次数2以上の頂点を数え上げ、頂点の数を求めて、それと辻褄を合わせるように次数2の個数を減らすことで解く方法もあります。
```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、隣接リストの受け取り
		int N = sc.nextInt();
		int[][] graph = sc.nextGraph(N,N-1);

		//次数別にカウントするようのバゲット
		int[] map = new int[N];
		//次数が2以上のものを数え上げる用の変数
		int count = 0;
		for(int i=1;i<=N;i++){
			if(graph[i].length>1){
				map[graph[i].length]++;
				count++;
			}
		}

		//スターグラフの次数2以上の頂点の個数
		int sum = (count-1)/3+1;

		//スターグラフ同士の連結で次数が2になっている頂点分を引く
		map[2] -= sum-1<<1;

		//答えの構築
		int[] ans = new int[sum];
		int index = 0;
		for(int i=2;i<N;i++)
			while(map[i]-->0)
				ans[index++] = i;

		//出力(小さい方からansに記録しているのでソートは要らない)
		out.println(ans);
 
		out.close();
	}
}
```
コンテスト中に思いつきはしたんですが、sumの計算式を間違えてしまって合わなくて、結局普通にBFSする解法に切り替えました。距離をmod3で考えるの、思いつきたかった…。

## 感想
A,B:易しい
C:ペナったけど易しい方
D:DPだな～って思ったけど遷移に漏れがないか不安だった
E:普通にBFSで見れば良い気はしたけど実装に手間取った
って感じでした。

なんか全体的に実装が遅かったです…。精進不足が出てしまった…。