ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし

AOJ 2321: Butterfly

問題

問題文概訳

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

そこで、彼女はいくつかのデートを諦めることにした。 彼女の予定は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択なので、最悪でも216 = 25536である。O(2x)の場合は、だいたい220 (x = 20) くらいまでならセーフとおぼえておくといい。
  • あとは、スケジュールがかぶらないかどうかを実装すれば

ソースコード

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;
    }
}