新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

参加記録:AtCoder Beginner Contest #017

[参加記録] AtCoder Beginner Contest #017

コンテストページ


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

結果

  • A, B, C完答の301点
  • D問題はひたすらTLE/MLE orz

プログラム

A問題
  • 3つの問題の配点siと評価ei(1以上10以下)が与えられたとき、合計点を求める
    • 問題iの獲得点数はsi * ei割
    • 各問題の獲得点数を計算して合計
import java.util.Scanner;

public class Main {

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

		int[] s = new int[3];
		int[] e = new int[3];
		for (int i = 0; i < 3; i++) {
			s[i] = scan.nextInt();
			e[i] = scan.nextInt();
		}

		System.out.println((s[0] * e[0] + s[1] * e[1] + s[2] * e[2])/10);
		scan.close();
	}
}
B問題
  • 文字列Xがchoku語(空文字, もしくはchoku語Tの末尾にch, o, k, uのいずれかをつけた文字列)であるかを判定
    • c, h, o, k, u以外の文字が現れたらchoku語ではない
    • cの直後にhが来なければchoku語ではない
import java.util.Scanner;

public class Main {

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

		String X = scan.next();

		if ("".equals(X)) {
			System.out.println("YES");
			scan.close();
			return;
		}

		char[] ch = X.toCharArray();
		
		for (int i = 0; i < ch.length; i++) {
			boolean flag = false;
			switch(ch[i]) {
				case 'o':
					break;
				case 'k':
					break;
				case 'u':
					break;
				case 'c':
					if (i != ch.length-1 && ch[i+1] == 'h') {
						i++;
						break;
					}
					else {
						flag = true;
					}
					break;
				default:
					flag = true;
			}
			
			if (flag) {
				System.out.println("NO");
				scan.close();
				return;
			}
		}
		
		System.out.println("YES");
		
		scan.close();
	}
}
C問題
  • N個の遺跡とM種類の宝石がある。遺跡iには、探索によって得られる得点siと、得られる宝石の範囲li〜riが与えられる
    • M種類の宝石を全て集めないように遺跡を探索した場合、得られる最大の合計点を求める
    • いもす法を使う。解説では得点を配列に入れていたが、自分は+-1していた(その宝石を獲得できる遺跡の数が入る)
import java.util.Scanner;

public class Main {

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

		int N = scan.nextInt();
		int M = scan.nextInt();

		int[] l = new int[N];
		int[] r = new int[N];
		int[] s = new int[N];
		int sum = 0;
		int max = 0;
		
		for (int i = 0; i < N; i++) {
			l[i] = scan.nextInt() - 1;
			r[i] = scan.nextInt() - 1;
			s[i] = scan.nextInt();
			sum += s[i];
		}

		// いもす法用の配列
		int[] imosu = new int[M + 1];

		// 宝石を得られる範囲のうち、l[i]に1を足してr[i]+1に1を引く
		for (int i = 0; i < N; i++) {
			imosu[l[i]] += 1;
			imosu[r[i] + 1] -= 1;
		}

		// いもす用の配列の中での最小値
		int minImosu = imosu[0];

		// 配列の値を順々に足していく。同時に最小値を求める
		for (int i = 1; i < M; i++) {
			imosu[i] = imosu[i] + imosu[i - 1];
			minImosu = Math.min(minImosu, imosu[i]);
		}

		// いもす用配列で数が小さい=その宝石を得られる遺跡の数が少ない
		// その遺跡に行かなかった場合の合計点を求める
		for (int i = 0; i < M; i++) {
			if (minImosu == imosu[i]) {
				int tmpSum = sum;
				for (int j = 0; j < N; j++) {
					if (l[j] <= i && i <= r[j]) {
						tmpSum -= s[j];
					}
				}
				max = Math.max(tmpSum, max);
			}
		}
		
		System.out.println(max);
		scan.close();
	}
}
  • 見直していて思ったが、ケースによってはWAになりそう…
    • 大量の宝石が手に入るけど点数はとても低いような遺跡がたくさんあった場合、上のプログラムだとダメそう
    • やっぱり遺跡の獲得点数をいもす法用の配列に入れなきゃダメぽい
D問題
  • ひたすらTLE。動的計画法を使おうとしたもののうまく行かず。。。
    • 解説を読むと尺取法というのを使うと良いらしい。

以下解説読んだら追記予定。