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

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし。たまにカメラの話や競馬の話も書きます。

AOJ 1306: Balloon Collecting

問題概要

これは、次々と落ちてくる風船をキャッチするゲームである。 プレイヤーは乗り物にのり、風船をキャッチする。 プレイヤーは乗り物を「右に移動させる」「左に移動させる」「その場で停止させる」の操作ができる。 風船が地面に着く時に、同じ座標に乗り物がいれば風船をキャッチできる。 もしキャッチできずに地面に落としてしまったらゲームオーバーだ。

ゲームの目的はすべての風船を取ることである。 乗り物は一度に風船を3つまで運ぶことができるが、 運んでいる風船の数が増えると乗り物はスピードが遅くなる。 風船をk個持っているときは、距離1だけ移動するのにk+1だけ時間がかかる。

あなたには、プレイヤーがすべての風船をキャッチできるか判断するプログラムを書いて欲しい。 もしキャッチできるなら最小の移動距離を、 不可能なら、キャッチが不可能になる最初の風船を出力せよ。 プレイヤーは最初に家の位置にいるとする。

方針

DPで解く。各風船について、「そのまま取りに行く」「家に風船を置いてから取りに行く」の2択がある。

DP[i][j] = i番目の風船を、j個風船持った状態でキャッチした場合の最小の移動距離

として計算していく。実際、i番目の風船をとった時の時間はt[i]で、位置はp[i] と決まっており、情報を更新するには前の風船の情報以外必要ないので、すべてのiについて値を保持しておく必要がない。

ソースコード

class Main {
    static Scanner sc = new Scanner(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception {
        while(true) {
            int n = sc.nextInt();
            if(n == 0) break;
            String[] ans = solve(n);
            System.out.println(ans[0] + " " + ans[1]);
        }
        sc.close();
    }
    
    static String[] solve(int n) {
        int[] p = new int[n];
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
            t[i] = sc.nextInt();
        }
        int inf = 1<<28;
        int[] prev_distance = new int[4];
        Arrays.fill(prev_distance, inf);
        
        // 最初の風船
        if(p[0] > t[0]){
            String[] ans = {"NG", "1"};
            return ans;
        }
        prev_distance[1] = p[0];
        
        
        for (int i = 1; i < n; i++) {
            if(getMin(prev_distance) == inf) {
                String[] ans = {"NG", ""+i};
                return ans;
            }
            
            int[] next_distance = new int[4];
            Arrays.fill(next_distance, inf);
            
            for(int j = 1; j < 4; j++) {
                if(prev_distance[j] != inf) {
                    // 家に戻って風船に行くまでの距離
                    int distance = p[i-1] + p[i];
                    // 家に戻って風船に行くまでの時間
                    int time = p[i-1] * (j+1) + p[i];
                    // 間に合う場合は値を更新
                    if(t[i-1] + time <= t[i]) {
                        next_distance[1] = Math.min(next_distance[1], prev_distance[j] + distance);
                    }
                    
                    // 家に戻らないパターン
                    // 風船がいっぱいでない
                    if(j != 3) {
                        distance = Math.abs(p[i] - p[i-1]);
                        time = distance * (j+1);
                        if(t[i-1] + time <= t[i]) {
                            next_distance[j+1] = Math.min(next_distance[j+1], prev_distance[j] + distance);
                        }
                    }
                }
            }

            prev_distance = next_distance;
        }
        int mindist = getMin(prev_distance);
        if(mindist == inf) {
            String[] ans = {"NG", ""+n};
            return ans;
        }else{
            int dist = mindist + p[n-1];
            String[] ans = {"OK", ""+dist};
            return ans;
        }
    }
    static int getMin(int[] a) {
        int ans = 1<<28;
        for (int i = 0; i < a.length; i++) {
            ans = Math.min(ans, a[i]);
        }
        return ans;
    }
}