Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2011-03-29

[]SRM500 01:23 はてなブックマーク - SRM500 - TopCoderの学習のお時間

2011-03-19 25:00-(JST

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14429&rm=307532

500回記念大会


Levelタイトル試合中あとでひとこと
250MafiaGameAC 21min-簡単なはずだけど難しい問題、面白い
500FractalPictureCompiledひどいバグにはまった
1000ProductAndSumUnOpened-簡単めだったらしい

  • Coding
    • 250
      • 問題文長い…けどそんなに読むのは詰まらなかった
      • 投票対象の人数=投票者数なので
      • 固定票が2票以上の人がいたら固定票最多タイの人だけが残る
      • 逆に2票以上の人がいなかったら全員1票で並ぶ
      • と考えると簡単だが
      • そのへん気づいていなかったので、
      • 1回目で決着がついた場合は~
      • とか
      • 1回目の投票結果の最大票数が固定票のみの最大数と同じ場合は~
      • とかの無駄な場合分けをいっぱい書いていた
      • 提出直後に全部気づいたが再提出で点数下がると悲しいのでよーく見直して問題ないことを確認
    • 500
      • 調べる四角形の座標が整数なのに着目
        • 整数座標にある枝とそれ以外の枝の部分を分けて計算するとよさそう
        • 枝の長さが1になるまでフラクタルを進めて、
        • 残りの非整数な長さの枝は1*1のマスに分けてやるとすべて計算対象に含まれるか含まれないかのどちらか
        • そして、長さ1の枝から派生する部分(1*1のマス内に収まる部分)の合計長さは厳密に計算可能
      • というわけであとはひたすら実装
      • フラクタルを作っていくところで枝の状態がどうにもおかしい
      • デバッグしてもなかなか間違いが見つからない
      • 終了2分前に、+と=をタイプミスしていて、不意なフィールドへの代入が起きて状態を壊しているのに気づく…
      • 間に合わず
      • その他小さいミスが2つあったけど十分普通のデバッグで対処できるようなものだった。残念
      • 前日にTwitterこう言っていたらまさにそんな感じのが出てくれた
      • こういう問題は結構好きですよ
  • Challenge
    • 250で投票を1ターンしかさせていない人を発見、撃墜
    • 調子にのってもう一人チャレンジしたら今度は自分がルールを勘違いしていた、失敗
  • System Test
    • 250は通った

結果

  • スコア:171.49 + 0.00 + 0.00 + (50*1-25*1) = 196.49
  • 順位:59位/867人
  • レート:2121 -> 2204

このスコアでこのレート上昇とは…

けどこれまでの自分の結果を思い返すとこういう回(Easy/Mediumともに難しめ)はだいたい上がっている気がする

記念のTシャツやらバッヂ?やらが当たったらしい。わーい。

[]SRM499 00:47 はてなブックマーク - SRM499 - TopCoderの学習のお時間

2011-03-08 25:00-(JST

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14428&rm=307408

うさぎ回。


Levelタイトル試合中あとでひとこと
250ColorfulRabbitsAC 6min-慎重に
550WhiteSpaceEditingTLE 34minああ、またTLEだったよ。あいつは計算量を見積もらないからな
1000ImpossibleGameOpened-途中まで

  • Coding
    • 250
      • 単純に数えればよさそうだけど
      • 最近簡単な問題でもミスしまくりだったので慎重に取り組む
      • サンプルを一つずつ丁寧に検証していって、合っている確信が持ててから書き始める
      • 提出時の部屋内順位は真ん中くらいでそう早くはないけど十分
    • 550
      • O(N^5)でやった。大枠はたぶんwrongさんのと同じような感じ
      • どんなふうにその考えに至ったかを書いておく
      • 手元でルールに従っていろいろ操作してみると、これは範囲DPだなーと思う
        • ある列を二つに割ったら、その片方が1列目~10列目をカバー、もう一方が11列目~50列目をカバー、と部分問題に分解できる形になるので
        • 計算量的にもなんかそれらしい
      • しかしこれだけでは、状態数が「i列目から」「j列目までの範囲を作るのに」「長さkの列から始めたときの必要な操作数」で50*50*100万になって無理
      • 行き詰まったので単純なケースを考えてみる。これすごく重要
        • 1列しかない場合…はさすがに自明すぎるので
        • 2列しかない場合:その2列の目標長さをa,b(a<b)とする
        • この2列を作るため、長さxの列から始めたときに必要な操作数は、
        • x < a の場合:まずxをaまで伸ばして、分裂させて、bまで伸ばすので (a-x) + 1 + (b-a) = b-x+1回
        • a <= x <= b の場合:まず分裂させて、片方はaまで縮める、片方はbまで伸ばすので 1 + (x-a) + (b-x) = b-a+1回(定数)
        • b < x の場合:x<aの場合と同じように考えて x-a+1回
        • で、結局これは、線形関数を連結した形(折れ線グラフ)
      • 列が2個じゃなくてもっと増えた時も、線形なのは変わらないだろう、きっと。(証明はしてません)
      • 折れ線グラフの最小値だから、線が折れ曲がるところだけ、つまりどれかの列の目標長さのところだけ調べれば良い!
        • あと開始状態の長さ0も追加で必要だけど
      • というわけで状態数が50*50*50に落ちた
      • だから計算量O(N^3)だと思ってテキトーにメモ化再帰書いて最大ケースもテストせず提出してしまった
      • 各状態での最小値を計算するのにO(N^2)ループしてるので全体ではO(N^5)だ…
    • 1000
      • 文字の順番は関係ないことはすぐ気づいて、
      • 強連結成分分解してどうのこうのかなあ、といったところまで
  • Challenge
    • 250のコーナーケース落ちを探すも見つからず
  • System Test
    • 250は通った
    • 550が落ちた
      • TLE
      • メモ化再帰をDPに書き換えると最悪ケース1.7秒で通りました(Java

結果

  • スコア:238.28 + 0.00 + 0.00 + (50*0-25*0) = 238.28
  • 順位:329位/755人
  • レート:2179 -> 2121

半分より上でもこの落ちっぷり。おそろしい

SRMC++に切り替えようかなぁ

[]SRM497 00:14 はてなブックマーク - SRM497 - TopCoderの学習のお時間

2011-02-11 11:00-(JST

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14426&rm=307222


Levelタイトル試合中あとでひとこと
250PermutationSignatureAC 52min-いつもは解けるタイプなはずのが大混乱
550CssRulesOpened-要実装で残念
1000ModuleSequenceUnOpened-見てない

  • Coding
    • 250
      • 数列が作れないというパターンはなさそう
      • 適当に法則を考えて実装するがことごとく外れる
      • サンプル通ったので提出したが全然違っていることに気づいて
      • さらにごちゃごちゃ修正してなんとかそれっぽのができたので再提出
      • 今回通した人の中では一番ひどいコードなのではないか
      • Dの範囲だけ反転させるというシンプルな解法はいつもだったら気づいてそうだけどなぜこの回は…
    • 550
      • 250で時間使いまくったのでひらめき一発で解けるようなのだったらいいなーと思って開いたら文法規則が書いてあるのが見えて絶望
      • XTHMLのパースをやったくらいのところで時間切れ
  • Challenge
    • 呆然としていた
  • System Test
    • 通った

結果

  • スコア:79.22 + 0.00 + 0.00 + (50*0-25*0) = 79.22
  • 順位:423位/550人
  • レート:2348 -> 2179

じわじわ上げてきてたのが一気に持って行かれた。さすがにここまで来るとワンミスが致命傷

 |