SRM 463

SRM

Div2 Easy: BunnyPuzzle

うさぎが条件を満たしつつ移動できる場合の数を求める問題。

class BunnyPuzzle {
public:
  int theCount(vector <int> bunnies) {
    int n = bunnies.size();
    int result = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i-1; j >= 0; --j) {
        int l = bunnies[i] - bunnies[j];
        int count = 0;
        for (int k = i-1; k >= 0 && bunnies[k] >= bunnies[i]-2*l; --k)
          ++count;
        if (count == 1)
          ++result;
      }
      for (int j = i+1; j < n; ++j) {
        int l = bunnies[j] - bunnies[i];
        int count = 0;
        for (int k = i+1; k < n && bunnies[k] <= bunnies[i]+2*l; ++k)
          ++count;
        if (count == 1)
          ++result;
      }
    }
    return result;
  }
};

Div2 Medium: RabbitNumbering

n要素の整数列{a_i}が与えられるので, n要素の順列pの中で, すべてのi≦nに対して p_i ≦ a_i であるようなものの数を求めよという問題。

class RabbitNumbering {
public:
  int theCount(vector <int> maxNumber) {
    int n = maxNumber.size();
    sort(maxNumber.begin(), maxNumber.end());
    long long result = 1;
    for (int i = 0; i < n; ++i) {
      result *= maxNumber[i] - i;
      result %= 1000000007;
    }
    return result;
  }
};

Div2 Hard: Nisoku

n枚の数字の書かれたカードの山が与えられる。カードの中から任意に2枚取り出し, 2枚のカードに書かれている数字の和か積を書き込んだ新しいカードを山に加える。取り出した2枚のカードは捨てる。この作業を繰り返し, 山にあるカードが1枚になったとき, そのカードに書かれている数字の最大値をもとめよ, という問題。

class Nisoku {
public:
  double theMax(vector <double> cards) {
    int n = cards.size();
    double result = 0;
    sort(cards.begin(), cards.end());
    for (int i = 0; i <= n; i += 2) {
      double v = 1;
      for (int j = 0; j < i/2; ++j)
        v *= cards[j] + cards[i-j-1];
      for (int j = i; j < n; ++j)
        v *= cards[j];
      result = max(result, v);
    }
    return result;
  }
};

この問題のアルゴリズムそのものはそんなに難しくない。

  1. 偶数iに対して, カードの山を2つの集合 A = {i番目に小さいカードより小さいカード}, B = {Aに入ってないカード} に分ける.
  2. Aに含まれるカードから順に一番大きいカードと一番小さいカードを取り出し和をとったものの積を計算する。
  3. Bの含まれるカードの積を計算する。
  4. AとBで計算した数字の積がその分割でできる最大値なのですべてのiについてこの値を計算すればいい。

アルゴリズムはこれだけだが, これが正しく動くことの証明が結構大変だった。

[追記] 証明に山の分割について書いてなかったので追記。単純にある数字を閾値にして2つに分割するだけで最大値が見つかるのは, 以下の式が成り立つからです。

a≧0 かつ b≦c ならば (a+c)b ≦ (a+b)c
(証明) (a+b)c - (a+c)b = a(c-b) ≧ 0