ABC290A～Dの解答[Java]

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

では、見ていきましょう。
※ライブラリがこれまでとちょっと変わってるので気になる方は[提出コード](https://atcoder.jp/contests/abc290/submissions?f.Task=&f.LanguageName=&f.Status=AC&f.User=viral)をご覧ください。

## A - Contest Result
問題文は[こちら](https://atcoder.jp/contests/abc290/tasks/abc290_a)

普通に$B$を添え字として$A$の和を求めれば良いですね。$B$が1-indexedであることに注意です。
```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、M、A、Bの受け取り 
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] A = sc.nextInt(N);
		int[] B = sc.nextInt(M);

		//和を取る
		long ans = 0;
		for(int num:B)
			ans += A[num-1];

		out.println(ans);
 
		out.close();
	}
}
```
易しめですね。

## B - Qual B
問題文は[こちら](https://atcoder.jp/contests/abc290/tasks/abc290_b)

先頭$K$個の`o`はそのまま、それ以降の`o`は`x`に変換して出力しました。
```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、K、Sの受け取り
		int N = sc.nextInt();
		int K = sc.nextInt();
		char[] S = sc.nextCharArray();

		//xにすべきところをxに変換
		for(int i=0;i<N;i++)
			if(S[i]=='o'&&K--<=0)
				S[i] = 'x';

		//出力
		out.println(S);
 
		out.close();
	}
}
```
`&&`の左辺が`false`であれば右辺の評価はされないのでこれで$K$個分`o`をスルー出来ます。

## C - Max MEX
問題文は[こちら](https://atcoder.jp/contests/abc290/tasks/abc290_c)

$K$個要素を選んだ時の$MEX(X)$は$K$を超えないので、$\mathrm{min}(MEX(A),K)$が答えとなります。
```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、K、Aの受け取り
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] A = sc.nextInt(N);

		//TreeSetに入れて、MEX(A)を調べる
		TreeSet<Integer> set = new TreeSet<>();
		for(int num:A)
			set.add(num);

		//Kに達した時点で切りあげるように
		int index = 0;
		while(!set.isEmpty()&&set.first()==index&&K-->0){
			set.pollFirst();
			index++;
		}

		//出力
		out.println(index);
 
		out.close();
	}
}
```
`!set.isEmpty()`を入れ忘れてREでペナルティを2回も食らってしまいました…焦りすぎですね…。

## D - Marking
問題文は[こちら](https://atcoder.jp/contests/abc290/tasks/abc290_d)

以下、$D$は$D$%$N$に置き換えても一般性を失わないので置き換えたものとして話を進めます($D$が$N$の倍数の場合は$1$に)。
あまりを取らなかった場合の$x$の値は$D(K-1)$です。そして、$x$が過去に印をつけた箇所と被る周期は$\mathrm{lcm}(N,D)$です。したがって、あまりを取らなかったときの$x$に対して被った分だけ加算して$N$で割ったあまりを求める、以下の式で答えが求められます。
$$( \lfloor \frac{D(K-1)}{\mathrm{lcm}(N,D)} \rfloor +D(K-1))\ \mathrm{mod}\ N$$

<details><summary>公式解説の式への変形</summary><div>

---

上記の式を式Aとします。
公式解説を見ると以下の式を用いて求めています。
$$\lfloor \frac{K-1}{N / \mathrm{gcd}(N,D)} \rfloor +D(K-1)\ \mathrm{mod}\ N$$
後ろの項はそのままなので前の項を式Aの前の項から導きます。
$N=ng$、$D=dg$($g$は$\mathrm{gcd}(N,D)$)とすると、$\mathrm{lcm}(N,D)=ndg$です。したがって、式Aの前の項は以下のように変形できます。
$$\frac{D(K-1)}{\mathrm{lcm}(N,D)}=\frac{dg(K-1)}{ndg}=\frac{K-1}{n}$$
よって、$n=N / \mathrm{gcd}(N,D)$より式Aは公式解説の式と同じ式になります。

---

</div></details>

```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 ) {
 
		//Tの受け取り
		int T = sc.nextInt();
		while(T-->0){

			//N、Dの受け取り
			int N = sc.nextInt();
			int D = sc.nextInt()%N; //Nで割ったあまりに変換
			if(D==0)
				D++; //「D==0だとずっと被り続ける」=「Dが1の時と同じ挙動」をするので1に変換

			//x=0から始まるので1引いておいた方が楽
			int K = sc.nextInt()-1;

			//上記の式の実装
			out.println(((long)D*K/MathFunction.lcm(N,D)+(long)D*K)%N);
		}
 
		out.close();
	}
}
```
気付かなくてずっと愚直に求めるコードを書いてしまってました…。

## 感想
A,B:易しい
C:ペナこそあったが、気付けば難しくはない
D:全然頭回ってなかった…
という感じでした。

焦りがまんまペナルティとして出た感じでした…。改めて、精進し直します。

## 追記(E - Make it Palindrome)
問題文は[こちら](https://atcoder.jp/contests/abc290/tasks/abc290_e)

[公式解説](https://atcoder.jp/contests/abc290/editorial/5757)の通りです。
```E.java
import java.util.Scanner;
import java.util.ArrayList;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

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

		//各要素のインデックスを格納
		ArrayList<ArrayList<Integer>> index = new ArrayList<>();
		for(int i=0;i<=N;i++)
			index.add(new ArrayList<>());
		for(int i=1;i<=N;i++){
			int A = sc.nextInt();
			index.get(A).add(i);
		}

		//全部の線の数え上げ
		long ans = 0;
		for(long i=1;i<=N;i++)
			ans += (N+1-i)*(i/2);

		//良い線を引く工程
		for(int i=1;i<=N;i++){
			int l = 0;
			int r = index.get(i).size()-1;
			while(l<r){
				if(index.get(i).get(l)<N+1-index.get(i).get(r))
					ans -= (long)(r-l)*index.get(i).get(l++);
				else
					ans -= (long)(r-l)*(N+1-index.get(i).get(r--));
			}
		}

		//出力
		System.out.println(ans);
	}
}
```
解説の悪い線を数えれば良さそうだなぁとは思ったのですが、それ以上思考を発展させることができませんでした…。