Single Round Match 536

Single Round Match 536 Round 1 - Division II:

http://community.topcoder.com/stat?c=round_overview&er=5&rd=14728

2問通過。570.69点。レートは785から857へ。

Problem Status Points
250 BinaryPolynomialDivTwo Passed System Test 202.49
500 RollingDiceDivTwo Passed System Test 368.20
1000 MergersDivTwo Opened 0.0
  • 2問通した。目標は達成
  • 3問目は10分足らなかった
  • プラグインを使った
    • 快適になった
    • テンプレートを整理しよう
  • プラグインから生成された実装を整形するシェルスクリプトの効果も大きかった
  • 問題を予め理解してから実装を始めた
    • 目には見え辛いが効果が大きい
  • 例に予め目を通した
    • 先と同じく目には見え辛いが効果が大きい
  • 紙と鉛筆を用意した
    • 簡単な例を紙と鉛筆でテストしてから実装を開始した
    • 効果絶大
  • 次回の目標
    • 3問通す

BinaryPolynomialDivTwo

実装とテストで14分。202.49/250.00獲得。

  • 総括
    • 難しくはないはずなのだが、時間がかかってしまった
    • 実装はグダグダだった
  • コードリーディング
    • P(0)は反復を利用しないで求めることができる
    • sizeはforブロック内で定義すればよい
    int p_0 = a[0], p_1 = 0;

    for (int i = 0, size = a.size(); i < size; i ++)
      p_1 += a[i];

提出した実装は以下。

class BinaryPolynomialDivTwo {
public:
  int countRoots(std::vector<int> a) {
    int size = a.size();

    int p_0 = 0, p_1 = 0;

    for (int i = 0; i < size; i ++) {
      p_0 += a[i] * ((i == 0) ? 1 : 0);
      p_1 += a[i];
    }

    int count = 0;

    if (p_0 % 2 == 0)
      count ++;

    if (p_1 % 2 == 0)
      count ++;

    return count;
  }
};

RollingDiceDivTwo

実装とテストで19分。368.20/500点獲得。

  • 総括
    • 初めは各試行に関してダイスの目のポピュレーションを取ろうとした
    • ポピュレーションをテーブルに書き込み、大きな数値から抽出しようとしたところで各試行を予め整列したほうが合理的であることに気付き、実装し直した
137  == (sort) ==>  137
364  == (sort) ==>  346
115  == (sort) ==>  115
724  == (sort) ==>  247
                    ||`-- max(7, 6, 5, 7) = 7
                    |`--- max(3, 4, 1, 4) = 4
                    `---- max(1, 3, 1, 2) = 3
                                            `-- sum(7, 4, 3) = 14
  • コードリーディング
    • 今考えると内側の反復で降順(size - 1、size - 2、...、0)としている意味が全くない
    for (int i = 0, size = rolls[0].size(); i < size; i ++) {
      int dp = 0;

      for (std::vector<std::string>::iterator it = rolls.begin(); it != rolls.end(); ++ it)
	dp = std::max((*it)[i] - '0', dp);
      
      sum += dp;
    }

提出した実装は以下。

class RollingDiceDivTwo {
public:
  int minimumFaces(std::vector<std::string> rolls) {
    for (std::vector<std::string>::iterator it = rolls.begin(); it != rolls.end(); ++ it)
      std::sort(it->begin(), it->end());

    int sum = 0;

    for (int i = 0, size = rolls[0].size(); i < size; i ++) {
      int dp = 0;

      for (std::vector<std::string>::iterator it = rolls.begin(); it != rolls.end(); ++ it)
	dp = std::max((*it)[size - i - 1] - '0', dp);
      
      sum += dp;
    }
    return sum;
  }
};

MergersDivTwo

10分ほど足らなかった。が、大会中に40分ほど時間をかけていたので合計50分。時間かけ過ぎ。

システムテスト終了後に提出。

  • 総括
    • r = {5, -7, 3}、k = 2の組み合わせを紙で考えたのが良かった
(( 5 - 7) / 2 + 3) / 2 = (-1 + 3) / 2 =  1      where r = {5, -7, 3}, k = 2, m = 2
(( 5 + 3) / 2 - 7) / 2 = ( 4 - 7) / 2 = -1.5
((-7 + 3) / 2 + 5) / 2 = (-2 + 5) / 2 =  1.5

(5 - 7 + 3) / 3 = 1.5                           where r = {5, -7, 3}, k = 2, m = 3

式を展開すると

 5 / 4 - 7 / 4 + 3 / 2 =  1                     where r = {5, -7, 3}, k = 2, m = 2
 5 / 4 + 3 / 4 - 7 / 2 = -1.5
-7 / 4 + 3 / 4 + 5 / 2 =  1.5

 5 / 3 - 7 / 3 + 3 / 3 =  1.5                   where r = {5, -7, 3}, k = 2, m = 3
    • 感覚的により左側にいる数値にかかる係数がより小さくなることが分かる
    • 例えば負の値はできるだけ小さくなるのが望ましい。つまり負の値はより左側にあったほうが合計が大きくなりそうだ
    • 同様に大きな正の値はできるだけ大きくなるのが望ましい。つまり、正の値、特に大きな値はより係数の大きい右側にあるほうが合計が大きくなりそうだ
    • ではまず入力を整列してしまおう
 5 -7  3  == (sort) ==>  -7  3  5
    • r = {5, -7, 3}、k = 2の場合は以下の何れかが答えとなりそうだ
 -7  3  5      -7  3  5
 ~~~~~         ~~~~~~~~
  -2    5        0.333
  ~~~~~~~
    1.5
    • 合計は再帰関数で計算する戦略にする。例えば与えられたリストの数が5でk = 3である場合、3つ、4つ、5つの数を合成する選択肢がある。4つの数をまとめるとリストの数が2つとなってしまい、総合的に成立しないことに注意
 a b c d e      a b c d e      a b c d e
 ~~~~~          ~~~~~~~        ~~~~~~~~~
   f   d e         h    e          i
   ~~~~~~~         ~~~~~~
      g               -


 *) f = (a + b + c)         / 3
    g = (f + d + e)         / 3
    h = (a + b + c + d)     / 4
    i = (a + b + c + d + e) / 5

    - = 成立しない数
    • つまり、リストの数が1より大きくkより小さい場合は成立しない
    • リストの数が1である場合、要素の数が結果
    • リストの数がkと同じかそれ以上である場合は、左側からkからリストの数まで合成して、結果が最大になるものを選べばよい
    • 今考えればfoldlみたいじゃないか

実装は以下。

class MergersDivTwo {
public:
  double findMaximum(std::vector<int> revenues, int k) {
    std::sort(revenues.begin(), revenues.end());

    std::vector<double> r;

    for (std::vector<int>::iterator it = revenues.begin(); it != revenues.end(); ++ it)
      r.push_back(*it);

    return search(r, k);
  };

private:
  double search(std::vector<double> revenues, int k) {
    int size = revenues.size();

    if (size == 1)
      return revenues[0];

    if (size < k)
      return -1.0e+16;

    double rp = -1.0e+16;

    for (int i = k; i <= size; i ++) {
      double sum = 0.0;

      for (int j = 0; j < i; j ++)
	sum += revenues[j];

      std::vector<double> r;

      r.push_back(sum / i);
      
      for (int j = i; j < size; j ++)
	r.push_back(revenues[j]);

      rp = std::max(search(r, k), rp);
    }

    return rp;
  };
}