Google Code Jam 2012 Round 1A

http://code.google.com/codejam/contest/1645485/dashboard

都合により一部のみ参戦。Problem Aを40分で解いた。20pt。2009位。

Problem Bは後で解いた。はまりにはまり、投稿が通るまで3時間ほどかかってしまった。

	Problem	Status	Points
10+10	Password Problem	correct+correct	10+10
15+18	Kingdom Rush		0+ 0
17+30	Cruise Control		0+ 0

Problem Aを40分で解いた
Problem Bを後で解いた
- はまりにはまり、3時間ほど考え込んでしまった
次回の目標
- A、Bを投稿する
- 1000位以内に入る

Password Problem

40分。Small、Largeともに一回の投稿。それぞれ10点を獲得し、合計20点。

じっくり考えてから実装した
- GCJはTopCoderに比べて時間があるからこそできた
- そうしなければパニックになって解けなかったように思う
- よい戦略であった
まず図を丁寧に書き、必要となるキー操作の数を考えた(AとBをそれぞれ4と10としている)

それぞれの事象が起こるのは、k個(k ≦ A)まで正確にパスワードを入力しているかにのみ依存する
- k個まで正確にパスワードを入力する事象をXとすると、その確率は

- この確率を先に計算しておく
これを用いるとそれぞれの方法の期待値は以下のように求めることができる

これらの期待値の中で一番小さいものを選んでやればよい
- 今考えるに、一つ目の式は二つ目の式の特殊なケースであった(i = 0)

提出した実装は以下。

#include <iostream>
#include <iomanip>
#include <vector>


int main(int argc, char** argv)
{
  int T;

  std::cin >> T;

  for (int t = 0; t < T; t ++) {
    int A, B;

    std::cin >> A >> B;

    std::vector<double> p(A), c(A, 0.0);

    for (int i = 0; i < A; i ++)
      std::cin >> p[i];

    c[0] = p[0];

    for (int i = 1; i < A; i ++)
      c[i] = c[i-1] * p[i];

    double s1 = 0.0;

    s1 = ((B - A) + 1 + 0) * c[A-1] + (((B - A) + 1) + (B + 1)) * (1 - c[A-1]);

    double s2 = A + B + 1;

    for (int i = 1; i < A; i ++)
      s2 = std::min((i + (B - A + i) + 1) * c[A-i-1] + (i + (B - A + i) + 1 + B + 1) * (1 - c[A-i-1]), s2);
    
    double s3 = 1 + B + 1;

    std::cout <<
      "Case #" << t + 1 << ": " <<
      std::fixed <<
      std::setprecision(6) <<
      std::min(std::min(s1, s2), s3) << std::endl;
  }
}

無駄が多い
- 後で整理する
整理してみた
- どうも奇麗に書けない

#include <iostream>
#include <iomanip>
#include <vector>


#define ALL(x) (x).begin(), (x).end()


int main(int argc, char** argv)
{
  int T;

  std::cin >> T;

  for (int t = 0; t < T; t ++) {
    int A, B;

    std::cin >> A >> B;

    std::vector<double> p(A + 1);

    p[0] = 1.0;

    for (int i = 0; i < A; i ++) {
      double x;

      std::cin >> x;

      p[i + 1] = p[i] * x;
    }

    double s = 1 + B + 1;

    for (int i = 0; i <= A; i ++)
      s = std::min((i + (B - A + i) + 1        ) *        p[A-i] +
                   (i + (B - A + i) + 1 + B + 1) * (1.0 - p[A-i]),
                   s);

    std::cout <<
      "Case #" << t + 1 << ": " <<
      std::fixed << std::setprecision(6) << s << std::endl;
  }
}

Kingdom Rush

後で解いた
貪欲法を用いた
- 2-star ratingのレベルを完了できるだけ完了してしまう
- 完了できる2-star ratingのレベルがなくなったら、1-star ratingのレベルを完了することにより、点数を稼ぐ
- その際、解ける1-star ratingの中で、2-star ratingがより大きいもの選ぶとよい
  - 小さい2-star ratingを直接完了したほうが1-star rating => 2-star ratingと完了するよりも回数が少ない。つまり、有利であるのでその機会をより多く残してやるようにする
