SRM 547 Div II
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の最大値は106
- int型のまま乗算をしたらオーバーフローする
- SRM 438 Div II FeudaliasBattleでの経験が役に立った
- 純然に嬉しい
- これはチャレンジフェーズでのチェックどころではないだろうか?
- 10分ほど時間があったので考えてみた
- サンプルの一つが105である
- int型のまま乗算したらオーバーフローするな...
- サンプルを全て実行しないで提出する人はいないだろう
- んー
- チャレンジの戦略としては今ひとつか
- 一応チェックしてみよう...
- ん?
- 2つの実装がオーバーフローする実装であった
class MinimalTriangle { public: double maximalArea(int length) { return length*length*sqrt(3)/4; } };
- 念のため写経テストをした
- lengthが105でもオーバーフローした
- 念のため106でチャレンジした
- 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
- 組み合わせ数は最大で250
- とても無理
- ではメモ化再帰か動的計画法なのではないか?
- しかし、何を引数に、何を戻り値にするかが思いつかなかった
- 柱の高さの差の合計を戻り値に考えて実装を初めてみた
- 思った以上に複雑になった上、選んだ柱の高さを復元してロープの長さを計算を実装することができなかった
- 貪欲法的な考え方を始める
- 思えばこの時点で敗北が決まっていた
- まず全ての柱の高さを最大値で設定し、一本ずつ高さ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_; };
- Pythonを用いて視覚化してみた
- ただただギザギザになるだけでもないのだな...
- 他のコーダーの実装を見よう
- SRM547 Div2 Medium(500) PillarsDivTwo - 赤コーダーになりたい
- いつもすごいなぁ...
- うーん、ぱっと見て何をしているか検討もつかない...
- DP力が足りないのだな
- ...hypotってなんだろう?
- をを
- cmathの関数であった
- C 99で標準関数となったようだ
- いつも√x2 + y2を書いていた
- その必要がなくなってしまった
- SRM 547 Div2 Two PillarsDivTwo - y42soraの日記 - TopCoder部
- 解説がとても丁寧だ
- しかし、何をしているやらさっぱり分からない...
- よーし、頑張って読むぞ...