Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2012-06-26

TopCoder Single Round Match 547 Div 1 22:47 TopCoder Single Round Match 547 Div 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - TopCoder Single Round Match 547 Div 1 - nodchipのTopCoder日記 TopCoder Single Round Match 547 Div 1 - nodchipのTopCoder日記 のブックマークコメント

出先からの参加でJava+Eclipseで参加しました

Easy 250 Pillars

  • はい・・・?どうすんだこれ・・・?
  • 自明な解はO(xy)だけど、TLE・・・
  • 高速化できるのかなぁ
  • もしかしてしゃくとりメソッド風に計算すればオーダー下がる?
  • 片方を一つ上にずらすとき、すべて張り替えるのではなく、1本はずして1本追加すると考えてみる
  • はじめにx=1~x、y=1のときのロープの長さの総和を求めておく
  • 次にyを1つずつ上にずらしてく
  • Passed System Test
public class Pillars {
  public double getExpectedLength(int W, int X, int Y) {
    double sum = 0;
    for (int x = 1; x <= X; ++x) {
      sum += Math.hypot(W, x - 1);
    }
 
    double total = sum;
    for (int y = 2; y <= Y; ++y) {
      sum -= Math.hypot(W, X - y + 1);
      sum += Math.hypot(W, y - 1);
      total += sum;
    }
 
    return total / X / Y;
  }
}

Middle 500 RectangularSum

  • なんというか不思議な問題
  • 多分(left, top, right, bottom)で囲まれる領域の和を一発で求める必要がある気がする
  • とりあえず式を出してみる
  • 総和めんどくさい
  • 出た
  • 3項の積なので、Sの約数を適当に割り当てればいいのかな?
  • 考えてみる
  • とりあえず書き始めて見る
  • 明らかに時間が足りないorz
  • タイムアップorz

Challenge Phase

  • 250で二乗オーダーで計算している人を探してみる
  • ・・・
  • いるはずないか
  • 後は適当に500を見てみる
  • どうせ変な解答が見つかるわけ・・・
  • いた・・・
  • なんか解答の上限が1辺2000までとかいう変な制約つけてる
  • これ細長い領域で落ちるよね・・・?
  • 幅1で長さ最大のケースを投入してみる
  • ・・・
  • 失敗
  • あれ?
  • 手計算間違えた?
  • サイズを一桁下げてみる
  • ・・・
  • 撃墜成功!
  • 期待値的にこれ以上攻めても旨みがないので終了

System Test

Submissions Defenses Challenges SystemPoint Ratings
Coders Qnty / PointsQnty / PointsQnty / PointsTest Total Old / New
nodchip1 234.77 0 0.00 2 25.00 0.00 259.772062 2101

2100台まで上げることができました。うまくいくとあと2回くらいで赤ですが、あんまり期待できませんorz

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20120626
 |