AOJ 2321: Butterfly

問題

• http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2321

問題文概訳

クレールは男好きだ。彼女はマジの男好きである。 彼女は何人もの男を引き連れている。彼女はいつもデートをしている。 しかしある日、彼女はデートの予定をかぶらせてしまった事に気づいた！なんてこったい！

そこで、彼女はいくつかのデートを諦めることにした。 彼女の予定は1時間をひとつの単位として組まれている。 例えば、13:00から15:00までといった具合だ。 彼女は2人以上とデートの予定をしている。 例えば、10:00-12:00と14:00-16:00はアダムと、 12:00-13:00と18:00-20:00 はボブと、といった具合だ。 彼女は一度に2人以上とはデートできない。 すべてのデートは6:00から22:00の間に設定されている。

彼女は最大の満足度を得たいと考えている。 それぞれの男は、その男が要求するデートの時間を満たせば、 彼女に特定の満足度を与えてくれる。 例えば、アダムの与えてくれる満足度は100、 モブの与えてくれる満足度は200であれば、彼女の満足度は300となる。 あなたの仕事は、満足度の最大を求めることである。

入力は複数のデータセットからなる。 それぞれのデータセットは以下のような形式である。

N
Guy_1
...
Guy_N

Nは男の数 (1 \leq N \leq 100)、Guyは男についての情報である。 男についての情報は以下の形式で与えられる。

M L
S_1, E_1
...
S_M E_M

Mはデートの回数、Lは満足度、 S,Mはそれぞれのデートの開始時間と終了時間である。

問題概要と方針

• 男ごとに「満足度」と「デート時間」が決められている。デート時間がかぶらないように、かつ満足度が最高になるように男を選んだ時にの満足度を答えよ

• パッと問題を見ると最初に区間スケジューリングを思い浮かべるが、デートの時間が複雑なので、区間スケジューリングでは難しい。

• 男の数はせいぜい16人しかいないので、全探索で解ける。その男とデートするかどうかの2択なので、最悪でも2¹⁶ = 25536である。O(2^x)の場合は、だいたい2²⁰ (x = 20) くらいまでならセーフとおぼえておくといい。
• あとは、スケジュールがかぶらないかどうかを実装すれば

ソースコード

• http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1374564
• Java
• 今回は結構綺麗に実装できた気がする。

class Main extends MyUtil{
    public static void main(String[] args) throws Exception{
        while(true){
            // 入力には独自クラスを使っている。
            int n = readInt();
            if(n == 0) break;
            
            Guy[] guys = new Guy[n];
            for(int i = 0; i < n; i++){
                int m = readIntMap(0);
                int l = readIntMap(1);
                
                Guy guy = new Guy();
                guy.l = l;
                guys[i] = guy;
                for(int j = 0; j < m; j++){
                    int[] in = readIntMap();
                    guy.start.add(in[0] - 6);
                    guy.end.add(in[1] - 6);
                }
            }
            
            System.out.println(dfs(guys, 0, n, new boolean[16]));
        }
    }
    
    static int dfs(Guy[] guys, int i, int n, boolean[] schedule){
        if(i >= n) return 0;
        // 使わない場合
        int ret0 = dfs(guys, i + 1, n, schedule);
        
        // 使える場合は使ってもいい
        int ret1 = 0;
        if(canFill(schedule, guys[i])){
            boolean[] schedule_cp = cp(schedule);
            fill(schedule_cp, guys[i]);
            ret1 = guys[i].l + dfs(guys, i + 1, n, schedule_cp);
        }
        
        return Math.max(ret0, ret1);
    }
    
    /**
    * 予定を入れられるならtrue,入れられないならfalse
    */
    static boolean canFill(boolean[] schedule, Guy guy){
        for(int i = 0; i < guy.start.size(); i++){
            int s = guy.start.get(i);
            int e = guy.end.get(i);
            for(int j= s; j < e; j++){
                if(schedule[j]) return false;
            }
        }
        return true;
    }
    
    /**
    * guyで入力された男に対応するスケジュールをtrueで埋める
    */
    static void fill(boolean[] schedule, Guy guy){
        for(int i = 0; i < guy.start.size(); i++){
            int s = guy.start.get(i);
            int e = guy.end.get(i);
            for(int j = s; j < e; j++){
                schedule[j] = true;
            }
        }
    }
    
    public static boolean[] cp(boolean[] a) {
        boolean[] b = new boolean[a.length];
        for (int i = 0; i < a.length; i++)
            b[i] = a[i];
        return b;
    }
}