ABC332A～Fの解答[Java]

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

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

## A - Online Shopping
問題文は[こちら](https://atcoder.jp/contests/abc332/tasks/abc332_a)

総額を求めて$S$円未満かを判定して処理しました。
```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、P、Kの受け取り
		int N = sc.nextInt();
		int P = sc.nextInt();
		int K = sc.nextInt();

  		//総額を求める
		long sum = 0;
		for(int i=0;i<N;i++)
			sum += sc.nextInt()*sc.nextInt();

   		//送料がかかるなら加算
		if(sum<P)
			sum += K;

   		//出力
		out.println(sum);

		out.close();
	}
}
```

## B - Glass and Mug
問題文は[こちら](https://atcoder.jp/contests/abc332/tasks/abc332_b)

問題文をそのままコードに落とし込んでシミュレーションしました。
```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){

		//K、G、Mの受け取り
		int K = sc.nextInt();
		int G = sc.nextInt();
		int M = sc.nextInt();

  		//シミュレーション
		int gla = 0;
		int mug = 0;
		while(K-->0){
			if(gla==G)
				gla = 0;
			else if(mug==0)
				mug = M;
			else{
				int sub = Math.min(G-gla,mug);
				mug -= sub;
				gla += sub;
			}
		}

  		//答えの出力
		out.println(gla+" "+mug);

		out.close();
	}
}
```

## C - T-shirts
問題文は[こちら](https://atcoder.jp/contests/abc332/tasks/abc332_c)

Bと同様にシミュレーションで解きました。
なるべく無地のTシャツをきた方が有利なのでそのように処理してます。
```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の受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

  		//ロゴ入りTシャツ(着れる物)
		int L = 0;

  		//洗濯待ち
		int subM = 0;
		int subL = 0;

  		//順に処理
		String S = sc.next();
		for(char c:S.toCharArray()){

  			//洗濯する
			if(c=='0'){
				M += subM;
				L += subL;
				subM = 0;
				subL = 0;
			}

   			//なるべく無地を使う
			else if(c=='1'){
				if(M>0){
					M--;
					subM++;
				}
				else{
					L = Math.max(L-1,0); //無ければ1着購入
					subL++;
				}
			}

   			//ロゴ入りを着る
			else{
				L = Math.max(L-1,0); //無ければ1着購入
				subL++;
			}
		}

  		//最終的に所有している(=購入した)ロゴ入りTシャツの枚数を答える
		out.println(L+subL);
		out.close();
	}
}
```

## D - Swapping Puzzle
問題文は[こちら](https://atcoder.jp/contests/abc332/tasks/abc332_d)

$H$、$W$が小さいので順列全探索で解きました。
操作回数はバブルソートで求めています。
```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){

		//H、W、A、Bの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		int[][] A = sc.nextInt(H,W);
		int[][] B = sc.nextInt(H,W);

  		//順列全探索
		int[] r = new int[H];
		int[] c = new int[W];
		Arrays.setAll(r,i->i);
		int ans = Integer.MAX_VALUE;
		do{
			Arrays.setAll(c,i->i);
			Loop:do{

   				//一致してないなら次の候補へ
				for(int i=0;i<H;i++)
					for(int j=0;j<W;j++)
						if(A[r[i]][c[j]]!=B[i][j])
							continue Loop;

       			//全一致したなら最小値更新
				ans = Math.min(ans,count(r,c));
    
			}while(ArrayFunction.nextPermutation(c));
		}while(ArrayFunction.nextPermutation(r));

  		//ちゃんと一致させることができたかで場合分け
		out.println(ans==Integer.MAX_VALUE?-1:ans);

		out.close();
	}

 	//操作回数を数えるメソッド
	private static int count(int[] r,int[] c){

 		//配列をコピーして、その配列をバブルソートする工程で操作回数を数える
		int count = 0;
		int[] subR = Arrays.copyOf(r,r.length);
		for(int i=0;i<r.length;i++){
			for(int j=1;j<r.length-i;j++){
				if(subR[j-1]>subR[j]){
					ArrayFunction.swap(subR,j-1,j);
					count++;
				}
			}
		}
		int[] subC = Arrays.copyOf(c,c.length);
		for(int i=0;i<c.length;i++){
			for(int j=1;j<c.length-i;j++){
				if(subC[j-1]>subC[j]){
					ArrayFunction.swap(subC,j-1,j);
					count++;
				}
			}
		}
		return count;
	}
}
```
BFSする、という手法もありましたね(Twitterで見かけて確かに、になりました)。

## E - Lucky bag
問題文は[こちら](https://atcoder.jp/contests/abc332/tasks/abc332_e)

[公式解説](https://atcoder.jp/contests/abc332/editorial/7904)の通りです。
$$\sum_{i}{(x_i-\bar{x})^2}$$
$$=\sum_{i}{x_i^2}-\frac{(\sum_{j}{w_j})^2}{D}$$
より、$\sum_{i}{x_i^2}$の最小値を求めています(これのおかげでDPテーブルはlongで扱えます)。
```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、D、Wの受け取り
		int N = sc.nextInt();
		int D = sc.nextInt();
		long[] W = sc.nextLong(N);

  		//DPテーブルの構築
		long[][] dp = new long[D+1][1<<N];
		for(int i=1;i<1<<N;i++){
			for(int j=0;j<N;j++)
				if((i&1<<j)>0)
					dp[1][i] += W[j];
			dp[1][i] *= dp[1][i];
		}

  		//遷移
		for(int i=2;i<=D;i++){
			for(int j=1;j<1<<N;j++){
				int S = (j-1)&j;
				dp[i][j] = dp[i-1][j];
				while(S>0){
					long num = dp[i-1][j^S]+dp[1][S];
					if(num<dp[i][j])
						dp[i][j] = num;
					S = (S-1)&j;
				}
			}
		}

  		//答えの出力
		long sum = MathFunction.sum(W);
		out.println((dp[D][(1<<N)-1]*D-sum*sum)/(double)D/D);

		out.close();
	}
}
```
思いつけたら良かったけど…う～ん…。

## F - Random Update Query
問題文は[こちら](https://atcoder.jp/contests/abc332/tasks/abc332_f)

遅延セグ木で解きました。
処理は一次関数$f(x)=ax+b$の形で表せるので、compositionなどもそのような処理になっています。
```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);

	//mod
	private static final int MOD = 998244353;

	//一次関数を表すクラス
	private static class F{
		final long a,b;
		F(long a,long b){
			this.a = a;
			this.b = b;
		}
	}

	public static void main(String[] args){

		//N、M、Aの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		Long[] A = new Long[N]; //セグ木に載せるためにLongで
		for(int i=0;i<N;i++){
			long num = sc.nextLong();
			if(MOD<=num)
				num -= MOD;
			A[i] = num;
		}

  		//遅延セグ木の宣言
		LazySegmentTree<Long,F> lSegT = new LazySegmentTree<>(A,0L,new F(1,0),false){
			public Long function(Long a,Long b){
				return a; //何だって良いのでテキトーに
			}

   			//一次関数を適用するメソッド
			public Long mapping(Long a,F f){
				long ans = a*f.a%MOD+f.b;
				if(MOD<=ans)
					ans -= MOD;
				return ans;
			}

   			//一次関数を合成するメソッド
			public F composition(F a,F b){
				long c = a.a*b.a%MOD;
				long d = b.a*a.b%MOD+b.b;
				if(MOD<=d)
					d -= MOD;
				return new F(c,d);
			}
		};

  		//前計算用
		Factorial fact = new Factorial(200_000,MOD);

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

  			//L、R、Xの受け取り
			int L = sc.nextInt();
			int R = sc.nextInt();
			int X = sc.nextInt();
			if(MOD<=X)
				X -= MOD;

    		//一次関数の形に直してapply
			long a = (R-L)*fact.getInverse(R-L+1)%MOD;
			long b = X*fact.getInverse(R-L+1)%MOD;
			lSegT.apply(L-1,R,new F(a,b));
		}

  		//答えの取得と出力
		long[] ans = new long[N];
		for(int i=0;i<N;i++)
			ans[i] = lSegT.get(i);
		out.println(ans);

		out.close();
	}
}
```
ずっと答え合わなくてどこミスったんだろう…とコンテスト後も考えていたんですが、まさかのライブラリがバグっておりました…。
こ、殺してくれ…。

## 感想
A,B,C,D:易しめ
E:何も見えてこなかった…
F:遅延セグ木とわかったのに…わかったのに…
って感じでした。

前日のARCでもレート下がったので、非常に悲しい…。まぁ、ライブラリのバグが見つかったと思えば…。