AtCoder Beginner Contest 167 (ABC167) に参加しました！

AtCoder Beginner Contest 167 (ABC167) に参加しました。
うーん、ちょっと悔しいですね。
感想を書いていきます。

ちなみに、前回の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

準備

前回から勉強したのは次の２つです。

• 二分探索
• 素数

今回のを見ると、そろそろDPやらないとやばそうですね・・・

経過

今回もスタートがスムーズでした。
（AtCoder社さんありがとうございます。）

A・B問題についてはスムーズに解けました。

C問題はちょっと時間がかかりました。(40分くらい)
見た感じ、重み付きナップザック問題かなと思ったのですが、まだやってないのでやばいなと思いました。

ただ、どこかのサイトでC問題までは全探索で何とかなるという風に書いてあったのを思い出し、なんとかbit全探索で通しました。

そのコードがこちらです。（汚いかもしれませんが）

import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();
		int X = sc.nextInt();

		int[] C = new int[N];
		int[][] A = new int[N][M];
		long C_sum = 0;
		long[] A_sum = new long[M];
		for(int i=0; i<N; i++) {
			C[i] = sc.nextInt();
			C_sum += C[i];

			for(int j=0; j<M; j++) {
				A[i][j] = sc.nextInt();
				A_sum[j] += A[i][j];
			}
		}

		//すべて選ぶ
		for(int i=0; i<M; i++) {
			if(A_sum[i] < X) {
				System.out.println(-1);
				return;
			}
		}

		long ans = C_sum;
		for(int i=0; i<(1<<N); i++) {
			long sum = C_sum;
			long[] Ai_sum = new long[M];
			System.arraycopy(A_sum, 0, Ai_sum, 0, A_sum.length);
			for(int j=0; j<N; j++) {
				//選択しない
				if((1 & (i >> j)) == 0) {
					sum -= C[j];
					for(int k=0; k<M; k++) {
						Ai_sum[k] -= A[j][k];
					}
				}
			}

			boolean ok = true;
			for(int j=0; j<M; j++) {
				if(Ai_sum[j] < X) {
					ok = false;
					break;
				}
			}

//			System.out.println("ans: " + ans);
			if(ok) {
				ans = Math.min(ans, sum);
//				System.out.println("ans_change: " + ans);
			}
		}

		System.out.println(ans);

	}

}

D問題は、そのまま順にたどっていくとTLEになるのは見えていたので、loopを作り、loopの余りをとることで計算時間を短縮しようとしましたが、TLE・・・。

原因は今の段階ではわかっていません。
この後、解説を見たいと思います。

結果

A~Cまでの3完です。
正直悔しいですね。
まだまだ、演習量が足りないので、増やせて行けたらと思います。

というわけで、ABC167の結果でした。
これからも引き続き、勉強を頑張っていきます。