はまりにはまって投稿が通るまで3時間かかった
- 整列に使った関数オブジェクトが原因らしい

class comparator {
public:
  bool operator()(const level_t& a, const level_t& b) const {
    if (a.first < b.first) {
      return true;
    }
    else if (a.first == b.first) {
      return a.second > b.second;
    }
  };
};

この関数オブジェクトを伴って以下のような整列を行っている
- 1-star ratingを完了するのに必要な点数がより小さいものをより左へ
- 1-star ratingが等しい場合、2-star ratingを完了するのに必要な点数がより小さいものをより左へ
が、この整列をすると答えが合わないようだ
- 単純に2-star ratingを完了するのに必要な点数がより大きいものから整列した場合のほうが効率がよかった
- 後で調べる
調べてみた
持ちスターが7で選択肢が(6, 8)、(7, 12)である場合を考える
- この選択肢の何れが直接2-star ratingを完了しやすいか考えてみよう
  - (6, 8)は持ちスターが8のときに完了できるが、(7, 12)は持ちスターが12でないと完了できない
  - つまり、(6, 8)を残したほうが後々の局面で得点的に有利となる
  - そのため、2-star ratingの数が大きければ大きいものを選んでおいたほうがよい
  - すっきりした
さらに、上述した関数オブジェクトにはとんでもないバグがあった
- 条件に合致しない場合に不定値を返してしまう
  - 思い起こしてみるに、これにはまったことが何回もあった気がする
  - よくやるのは
    - intを返す関数オブジェクトを書いてしまう(qsortと勘違いしている)
    - 不定値を返す関数オブジェクトを書いてしまう(今回のケース)
- 正しくは以下

class comparator {
public:
  bool operator()(const level_t& a, const level_t& b) const {
    if (a.first < b.first) {
      return true;
    }
    else if (a.first == b.first) {
      return a.second > b.second;
    }
    else {
      return false; /* SHOULD EXPLICITLY RETURN false */
    }
  };
};

実装は以下。

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <list>


#define ALL(x) (x).begin(), (x).end()


typedef std::pair<int, int> level_t;

typedef std::list<level_t> level_list_t;


class less_equal1st {
public:
  less_equal1st(int x) : x_(x) {};

public:
  bool operator()(level_t& level) const {
    return level.first <= x_;
  };

private:
  int x_;
};

class less_equal2nd {
public:
  less_equal2nd(int x) : x_(x) {};

public:
  bool operator()(level_t& level) const {
    return level.second <= x_;
  };

private:
  int x_;
};

class comparator {
public:
  bool operator()(const level_t& a, const level_t& b) const {
    return a.second > b.second;
  };
};


#define INF (1 << 30)


int solve(level_list_t levels)
{
  int s = 0, c = 0;

  while (levels.size()) {
    level_list_t::iterator it = std::find_if(ALL(levels), less_equal2nd(s));
    
    if (it != levels.end()) {
      if (it->first < INF) {
	s += 2;
      }
      else {
	s += 1;
      }

      c ++;

      levels.erase(it);

      continue;
    }

    levels.sort(comparator());

    it = std::find_if(ALL(levels), less_equal1st(s));
    
    if (it != levels.end()) {
      it->first = INF;

      s += 1;
      c ++;
      
      continue;
    }

    return -1;
  }

  return c;
}

int main(int argc, char** argv)
{
  int T;

  std::cin >> T;

  for (int t = 0; t < T; t ++) {
    int N;

    std::cin >> N;

    level_list_t levels;

    for (int i = 0; i < N; i ++) {
      int a, b;

      std::cin >> a >> b;

      levels.push_back(std::make_pair<int, int>(a, b));
    }

    int c = solve(levels);

    if (c >= 0) {
      std::cout << "Case #" << t + 1 << ": " << c << std::endl;
    }
    else {
      std::cout << "Case #" << t + 1 << ": Too Bad" << std::endl;
    }
  }
}