ABC287A～Dの解答[Java]

## はじめに
今回はDまでしか解けなかったのでDまで載せようと思います。

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

## A - Majority
問題文は[こちら](https://atcoder.jp/contests/abc287/tasks/abc287_a)

先頭の文字だけ見ればどちらか判別できるので、先頭の文字が`F`のものを数えて過半数か判定しました。
```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の受け取り
		int N = System.in.nextInt();

		//総数
		int count = 0;

		//一文字目がFのものを数える
		for(int i=0;i<N;i++)
			if(System.in.next().charAt(0)=='F')
				count++;

		//過半数か？
		System.out.println(count*2>N?"Yes":"No");
 
		System.out.close();
	}
}
```
まぁ問題はないですね。

## B - Postal Card
問題文は[こちら](https://atcoder.jp/contests/abc287/tasks/abc287_b)

boolean型配列で$M$個の中に含まれるかを記録しておき、$S$を数字として受け取って$S$%$1000$が存在するかを判定しました。
```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){
 
		//N、M、Sの受け取り(Sは数値として)
		int N = System.in.nextInt();
		int M = System.in.nextInt();
		int[] S = System.in.nextInt(N);

		//Tが存在するか
		boolean[] isT = new boolean[1000];
		while(M-->0){
			int T = System.in.nextInt();
			isT[T] = true;
		}

		//Tの中にSがある数を数える
		int count = 0;
		for(int s:S)
			if(isT[s%1000])
				count++;

		//出力
		System.out.println(count);
 
		System.out.close();
	}
}
```
これもそこまで悩まなかったです。

## C - Path Graph?
問題文は[こちら](https://atcoder.jp/contests/abc287/tasks/abc287_c)

パスグラフの条件を満たすものは次数が$1$の頂点が$2$個、$2$の頂点が$N-2$個の連結グラフだと言い換えられるので、それを判定しました。
```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();

		//各頂点の次数
		int[] count = new int[N+1];

		//連結か見る用のUnionFind
		UnionFind uf = new UnionFind(N);

		//連結と次数の加算
		while(M-->0){
			int u = System.in.nextInt();
			int v = System.in.nextInt();
			count[u]++;
			count[v]++;
			uf.unite(u-1,v-1);
		}

		//次数が1のもの、2のもの、その他のもの
		int count1 = 0;
		int count2 = 0;
		int countAny = 0;

		//それぞれの次数に合わせて変数を増加
		for(int num:count){
			if(num==1)
				count1++;
			else if(num==2)
				count2++;
			else
				countAny++;
		}

		//頂点0の分が数えられているのでcountAnyは1になっていて、それ以外は上記の条件で判定
		System.out.println(count1==2&&count2==N-2&&countAny==1&&uf.groupCount()==1?"Yes":"No");
 
		System.out.close();
	}
}
```
連結かどうかを判定し忘れてずっと頭抱えてました…。

↓通らないケース
```
5 4
1 2
3 4
4 5
3 5
```

## D - Match or Not
問題文は[こちら](https://atcoder.jp/contests/abc287/tasks/abc287_d)

$x$から$x+1$に変化するときの$S'$の変化は$x$文字目が$S$の$|S|-x$番目から$x$番目の文字に入れ替わるだけなので、最初に$x=0$の時の不一致な箇所を数えておき、$x=1,2,...,|T|$では不一致が増えたか減ったかのみを見ることで解けると思い、それを実装しました。
```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){
 
		//S、Tの受け取り
		char[] S = System.in.nextCharArray();
		char[] T = System.in.nextCharArray();

		//不一致の数を数える
		int falseCount = 0;
		for(int i=0;i<T.length;i++){
			if(S[S.length-T.length+i]!=T[i]&&S[S.length-T.length+i]!='?'&&T[i]!='?')
				falseCount++;
		}

		//最初x=0の時の判定
		System.out.println(falseCount==0?"Yes":"No");

		//x=1～|T|
		for(int i=0;i<T.length;i++){

			//最初不一致だったなら解消されるので-1
			if(S[S.length-T.length+i]!=T[i]&&S[S.length-T.length+i]!='?'&&T[i]!='?')
				falseCount--;

			//変化後が不一致なら+1
			if(S[i]!=T[i]&&S[i]!='?'&&T[i]!='?')
				falseCount++;

			//全部一致=falseCountが0か？
			System.out.println(falseCount==0?"Yes":"No");
		}
 
		System.out.close();
	}
}
```
Cで悩んだときに先にこっちに着手できたのは良かったです。

## 感想
A,B:易しい
C:考察抜けがあって沼った…。
D:比較的易しい気がする
って感じでした。

めちゃくちゃレート下がりました…。次回取り返せるかな…。

## 追記(E - Karuta)
問題文は[こちら](https://atcoder.jp/contests/abc287/tasks/abc287_e)

詳しい説明は[公式解説](https://atcoder.jp/contests/abc287/editorial/5609)に任せます。
```E.java
import java.util.Scanner;
import java.util.Arrays;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

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

		//文字列に何番目のものかという情報も持たせたいのでクラス定義
		class Pair implements Comparable<Pair>{
			int id;
			String str;
			Pair(int i,String s){
				id = i;
				str = s;
			}
			@Override
			public int compareTo(Pair p){
				return str.compareTo(p.str);
			}
		}

		//文字列の受け取り
		Pair[] S = new Pair[N];
		for(int i=0;i<N;i++)
			S[i] = new Pair(i,sc.next());

		//文字列でソート
		Arrays.sort(S);

		//前後比較してより良い方を格納
		int[] ans = new int[N];
		for(int i=0;i<N;i++){
			int len1 = 0<i?check(S[i].str,S[i-1].str):0;
			int len2 = i<N-1?check(S[i].str,S[i+1].str):0;
			ans[S[i].id] = Math.max(len1,len2);
		}

		//出力高速化のための作業
		StringBuilder sb = new StringBuilder();
		for(int num:ans){
			sb.append(num);
			sb.append("\n");
		}

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

	//比較メソッド
	static int check(String S1,String S2){
		int len = Math.min(S1.length(),S2.length());
		for(int i=0;i<len;i++)
			if(S1.charAt(i)!=S2.charAt(i))
				return i;
		return len;
	}
}
```
「ソートして前後しか見なくて良い」という発想になれませんでした…精進不足ですね。