新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

参加記録:AtCoder Beginner Contest #15

[参加記録] AtCoder Beginner Contest#15

コンテストURL


Welcome to AtCoder Beginner Contest #015 - AtCoder Beginner Contest #015 | AtCoder

結果

  • A, B, C回答の300点
    • 楽勝じゃん!とかやっていたらDがひたすらTLE...orz

プログラム

A問題
  • 2つの文字列a, bが入力されるので、長い方の文字列を出力しろという問題。
package y141122.a;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        String a = scan.next();
        String b = scan.next();

        if (a.length() < b.length())
            System.out.println(b);
        else
            System.out.println(a);
            
        scan.close();
    }
}
B問題
  • N個の数字が入力されるので、0を除いた数値の平均(小数点切り上げ)を出力しろという問題。
package y141122.b;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int A[] = new int[N];
        int num = 0;
        int sum = 0;

        for (int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
            if (A[i] > 0) {
                num++;
                sum += A[i];
            }
        }

        System.out.println((int) Math.ceil((double) sum / num));

        scan.close();
    }
}
C問題
  • K択問題がN個あり、選んだ選択肢に割り当てられた数字をXORすると0になる場合があるか判定
package y141122.c;

import java.util.Scanner;

public class Main {

    static int N;
    static int K;
    static int T[][];
    static boolean flag = false;

    public static void saiki(int num, int cur) {
        if (flag) {
            return;
        }

        if (num == N) {
            if (cur == 0) {
                flag = true;
            }
            return;
        }

        for (int i = 0; i < K; i++) {
            if (num == 0) {
                saiki(num + 1, T[num][i]);
            } else {
                saiki(num + 1, cur ^ T[num][i]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        N = scan.nextInt();
        K = scan.nextInt();
        T = new int[N][K];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < K; j++) {
                T[i][j] = scan.nextInt();
            }
        }

        saiki(0, 0);

        if (flag) {
            System.out.println("Found");
        } else {
            System.out.println("Nothing");
        }

        scan.close();
    }
}
D問題
  • 幅Wの領域に、幅A[i]&重要度B[i]のスクショを貼り付ける
    • ただしスクショの枚数はK以下、幅はW以下でないといけない
    • 重要度が一番高いときの値を求める
  • 自分の解答
    • 普通に再帰
    • ここから頑張って枝刈りしたりメモ化とかやってみたがダメだったorz
import java.util.Scanner;
 
public class Main {
	static int W;
	static int N;
	static int K;
	static int A[];
	static int B[];
	static int rem[];
	static int max = 0;
	
	public static void saiki(int cur, int num, int wid, int imp) {
		if (cur == N || num == K) {
			max = Math.max(max, imp);
			return;
		}

		if (imp + rem[cur] <= max) {
			return;
		}

		saiki(cur + 1, num, wid, imp);
 
		if (num < K && wid + A[cur] <= W) {
			saiki(cur + 1, num + 1, wid + A[cur], imp + B[cur]);
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
 
		W = scan.nextInt();
		N = scan.nextInt();
		K = scan.nextInt();
		A = new int[N];
		B = new int[N];
 
		for (int i = 0; i < N; i++) {
			A[i] = scan.nextInt();
			B[i] = scan.nextInt();
			rem[0] += B[i];
		}

		for (int i = 1; i < N; i++) {
			rem[i] = rem[i - 1] - B[i - 1];
		}
 
		saiki(0, 0, 0, 0);
		
		System.out.println(max);
		
		scan.close();
	}
}
  • というわけで以下を参考にメモ化してみた。
    • AtCoder Beginner Contest 015 解説
    • dp[残り幅][残りスクショ数][現在見ているスクショ]で重要度の最大値をメモする
    • 無駄な分岐とかありそうだけどとりあえずACだったのでいいやw
import java.util.Scanner;

public class Main {
    static int W;
    static int N;
    static int K;
    static int A[];
    static int B[];
    static int dp[][][];

    public static int dfs(int useW, int useNum, int now) {
        if (useW < 0 || useNum < 0 || now == N) {
            return 0;
        }

        if (dp[useW][useNum][now] != -1) {
            return dp[useW][useNum][now];
        } else {
            if (useW - A[now] < 0 || useNum - 1 < 0) {
                return dp[useW][useNum][now] = dfs(useW, useNum, now + 1);
            } else {
                return dp[useW][useNum][now] = Math.max(
                        B[now] + dfs(useW - A[now], useNum - 1, now + 1),
                        dfs(useW, useNum, now + 1));
            }
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        W = scan.nextInt();
        N = scan.nextInt();
        K = scan.nextInt();
        A = new int[N];
        B = new int[N];
        dp = new int[W + 1][K + 1][N + 1];

        for (int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
            B[i] = scan.nextInt();
        }

        for (int i = 0; i <= W; i++) {
            for (int j = 0; j <= K; j++) {
                for (int k = 0; k <= N; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }

        System.out.println(dfs(W, K, 0));

        scan.close();
    }
}