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

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

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

は常に成立するから。

任意の二匹についてこの並べ方を適用できるのでこれを比較関数にしてソートする。

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 risk = -C[0].S;
  45         for (int i = 1; i < N; i++) {
  46             risk = Math.max(-C[i].S, risk + C[i].W);
  47         }
  48         return risk;
  49     }
  50 }

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

-  ⇤ ← 2012-12-04 17:23:19時点のリビジョン1 → 
  サイズ: 1184
  編集者: iz
  コメント:
+   ← 2012-12-04 17:39:52時点のリビジョン6 → ⇥
  サイズ: 2928
  編集者: iz
  コメント:
-削除された箇所はこのように表示されます。
+追加された箇所はこのように表示されます。
 行 5:
-特殊な比較関数用意でソートして貪欲に解いた。
なんか二分探索って話を師匠も工房の先生もしていたのだが・・・
+特殊な比較関数用意でソートして貪欲に解いた。 なんか二分探索って話を師匠も工房の先生もしていたのだが・・・
 行 9:
-牛C1のStrengthをS1, WeightをW1
牛C2のStrengthをS1, WeightをW2として
-行 12:
+行 10:
-. C1をC2の上に乗っけるとき
maxRisk = max(-S1, -S2 + W1)
+牛C1のStrengthをS1, WeightをW1 牛C2のStrengthをS1, WeightをW2として
-行 15:
+行 12:
-. C2をC1の上に乗っけるとき
maxRisk = max(-S2, -S1 + W2)
+. C1をC2の上に乗っけるとき maxRisk = max(-S1, -S2 + W1)

2. C2をC1の上に乗っけるとき maxRisk = max(-S2, -S1 + W2)
-行 19:
+行 17:
-行 20:
+行 19:
-max(-S1, -S2 + W1) < max(-S2, -S1 + W2)ならC1を下に
すればいい。同じならどっちでもいい。
+max(-S1, -S2 + W1) < max(-S2, -S1 + W2)ならC1を下にすればいい。同じならどっちでもいい。
-行 24:
+行 23:
 行 25:
-max(-S1, -S2 + W1) = -S1
max(-S2, -S1 + W2) = -S2
+ * max(-S1, -S2 + W1) = -S1 

 * max(-S2, -S1 + W2) = -S2
-行 28:
+行 31:
--S1 >= -S1 + W2
-S2 >= -S2 + W1
+ * -S1 >= -S1 + W2

 * -S2 >= -S2 + W1
-行 34:
+行 40:
+maxRiskの最小値については牛を下から順に積んでいくと考える。
-行 35:
+行 42:
+初期値を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 risk = -C[0].S;
        for (int i = 1; i < N; i++) {
            risk = Math.max(-C[i].S, risk + C[i].W);
        }
        return risk;
    }
}
}}}