ABC330A～Fの解答[Java]

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

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

## A - Counting Passes
問題文は[こちら](https://atcoder.jp/contests/abc330/tasks/abc330_a)

普通にfor文で受け取りながらL以上ならインクリメントする方針で解きました。
```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){

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

  		//数え上げ
		int ans = 0;
		while(N-->0)
			if(sc.nextInt()>=L)
				ans++;

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

		out.close();
	}
}
```

## B - Minimize Abs 1
問題文は[こちら](https://atcoder.jp/contests/abc330/tasks/abc330_b)

問題文の式を考えてみると、$X_i = \min(R,\max(L,A_i))$であることがわかるので、それを求めました。
```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、L、R、Aの受け取り
		int N = sc.nextInt();
		int L = sc.nextInt();
		int R = sc.nextInt();
		int[] A = sc.nextInt(N);

  		//答えの構築
		int[] ans = new int[N];
		for(int i=0;i<N;i++){
			if(A[i]<L)
				ans[i] = L;
			else if(R<A[i])
				ans[i] = R;
			else
				ans[i] = A[i];
		}

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

		out.close();
	}
}
```
Java21からは`Math::clamp`を使えるので、言語アップデートを待ちましょう。

## C - Minimize Abs 2
問題文は[こちら](https://atcoder.jp/contests/abc330/tasks/abc330_c)

$x$は$\sqrt{D}$まで試せば良いと思ったので、その範囲で全探索しました。
```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){

		//Dの受け取り
		long D = sc.nextLong();

  		//全探索
		long ans = D;
		for(long x=0;x*x*2<=D;x++){
			long y = (int)Math.sqrt(D-x*x);
			ans = Math.min(ans,Math.abs(D-x*x-y*y));
			y++;
			ans = Math.min(ans,Math.abs(D-x*x-y*y));
		}

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

		out.close();
	}
}
```

## D - Counting Ls
問題文は[こちら](https://atcoder.jp/contests/abc330/tasks/abc330_d)

問題文の条件を満たす三つ組のマスはL字型になると思ったので、予め各行、列の`o`の数を数えておき、L字のちょうど曲がり角の部分のマスを全探索すれば重複無く探索できるかなと考え、それを実装しました。
```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(N);

  		//各行、列のoの数を数える
		int[] countI = new int[N];
		int[] countJ = new int[N];
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(S[i][j]=='o'){
					countI[i]++;
					countJ[j]++;
				}
			}
		}

  		//数え上げ
		long ans = 0;
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(S[i][j]=='o'){

    				//自分以外で数えたいので-1してる
					ans += (countI[i]-1)*(countJ[j]-1);
				}
			}
		}

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

		out.close();
	}
}
```
気付けば特に悩まないですね。

## E - Mex and Update
問題文は[こちら](https://atcoder.jp/contests/abc330/tasks/abc330_e)

$A$に含まれていない値をTreeSetで管理することでこの問題を解きました。
```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、Q、Aの受け取り
		int N = sc.nextInt();
		int Q = sc.nextInt();
		int[] A = sc.nextInt(N);

  		//Map代わり
		int[] count = new int[N+1];
		for(int num:A)
			if(num<N)
				count[num]++;

		//Set(Mex候補)
		TreeSet<Integer> set = new TreeSet<>();
		for(int i=0;i<=N;i++)
			if(count[i]==0)
				set.add(i);

		//クエリの処理
		while(Q-->0){

  			//i、xの受け取り
			int i = sc.nextInt()-1;
			int x = sc.nextInt();

   			//Mex候補になるか確認
			if(A[i]<N)
				if(--count[A[i]]==0)
					set.add(A[i]);

			A[i] = x;

			//Mex候補から外れるか確認
			if(A[i]<N)
				if(count[A[i]]++==0)
					set.remove(A[i]);

			//mexの出力
			out.println(set.first());
		}

		out.close();
	}
}
```
最初NをSetに入れるのを忘れてしまって2回もペナルティを頂いてしまいました…。

## F - Minimize Bounding Square
問題文は[こちら](https://atcoder.jp/contests/abc330/tasks/abc330_f)

$X$座標と$Y$座標の話は独立に考えて良いため、$X$座標に関してのみ最初は書きます。
ある非負整数$M$について、$X$座標と平行な辺の長さを$M$にするために必要なコストは左右から、移動する点の少ない方を貪欲に動かす手法を用いれば$O(N)$で答えが出せるので、辺の長さを$i$にするコストは$K$以下か？という判定問題に落とし込め、これは決め打ち二分探索を用いることで最小の長さを求めることができます。あとは、$X$座標と$Y$座標を同時に処理することで本問題を解きました。
```F.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、K、X、Yの受け取り
		int N = sc.nextInt();
		long K = sc.nextLong();
		int[] X = new int[N];
		int[] Y = new int[N];
		for(int i=0;i<N;i++){
			X[i] = sc.nextInt();
			Y[i] = sc.nextInt();
		}

		//ソートしても大丈夫なのでソートしておく
		Arrays.sort(X);
		Arrays.sort(Y);

		//二分探索(ラムダ式の中が判定関数)
		int ans = Searcher.overSearch(0,(int)1e9,0,(int i)->{
			long sum = 0;

			//X座標と平行な辺をi以下にする
			int xL = X[0];
			int xR = X[N-1];
			int countXL = 1;
			int countXR = 1;
			while(i<xR-xL){
				if(countXL<countXR){
					if(xR-X[countXL]<i)
						sum += (long)countXL*(xR-xL-i);
					else
						sum += (long)countXL*(X[countXL]-X[countXL-1]);
					xL = X[countXL++];
				}
				else{
					if(X[N-countXR-1]-xL<i)
						sum += (long)countXR*(xR-xL-i);
					else
						sum += (long)countXR*(X[N-countXR]-X[N-countXR-1]);
					xR = X[N-(++countXR)];
				}
			}

   			//Y座標と平行な辺をi以下にする
			int yL = Y[0];
			int yR = Y[N-1];
			int countYL = 1;
			int countYR = 1;
			while(i<yR-yL){
				if(countYL<countYR){
					if(yR-Y[countYL]<i)
						sum += (long)countYL*(yR-yL-i);
					else
						sum += (long)countYL*(Y[countYL]-Y[countYL-1]);
					yL = Y[countYL++];
				}
				else{
					if(Y[N-countYR-1]-yL<i)
						sum += (long)countYR*(yR-yL-i);
					else
						sum += (long)countYR*(Y[N-countYR]-Y[N-countYR-1]);
					yR = Y[N-(++countYR)];
				}
			}

   			//かかったコストがK以下なら1、Kを超えるなら0
			return sum>K?0:1;
		});

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

		out.close();
	}
}
```
かなり悩んでしまいましたが時間内に解けて良かったです。

## 感想
A,B,C,D:易しめ
E:Eにしてはかなり易しいかも？
F:結構悩んじゃった…
って感じでした。

ペナを減らせるようちゃんと注意を払わないと、ですねぇ…。