D問題を貪欲法で解いてみた＆C問題

リアルタイム参戦ではありませんがA〜D問題まで一通り解いてみました。AとBは大体解説と同じようなコードになると思うので省略しますが、特にD問題は解説と違う方法が真っ先に浮かんだのでその方法について紹介します。

問題（外部リンク）

AtCoder Beginner Contest 080 - AtCoder Beginner Contest 080 | AtCoder

C問題

解説にある通り、時間の区分が固定で10、かつ店の数が多くても100しかないので全探索でも十分解くことができます。今回の場合はループの開始条件と終了条件を2進数で表記したほうが考えやすいと思ったので0bを使って書いてみました（1.7以降で使えるようになったそうです）。途中にアンダーバーを入れてあるのも単に見た目の問題ですが、桁数が大きいリテラルを記述する際には割と便利かもしれません。
なお、解説では本格的なビット演算をおこなっていますが、下記のコードでも一応間に合います。

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		int n = Integer.parseInt(input);
		
		boolean[][] open = new boolean[n][10];
		for(int i = 0; i < n; i++){
			String[] tmpArray = br.readLine().split(" ");
			for(int j = 0; j < 10; j++){
				if(tmpArray[j].equals("1")){
					open[i][j] = true;
				}
			}
		}
		
		int[][] profits = new int[n][11];
		
		for(int i = 0; i < n; i++){
			String[] tmpArray = br.readLine().split(" ");
			for(int j = 0; j < 10; j++){
				profits[i][j] = Integer.parseInt(tmpArray[j]);
			}
		}
		
		//ありえるのは1023通り
		int max = Integer.MIN_VALUE;
		for(int i = 0b1; i <= 0b11_1111_1111 ; i++){
			
			int tmpProfit = 0;
			//店ごとにチェック
			for(int j = 0; j < n; j++){
				int sameTime = 0;
				int tmp = i;
				for(int k = 0; k < 10; k++){
					if(open[j][k] && tmp % 2 == 1){
						sameTime++;
					}
					tmp /= 2;
				}
				
				tmpProfit += profits[j][sameTime];
			}
			
			if(max < tmpProfit){
				max = tmpProfit;
			}
		}
		System.out.println(max);
	}
}

D問題

ここでは解説とは全く違うアプローチを取りました。大雑把に言うと「番組を開始時間の早い順に並べ、使える録画機があればどれでもいいので録画させ、全部使えないなら新しい録画機を使う」という貪欲法です。
正直なところ証明はしていないのですが、直感には反しない方法だと思います。
また、解説にある方法だと1つでも放送時間が長い番組があったらたとえNやCが小さくてもそれなりのループ回数が必要になるのに対してこの方法なら放送時間に依存せずに計算が可能です。（一方、おそらくNやCが十分に大きければどちらの方法もあまり変わらなくなると思います）

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		String[] tmpArray = input.split(" ");
		int n = Integer.parseInt(tmpArray[0]);
		int c = Integer.parseInt(tmpArray[1]);
		
		Program[] programs = new Program[n];
		for(int i = 0; i < n; i++){
			tmpArray = br.readLine().split(" ");
			programs[i] = new Program(Integer.parseInt(tmpArray[0]), 
					Integer.parseInt(tmpArray[1]), Integer.parseInt(tmpArray[2]));
		}
		
		Arrays.sort(programs);
		
		//c+1以上の同時録画はありえない
		Program[] recorder = new Program[c + 1];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < c; j++){
				//録画機が使われていない場合
				if(recorder[j] == null){
					recorder[j] = programs[i];
					break;
				}
				//同じチャンネルかつ録画可能な場合
				else if(recorder[j].channel == programs[i].channel
						&& programs[i].start >= recorder[j].end){
					recorder[j] = programs[i];
					break;
				}
				//この分岐は違うチャンネルである前提なので0.5も考慮
				else if((double)programs[i].start >= recorder[j].end + 0.5){
					recorder[j] = programs[i];
					break;
				}
			}
		}
		
		//結局いくつ使ったか
		for(int i = 0; i <= c; i++){
			if(recorder[i] == null){
				System.out.println(i);
				break;
			}
		}
	}

}

class Program implements Comparable<Program>{
	int start;
	int end;
	int channel;
	
	public Program(int s, int e, int c){
		start = s;
		end = e;
		channel = c;
	}

	public int compareTo(Program p) {
		return this.start - p.start;
	}
}