ABC268A～Dの解答[Java]

## はじめに
今回も4完出来たのでDまで載せようと思います。

では見ていきましょう。

## A - Five Integers
問題文は[こちら](https://atcoder.jp/contests/abc268/tasks/abc268_a)

[公式解説](https://atcoder.jp/contests/abc268/editorial/4779)のように全部比べていっても良いですが、今回はHashSetを使ってみました。
Setで要素の重複はしないので、単純にsize()を出力すれば良いです。
```A.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{

		//重複を弾くためのHashSet
		HashSet<Integer> list = new HashSet<Integer>();

		//それぞれをadd
		for(int i=0;i<5;i++){
			list.add(System.in.nextInt());
		}

		//数字の種類を出力
		System.out.println(list.size());
		System.out.close();
	}
}
```
簡単ですね。

## B - Prefix?
問題文は[こちら](https://atcoder.jp/contests/abc268/tasks/abc268_b)

SとTをchar型配列として受け取って一文字ずつ比較しました。
```B.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{

		//S、Tそれぞれをchar型配列として受け取り
		char[] S = System.in.nextCharArray();
		char[] T = System.in.nextCharArray();

		//SがTより長いなら弾く
		if(S.length>T.length){
			System.out.println("No");
		}else{

			//先頭から順に見ていく
			for(int i=0;i<S.length;i++){
				if(S[i]!=T[i]){
					System.out.println("No");
					System.exit(0);
				}
			}

			//forを抜けた=一致したのでYesを出力
			System.out.println("Yes");
		}
		System.out.close();
	}
}
```

ただ、接頭辞かだけの判定ならStringクラスのメソッド`startsWith(String prefix)`を使うだけで良かったですね。

```B改.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{

		//S、Tの受け取り
		String S = System.in.next();
		String T = System.in.next();

		//接頭辞ならYes、違うならNo
		System.out.println(T.startsWith(S)?"Yes":"No");
		System.out.close();
	}
}
```

どちらでも実行時間に差はほとんどありませんでした。

## C - Chinese Restaurant
問題文は[こちら](https://atcoder.jp/contests/abc268/tasks/abc268_c)

pが`0 1 2 3･･･`って並んでいる時を考えてみると、pi-iは常に一定になることがわかります。では0と1を末尾に持って行った`2 3･･･0 1`の場合はどうでしょう。pi-iは末尾の0と1だけ異なってしまいます。しかし、modNではどうでしょう。
2-0=2、3-1=2、･･･、0-(N-2)=2-N≡2 mod N、1-(N-1)=2-N≡2 modN
一致していますね。
ということで、どれかの数字Mを基準にしたときに`M M+1 M+2･･･ (modN)`と一致している個数を数えれば人Mと料理Mを一致させたときに喜ぶ人数が求められます(実際には±1の範囲も加算する)。
```C.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{

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

		//pi-i modNの重複を数える配列
		int[] count = new int[N];

		//条件を元に加算
		for(int i=0;i<N;i++){
			count[(p[i]-i+N+1)%N]++;
			count[(p[i]-i+N)%N]++;
			count[(p[i]-i+N-1)%N]++;
		}

		//最大を探す
		int max = 0;
		for(int tmp:count){
			max = Math.max(max,tmp);
		}

		//出力
		System.out.println(max);
		System.out.close();
	}
}
```
早めに解法に気付いて良かったです。

## D - Unique Username
問題文は[こちら](https://atcoder.jp/contests/abc268/tasks/abc268_d)

DFSで実装しました。
選んだ文字数と作りかけのユーザー名を引数に持つようにして全通り試しました。
間に合うのか？と思うかもしれませんが、かなり組合せの数が少ないので十分終わります。

<details><summary>各Nでの通り数</summary><div>

---
全部の文字の長さが1で、かつ重複が無い時が一番通り数が増えるのでその条件下での通り数を求めます。

・N=1の時
1個しかないので1通りです。

・N=2の時
並べ替えは2!=2通り、間に`_`を16-2=14個まで入れられるので、2×14=28通りです。

・N=3の時
並べ替えは3!=6通り、`_`を合計16-3=13個入れられ、必ずそれぞれの間に1個以上入れる必要があるので、
$6 \times \sum_{i=1}^{13}\sum_{j=1}^{13-i}1=396$通りです。

以下同様に、

・N=4の時
$4! \times \sum_{i=1}^{12}\sum_{j=1}^{12-i}\sum_{k=1}^{12-i-j}1=5280$通り

・N=5の時
$5! \times \sum_{i=1}^{11}\sum_{j=1}^{11-i}\sum_{k=1}^{11-i-j}\sum_{l=1}^{11-i-j-k}1=15120$通り

・N=6の時
$6! \times \sum_{i=1}^{10}\sum_{j=1}^{10-i}\sum_{k=1}^{10-i-j}\sum_{l=1}^{10-i-j-k}\sum_{m=1}^{10-i-j-k-l}1=90720$通り

・N=7の時
$7! \times \sum_{i=1}^{9}\sum_{j=1}^{9-i}\sum_{k=1}^{9-i-j}\sum_{l=1}^{9-i-j-k}\sum_{m=1}^{9-i-j-k-l}\sum_{n=1}^{9-i-j-k-l-m}1=141120$通り

・N=8の時
並べ替えは8!=40320通り、間に`_`を16-8=8個まで入れられますが、8文字の間は7カ所あってそれぞれに1個以上入れる必要があるので、全て`_`か追加で`_`をどこかに入れると考えれば`_`の入れ方は8通りです。よって、40320×8=322560通りです。

ということで、最大でも322560通り調べれば良いので十分終わります。

---

</div></details>

N=1の時は先に弾いてしまいました。

```D.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	//dfsに渡すためにstaticで
	static HashSet<String> blackList = new HashSet<String>();
	static String[] S;
	static boolean[] isUsed;
 
	public static void main(String[] args)throws IOException{

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

		//TをブラックリストとしてHashSetに
		while(M-->0){
			blackList.add(System.in.next());
		}

		//N=1のときは別に処理
		if(N==1){
			int now = blackList.size();
			blackList.add(S[0]);
			System.out.println((S[0].length()>2&&now<blackList.size())?S[0]:"-1");
			System.exit(0);
		}

		//すでに使ってる文字か管理するboolean型配列
		isUsed = new boolean[N];

		//答え用変数
		String answer = "";
		for(int i=0;i<N;i++){

			//使用済みに
			isUsed[i] = true;

			//dfs
			answer = search(S[i],N-1);

			//答えが見つかったなら終了
			if(!answer.equals("-1"))
				break;

			//使用済みを解除
			isUsed[i] = false;
		}

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

	//dfs
	public static String search(String name,int n){

		//使ってない文字列を探す
		for(int i=0;i<S.length;i++){
			if(isUsed[i])
				continue;

			//使用済みにセット
			isUsed[i] = true;

			//`_`を入れられるだけ入れてみる
			for(int j=1;j<=16-name.length()-S[i].length();j++){

				//StringBuilderで整形
				StringBuilder sb = new StringBuilder(name);
				for(int k=0;k<j;k++){
					sb.append('_');
				}
				sb.append(S[i]);

				//ちょうど最後の文字？
				if(n==1){

					//HashSetに突っ込んでみてサイズが変わればそれを返す
					int now = blackList.size();
					blackList.add(sb.toString());
					if(now<blackList.size())
						return sb.toString();
				}else{

					//dfs(-1以外が返ってきたらそれを返す)
					String ret = search(sb.toString(),n-1);
					if(!ret.equals("-1"))
						return ret;
				}
			}

			//使用済みを解除
			isUsed[i] = false;
		}

		//見つからなかったら-1を返す
		return "-1";
	}
}
```
N=1の時に|S|<3をNoとするのを忘れてたのでとんでもないペナルティをいただいてしまいました･･･。

## 感想
A、B:易しい
C:比較的容易に気付いた。
D:バグり散らかしたが、発想だけは速攻で出来たのでヨシ！
って感じでした。

Cまでを比較的早めに解けたのでパフォーマンスが高かったですが、Dはもうちょっと早く解きたかったなぁという気持ちが･･･。