SRM 547 Div II - agwの日記

Single Round Match 547 Round 1

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

250に4分。500に1時間ほどかけ、システムテストで落ちた。2つのチャレンジに成功。合計341.30点。レートは945から993へ。緑コーダー。

	Problem	Status	Points
250	MinimalTriangle	WA	241.30
500	PillarsDivTwo	WA	0.00
1000	RelativelyPrimeSubset	Unopened

250に4分。241.30点
500に57分。367.46点
- システムテストが通らなかった
残り10分
- 1000を開けずにチャレンジの準備をする
2回チャレンジ成功
また250しか解けなかった
- レートが落ちてもおかしくない
- 2問必ず通すようにしなければならない
次回の目標
- 2問通す

MinimalTriangle

http://community.topcoder.com/stat?c=problem_statement&pm=12056&rd=14739

4分。241.30点。

一辺の長さがlの正六角形にお互いに交差しない対角線を3本引く。そのとき出来る最小の三角形の面積を求める問題。

一辺の長さがlの正六角形がある

お互いに交差しない対角線を3本引く。考えられる対角線の引き方は大きく以下の二通り

対角線を引いたことで出来る三角形は2種類しかない
そのうち小さいほうの三角形はこちら

もう一方の三角形がこの三角形より大きいのは、以下の図を見れば明らかだ

では面積を計算しよう
三角形の面積の倍の平行四辺形を考えて、

その平行四辺形の半分の三角形を考える

点線の長さを三角形の高さhとすると、ピタゴラスの定理よりlとhから以下の式を立てることができる

hは以下のように求めることができる

ここから三角形の面積aを求める

提出した実装は以下(システムテストをパスした)。

class MinimalTriangle {
public:
  double maximalArea(int length) {
    double l = length;

    return l * l * sqrt(3) / 4;
  };
};

lengthの最大値は10⁶
- int型のまま乗算をしたらオーバーフローする
- SRM 438 Div II FeudaliasBattleでの経験が役に立った
  - 純然に嬉しい
これはチャレンジフェーズでのチェックどころではないだろうか?
- 10分ほど時間があったので考えてみた
- サンプルの一つが10⁵である
- int型のまま乗算したらオーバーフローするな...
- サンプルを全て実行しないで提出する人はいないだろう
んー
- チャレンジの戦略としては今ひとつか
- 一応チェックしてみよう...
ん?
- 2つの実装がオーバーフローする実装であった

class MinimalTriangle
{
  public:
  double maximalArea(int length)
  {
     return length*length*sqrt(3)/4;
  }

};

念のため写経テストをした
- lengthが10⁵でもオーバーフローした
- 念のため10⁶でチャレンジした
- 2回成功した
このチャレンジをしていなかったらレートが下がっていただろう
- しかし、たまたま運がよかっただけだ
うーん
- 早く2問確実に解けるように実力を付けようと誓うのであった

PillarsDivTwo

http://community.topcoder.com/stat?c=problem_statement&pm=12075&rd=14739

提出までに57分。367.46点。システムテストで落ちた。

数本の柱の高さの最大値とその間隔wが与えられる
- 初めのサンプルでは3本の柱の高さの最大値が何れも3で、その間隔が2である

実際の柱の高さは1から与えられた柱の高さまでである
- 柱の高さは整数
  - SRM中はこの条件を見逃していた...
この柱の先にロープをかける
- かけたロープの長さが最長になるように柱の高さを選ぶ
例えば全ての柱が高さ3である場合、ロープの長さは4となる

しかし、両脇の柱の高さに1を選んだ場合、ロープの長さは約5.66となる

他の例も考えてみよう
以下は柱の高さの最大値を5、2、5、2、5、柱の間隔を5としたものだ

ロープの長さを最大にする柱の高さは以下のように、5、1、5、1、5となるだろう

柱の間隔を3としても同様

柱の高さの差を考えればロープの長さが求まるように考えた
- 柱の高さの差をΔhとする

Δhを使えば、ロープの長さは以下の式で求められる

もう一つ例を考えてみよう

この場合の正解は以下だろう

それぞれの柱の高さは与えられた最大値か1を選べばロープの長さを最長化できそうに思えた
- 1つの柱の選択肢が2種類
- 与えられる最大の柱の数は50
- 組み合わせ数は最大で2⁵⁰
  - とても無理
ではメモ化再帰か動的計画法なのではないか?
- しかし、何を引数に、何を戻り値にするかが思いつかなかった
- 柱の高さの差の合計を戻り値に考えて実装を初めてみた
  - 思った以上に複雑になった上、選んだ柱の高さを復元してロープの長さを計算を実装することができなかった
貪欲法的な考え方を始める
- 思えばこの時点で敗北が決まっていた
まず全ての柱の高さを最大値で設定し、一本ずつ高さ1にしてみてロープの長さが最長になるような選択を続けるような実装を行った
- サンプルを通った
- 順番によって選択肢がはまってしまうように思えた
- しかし、もうこれ以上改善できないと判断し、提出

以下は提出した実装(システムテストを通らない)。

class PillarsDivTwo {
public:
  double maximalLength(std::vector<int> height, int w) {
    int size = height.size();
 
    double l = evaluate(height, w);
 
    while (1) {
      int t = -1;
 
      for (int i = 0; i < size; i ++) {
        int h = height[i];
      
        height[i] = 1;
       
        double ll = evaluate(height, w);
       
        if (ll > l) {
          l = ll;
          t = i;
        }
       
        height[i] = h;
      }
 
      if (t == -1)
        break;
 
      height[t] = 1;
    }
 
    return l;
  };
 
private:
  inline double evaluate(const std::vector<int>& height, double w) const {
    double l = 0.0;
 
    for (int i = 0, size = height.size(); i < size - 1; i ++) {
      double d = height[i+1] - height[i];
 
      l += sqrt(d * d + w * w);
    }
 
    return l;
  };
};

システムテストで落ちた
メモ化再帰で考え始める
あ
- 返り値にはそこまでの最長のロープの長さでよいではないか
  - 実数の戻り値をメモ化する発想がなかった...
- ではパラメータについて考えてみよう
一つ目のパラメータは配列の添字であるはずだ
他のパラメータが分からない...
気分を変えて再帰関数内での選択肢を考える
- 再帰関数ではそのときの柱の最大値か1を選ぶはずだ
あ
- もう一つのパラメータは選んだ柱の高さとすればよいのではないか?
- 「現在の高さ」と考えたほうがよいかもしれない

ここまで考えて実装したのが以下(システムテスト済)。

class PillarsDivTwo {
public:
  double maximalLength(std::vector<int> height, int w) {
    height_ = height;

    memo_.clear();

    return std::max(search(w, 1, height[0]), search(w, 1, 1));
  };

private:
  inline double distance(double dx, double dy) const {
    return sqrt(dx * dx + dy * dy);
  };

  double search(double w, int i, int j) {
    if (i == height_.size())
      return 0;
    
    std::pair<int, int> key(i, j);

    if (memo_.count(key))
      return memo_[key];

    double& r = memo_[key];

    r = distance(w, 1 - j) + search(w, i + 1, 1);

    if (height_[i] > 1)
      r = std::max(distance(w, height_[i] - j) + search(w, i + 1, height_[i]), r);
    
    return r;
  };

private:
  std::vector<int> height_;

  std::map<std::pair<int, int>, double> memo_;
};