"iz/競技プログラミング/PKU 3045 Cow Acrobats"の差分

2と8のリビジョン間の差分 (その間の編集: 6回)

http://poj.org/problem?id=3045

50000匹の牛がピラミッド作って喜ぶ問題。どんな牛だよ。

特殊な比較関数用意でソートして貪欲に解いた。なんか二分探索って話を師匠も工房の先生もしていたのだが・・・

二匹の牛について最大のリスクmaxRiskが最小になるような並べ方を考える。

牛C1のStrengthをS1, WeightをW1 牛C2のStrengthをS1, WeightをW2として

1. C1をC2の上に乗っけるとき maxRisk = max(-S1, -S2 + W1)

2. C2をC1の上に乗っけるとき maxRisk = max(-S2, -S1 + W2)

よって

max(-S1, -S2 + W1) > max(-S2, -S1 + W2)ならC2を下に

max(-S1, -S2 + W1) < max(-S2, -S1 + W2)ならC1を下にすればいい。同じならどっちでもいい。

ところでこれは-S2+W1と-S1+W2を比較するだけでいい。

なぜならS1, S2, W1, W2が正整数であるため

max(-S1, -S2 + W1) = -S1
max(-S2, -S1 + W2) = -S2

が同時に成立せず、

-S1 >= -S1 + W2
-S2 >= -S2 + W1

は常に成立するから。

次に3匹の並べ方について考える。

3匹C1(S1, W1), C2(S2, W2), C3(S3, W3)がいて、C1とC2ではC1を上にC2を下にするのが最適で、C2とC3ではC2を上にC3を下にするのが最適であることが分かっていると仮定する。このときC1とC3ではC1を上にC3を下にするのが最適なら、任意の二匹についてこの並べ方を適用できる。

仮定から、 -S2 + W1 >= -S1 + W2 -S3 + W2 >= -S2 + W3 2式を足して、 -S3 + W1 >= -S1 + W3 よってC1とC3ではC1を上にC3を下にするのが最適

これを比較関数にしてソートする。

maxRiskの最小値については牛を下から順に積んでいくと考える。

初期値をmaxRisk = -(一番下の牛のStrength)として、

ある牛C（Strength: S, Weight: W）をてっぺんに乗っけるとき下の牛すべてについてriskがWだけ増えるので

maxRisk = max(-S, maxRisk + W)

で計算できる。

   1 import java.io.*;
   2 import java.util.*;
   3 
   4 public class Main {
   5     BufferedReader br;
   6     Main() {
   7         br = new BufferedReader(new InputStreamReader(System.in));
   8     }
   9     public static void main(String[] args) {
  10         new Main().run();
  11     }
  12     class Cow {
  13         int W, S;
  14         Cow(int W, int S) {
  15             this.W = W;
  16             this.S = S;
  17         }
  18         public String toString() {
  19             return "W: " + W + " S: " + S;
  20         }
  21     }
  22     int N;
  23     Cow [] C;
  24     void init() {
  25         try {
  26             N = Integer.parseInt(br.readLine());
  27             C = new Cow[N];
  28             for (int i = 0; i < N; i++) {
  29                 String [] WS = br.readLine().split(" ");
  30                 C[i] = new Cow(Integer.parseInt(WS[0]), Integer.parseInt(WS[1]));
  31             }
  32             Arrays.sort(C, new Comparator<Cow>() {
  33                 @Override public int compare(Cow a, Cow b) {
  34                     return (-a.S + b.W) - (-b.S + a.W);
  35                 }
  36             });
  37         } catch (IOException e) {}
  38     }
  39     void run() {
  40         init();
  41         System.out.println(solve());
  42     }
  43     int solve() {
  44         int maxRisk = -C[0].S;
  45         for (int i = 1; i < N; i++) {
  46             maxRisk = Math.max(-C[i].S, maxRisk + C[i].W);
  47         }
  48         return maxRisk;
  49     }
  50 }

iz/競技プログラミング/PKU 3045 Cow Acrobats (最終更新日時 2012-12-17 17:25:09 更新者 iz)

-  ⇤ ← 2012-12-04 17:24:44時点のリビジョン2 → 
  サイズ: 1185
  編集者: iz
  コメント:
+   ← 2012-12-17 17:24:28時点のリビジョン8 → ⇥
  サイズ: 3453
  編集者: iz
  コメント:
-削除された箇所はこのように表示されます。
+追加された箇所はこのように表示されます。
 行 6:
-行 19:
+行 20:
-max(-S1, -S2 + W1) < max(-S2, -S1 + W2)ならC1を下に すればいい。同じならどっちでもいい。
+max(-S1, -S2 + W1) < max(-S2, -S1 + W2)ならC1を下にすればいい。同じならどっちでもいい。
-行 25:
+行 26:
-max(-S1, -S2 + W1) = -S1 max(-S2, -S1 + W2) = -S2 が同時に成立せず、
+ * max(-S1, -S2 + W1) = -S1
-行 27:
+行 28:
--S1 >= -S1 + W2 * -S2 >= -S2 + W1 は常に成立するから。
+ * max(-S2, -S1 + W2) = -S2
-行 29:
+行 30:
-任意の二匹についてこの並べ方を適用できるのでこれを比較関数にしてソートする。
+が同時に成立せず、

 * -S1 >= -S1 + W2

 * -S2 >= -S2 + W1 

は常に成立するから。

次に3匹の並べ方について考える。

3匹C1(S1, W1), C2(S2, W2), C3(S3, W3)がいて、C1とC2ではC1を上にC2を下にするのが最適で、C2とC3ではC2を上にC3を下にするのが最適であることが分かっていると仮定する。
このときC1とC3ではC1を上にC3を下にするのが最適なら、任意の二匹についてこの並べ方を適用できる。

仮定から、
-S2 + W1 >= -S1 + W2
-S3 + W2 >= -S2 + W3
2式を足して、
-S3 + W1 >= -S1 + W3
よってC1とC3ではC1を上にC3を下にするのが最適

これを比較関数にしてソートする。

maxRiskの最小値については牛を下から順に積んでいくと考える。

初期値をmaxRisk = -(一番下の牛のStrength)として、

ある牛C（Strength: S, Weight: W）をてっぺんに乗っけるとき
下の牛すべてについてriskがWだけ増えるので

maxRisk = max(-S, maxRisk + W)

で計算できる。


{{{#!highlight java
import java.io.*;
import java.util.*;

public class Main {
    BufferedReader br;
    Main() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    public static void main(String[] args) {
        new Main().run();
    }
    class Cow {
        int W, S;
        Cow(int W, int S) {
            this.W = W;
            this.S = S;
        }
        public String toString() {
            return "W: " + W + " S: " + S;
        }
    }
    int N;
    Cow [] C;
    void init() {
        try {
            N = Integer.parseInt(br.readLine());
            C = new Cow[N];
            for (int i = 0; i < N; i++) {
                String [] WS = br.readLine().split(" ");
                C[i] = new Cow(Integer.parseInt(WS[0]), Integer.parseInt(WS[1]));
            }
            Arrays.sort(C, new Comparator<Cow>() {
                @Override public int compare(Cow a, Cow b) {
                    return (-a.S + b.W) - (-b.S + a.W);
                }
            });
        } catch (IOException e) {}
    }
    void run() {
        init();
        System.out.println(solve());
    }
    int solve() {
        int maxRisk = -C[0].S;
        for (int i = 1; i < N; i++) {
            maxRisk = Math.max(-C[i].S, maxRisk + C[i].W);
        }
        return maxRisk;
    }
}
}}}