ABC365A～Eの解答[Java]

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

なお、僕のライブラリは[GitHub](https://github.com/viral8code/viral-Library)よりご確認ください。
では、見ていきましょう。

## A - Leap Year
問題文は[こちら](https://atcoder.jp/contests/abc365/tasks/abc365_a)

問題文の通りに実装しました。
```A.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

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

  		//問題文の通りに実装
		if(Y%4>0){
			out.println(365);
		}
		else if(Y%100>0){
			out.println(366);
		}
		else if(Y%400>0){
			out.println(365);
		}
		else{
			out.println(366);
		}

		out.close();
	}
}
```

## B - Second Best
問題文は[こちら](https://atcoder.jp/contests/abc365/tasks/abc365_b)

$1$番目に大きい値、$2$番目に大きい値を保持しておくことで順に見ていきながら処理することができます。
```B.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

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

  		//最大値のインデックスを記録
		int max1 = 0;
		int max2 = 1;
		if(A[0]<A[1]){
			max1 = 1;
			max2 = 0;
		}

  		//更新
		for(int i=2;i<N;i++){
			if(A[max1]<A[i]){
				max2 = max1;
				max1 = i;
			}
			else if(A[max2]<A[i]){
				max2 = i;
			}
		}

  		//2番目に大きいインデックスを出力
		out.println(max2+1);

		out.close();
	}
}
```

## C - Transportation Expenses
問題文は[こちら](https://atcoder.jp/contests/abc365/tasks/abc365_c)

上限が決まれば総和が$M$以下かは高速に判定できるため、二分探索で最大の$x$を求めることができます。
```C.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

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

  		//二分探索
		long ans = Searcher.downSearch(0,Long.MAX_VALUE>>1,M,B->{
			long sum = 0;
			for(int num:A)
				sum += Math.min(B,num);
			return sum;
		});

  		//答えの出力
		out.println(ans==Long.MAX_VALUE>>1?"infinite":ans);

		out.close();
	}
}
```

## D - AtCoder Janken 3
問題文は[こちら](https://atcoder.jp/contests/abc365/tasks/abc365_d)

DPの要領で変数を更新していくことで解を求めました。
```D.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//N、Sの受け取り
		int N = sc.nextInt();
		char[] S = sc.nextCharArray();

  		//DP
		int r = 0;
		int p = 0;
		int s = 0;
		for(char c:S){
			int nr,np,ns;
			if(c=='R'){
				ns = Integer.MIN_VALUE;
				np = Math.max(r,s)+1;
				nr = Math.max(p,s);
			}
			else if(c=='P'){
				nr = Integer.MIN_VALUE;
				ns = Math.max(r,p)+1;
				np = Math.max(r,s);
			}
			else{
				np = Integer.MIN_VALUE;
				nr = Math.max(p,s)+1;
				ns = Math.max(r,p);
			}
			r = nr;
			p = np;
			s = ns;
		}

  		//答えの出力
		out.println(MathFunction.max(r,p,s));

		out.close();
	}
}
```

## E - Xor Sigma Problem
問題文は[こちら](https://atcoder.jp/contests/abc365/tasks/abc365_e)

各bit毎に、$i$からのxor和が1になる区間の長さを求めてあげることで高速に解を求めることができます。
```E.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

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

  		//bit毎に数え上げ
		long ans = 0;
		for(int i=0;i<28;i++){

  			//xor和が1になる区間の数え上げ
			int a = 0;
			boolean flag = false;
			for(int j=0;j<N;j++){
				if((A[j]&(1<<i))>0){
					flag = !flag;
				}
				if(flag)
					a++;
			}

   			//直前の始点が1ならxor和が0になる区間と1になる区間が反転するので、それを処理しながら数え上げ
			long sum = 0;
			for(int j=0;j<N;j++){
				if((A[j]&(1<<i))>0){
					--a;
				}
				sum += a;
				if((A[j]&(1<<i))>0){
					a = (N-j-1)-a;
				}
			}

   			//今のbitに合わせて補正して加算
			ans += sum*(1<<i);
		}

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

		out.close();
	}
}
```
全然サンプルと合わなくて凄い時間かけてしまいました…。

## 感想
A,B:易しい
C:二分探索らしい問題文だった
D:易しめなDP
E:細かい実装ミスが重なって凄い大変だった…
って感じでした。

う～ん…もっと速度を出したかった…。