Hatena::Grouptopcoder

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

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

2010-06-18

[][]SRM473 20:36 はてなブックマーク - SRM473 - TopCoderの学習のお時間

2010-06-18 10:00-(JST

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

平日午前中。

Levelタイトル試合中あとでひとこと
DIV1 250SequenceOfCommandsWA-TopCoder歴の中で過去最大のへぼいミス
DIV1 500RightTriangleAC 7min-正解率を見るとこの位が500の適正難易度なのか
DIV1 1000RooksPartyCompiled-途中まで書いたので記念Compile
  • Coding
    • 250
      • 無限遠に行かないときは、結局同じ位置でループになるからそれを調べればいい
      • 4回サイクル回せば最初と同じ向きになるので、4回通り実行し終わった後に位置が移動している⇔発散する と判定できる
        • なぜか3サイクルで元の向きに戻る可能性を考えてしまって12サイクル回してた…
      • 特に問題なく書けて一発でサンプル通った、提出
    • 500
      • 円に内接する三角形が直角三角形なのって斜辺が直径になる場合のみ、だよね…?
        • 今年の東大入試で似たのがなかったっけ
      • とりあえず、点の数が奇数ならば return 0;
      • どの位置が赤になるのかさえわかれば後は簡単
      • けれども点の数が10万なので、ナイーブにO(points^2)でやるとTLE
      • O(places + points) でやる方法を思いついた
        • まずは赤の点が重複したときに次の位置にずれるのは考えず、各位置に赤い点を重複して置いておく
        • 次に、placesを先頭から順にたどって、先に置いておいた赤の点を拾いつつ、1個ずつばら撒いていく
      • これでサンプル通った、提出
      • 500では見たことのない高い点数になった。不安…
      • とはいえコーナーケースも見つからないので次へ
    • 1000
      • しばらく問題を眺めて以下の洞察を得た
        • 同じ行・列には同じ色の駒しか置けない
        • 可能な配置に対して、その行や列の順序を入れ替えても配置可能なことは不変
        • 行・列の入れ替えを使って左上から順に色ごとにまとめていくことで、対角成分の周囲にだけ要素があるブロック行列みたいな形に変形できる
      • というわけで、色ごとに盤面の左上から順に長方形の領域に詰め込んでやって、詰め込み方ごとに行・列の並び替えが何通りあるかを足し上げると良いのではないかと考えた
      • たぶん工夫なしでやると遅いので memo[どの色まで使ったか][次の色のブロックを始めるx座標][同じくy座標] を状態空間とするメモ化DFSを書こうとした
      • しかし間に合わなかった
      • この方針で合ってるかどうかは未検証
  • Challenge
    • 250をざっと見てみたけど落ちそうなポイントは見あたらない
      • と思っていたら自分の250が落とされた…!
      • コピペミスで、dyと書くべき所がdxになっていたのが原因…これはひどい
    • 500を見る
      • 赤くする点を正しく決めれてなさそうなコードを発見
      • 即興でテストケースが作れたので投げてみると落ちてくれた
      • 1つずつナイーブに調べていそうなコードがあったのでTLEするかと思って最大ケースを投げてみたが落ちなかった
        • 次に入れるべき位置を随時更新しているのを見落としていた
  • System Test
    • 自分の500は通った
    • 部屋内で撃墜残しは500が1つ、どこで落ちてるのかはよくわからない

結果

  • スコア:0.00 + 465.97 + 0.00 + (50*1-25*1) = 490.97
  • 順位:122位/471人
  • レート:1829→1875

自己最高順位が逃げていった…。また次回がんばろう。今回くらいの速さを安定して出せて変なミスを減らせれば、レーティング2000どころか赤が見えてくる

なぜか強い人が500をあまり一瞬で解けていなかったようで、あと10秒速ければ全体で最速だった http://www.topcoder.com/tc?module=ProblemDetail&rd=14155&pm=10976

2010-06-11

[][] SRM472 02:22 はてなブックマーク -  SRM472 - TopCoderの学習のお時間

2010-06-05 27:00-(JST

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

珍しい時間

Levelタイトル試合中あとでひとこと
DIV1 250PotatoGameAC 29min+1回再提出-実験して推測
DIV1 600TwoSidedCardsCompiled-DPを書いて撃沈
DIV1 900ColorfulTilesOpened-正しく900とは珍しい
  • Coding
    • 250
      • Nimかー。サイズが大きいのでO(N)でも無理。単純なシミュレーションではない
      • 4進数だと思えば、1ターンごとにどれかの桁が1ずつ減っていくから、4進数にしたときの各桁の和が系の性質を定める値だ!
      • さくっと書いて提出、部屋内最速!
      • って、これ本当か? 怪しい気がしてならないので反例を探してみよう
      • うーむ、n=8のとき、先手が4を取ると後手の勝ちだが、1を取ると先手の勝ちになるぞ。繰り下がりが起きるから、各桁の和は使えないのか
      • ではなんだろう、わからない
      • わからない
      • サンプルがとても不親切なのは、いろんな例を載せてしまうとバレてしまうような単純な規則があるからではないか?
      • DPでn=1000まで計算させてみた
      • 明らかにパターンが見える…
      • どうしてそうなるかは置いておいてとりあえずサブミット
    • 600
      • 何も手がかりがつかめない
      • 600>900のこともあるから900を開いてみよう
    • 900
      • さっぱりわからない
      • これは正しく900点だろう
      • 600に戻ろう
    • 600
      • 前から1枚ずつ足していって、場合の数を更新していくDPコードを書いてみる
        • dp[i][j][k] で 「i枚目までを並べたときにj番目の位置の数字がkである場合の数」
      • 状態遷移にカードの裏表がちゃんと反映できないだめ解法だった
  • Challenge
    • 250は間違いなく自分と同じミスしている人がいるのでスピード勝負
    • 4で割った余りを足していっているようなコードを3つ落とせた
  • System Test
    • 自分の250は通った
    • 部屋内で撃墜残しはゼロ
  • スコア:119.70 + 0.00 + 0.00 + (50*3-25*0) = 269.70
  • 順位:65位/686人
  • レート:1697→1829

長らくレーティングの範囲が変わっていない

250の規則は、4 ≡ -1 mod 5 が関係してるのか

2010-03-17

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

2010-03-16 24:00-(JST

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

日本人が4人もいる部屋はたぶん初めて


Levelタイトル試合中あとでひとこと
DIV1 250ColorfulStringsAC 15min-算数+実装。好きなタイプの問題
DIV1 550ColorfulDecorationOpened-さっぱりわからなかった。グラフは知識もセンスも不足
DIV1 1000ColorfulMazeUnOpened--
  • Coding
    • 250
      • をを、入力範囲でかいぞ、どうしたら…
      • これはいつもの250よりだいぶ難しめに違いないのでじっくり問題を把握する
      • Colorfulかどうかの判定には1桁だけの部分も使うんですね
        • ということは同じ数字は2回以上出てこないので、n>=11 の場合は return "" でよい
      • あとは0123456789のpermutationを調べるだけ…?
      • しかし1回の判定がそれなりに重いので 10! はけっこう厳しくないか
      • 2桁以上の場合に0を含んでると、連続数字の積に0が複数回出てくることになるのでだめですね
        • ただし1桁の場合は別。チャレンジポイント
        • あと、kが1始まりなので、n=1,k=10 (答えは"9")でミスって""を返しちゃってる人がいるかも
      • というわけで 9! ならたぶん大丈夫…かな…? まあ書いてみよう
      • 1〜9からn個使うpermutationを効率的に列挙するには
      • next_permutation使うと泥沼になりそうだったのでシンプルに枝刈り再帰で
      • あとは頑張って書くだけ
      • 書いた、最大ケースも0.3秒で終わる。セーフ
      • 提出
      • 0と同様に1も使えないことはコード書いている最中に気づいたが、計算量は問題なさそうだったのでそのままにしといた
    • 550
      • 図がやばげ
      • 答えの取り得る範囲から二分探索かもとは思ったが
      • ある解候補に対して、その制約を満たす配置があるかどうかをどうやって判定できるかが全くわからない
      • 焼きなましてやろうかと一瞬考えるなど
      • あまりにわからないので歯を磨いたりしていた
  • Challenge
    • 250でわかりやすいコーナーケースがあって赤4人部屋なので撃墜は秒単位の争いになりそう
    • 1つ取れればラッキーというくらいか
    • と思っていたらそんなでもなかった
    • 250のn=1で落ちる人が次々と3人見つかって撃墜成功
    • ラスト20秒でもう1人非常に怪しそうな人を見つけて悩むも結局チャレンジせず
      • やはりシステムテストのn=1なケースで落ちてた
      • しかし確信は持てなかったので自重したのは正解だと思う
  • System Test
    • 自分の250は通った
    • 250の撃墜残しは3人
      • 1人は↑の人
      • 1人はn=1の場合にstringではなくてchar*にポインタ演算したみたいなものを返していて、なんか変な返値になっていた。これは予想外
      • 1人はよくわからないケースで落ちてた。これを撃墜するのは無理
  • スコア:198.83 + 0.00 + 0.00 + (50*3-25*0) = 348.83
  • 順位:92位/720人
  • レート:1829→1915

連続2桁は初めて

2010-03-02

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

2010-03-02 21:00-(JST

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

久々にうまくいったSRM

Random Coder Statsの言っている通り自分は数学ゲー向きなのだろうか。自身ではあまりそんな気はしていないが


Levelタイトル試合中あとでひとこと
DIV1 250RabbitNumberingAC 2min-greedyに掛け算するだけ
DIV1 500NisokuAC 24min+再提出1回-とても数学
DIV1 1000RabbitPuzzleOpened-時間たくさんあったが解いてる人が少なかったので諦め
  • Coding
    • 250
      • ソートして順番にやるだけー
      • キー捌きがいまいちで少しもたついてしまったが部屋内最速で驚いた
    • 500
      • 2以上のもの同士は足すよりも掛けた方が大きくなる
      • 2未満のものは…
      • 最小1.5だから2つ足すと3以上になって、
      • a>=3、b>=1.5の下では a*b >= a+b なので3つ以上を足し合わせることはない
      • つまり2未満のものからペアを作って足して、できたものを掛ければよい?
      • 積を大きくするペアの作り方は、できるだけ近い数がたくさんできるように両側から足していくのがよい
        • 個数が奇数の場合は一番大きいのを余らせる
      • これでサンプル通ったので提出
      • 500にしてはあっけなかったのでコーナーケースを考える
      • 最小サイズは2か
      • ん…? 2以上の数と2未満の数の場合どうなる?
      • 1.8と2.1… うわーん掛けるより足した方が大きいではないか
      • 結局いくつまでなら足した方が有利なんだ…?
      • ふむ。最大サイズ50なので、どこまでを足し算にするか全部調べちゃえ。いくつの数まで足し算が有利かとかを考えるよりそちらが確実
      • 再提出
    • 1000
      • 50分近くあったが
      • とりあえず初期状態でA-B-Cと並んでるとすると
      • A-B間の距離とB-C間の距離の最小公倍数最大公約数で系全体が割れるなぁとか
      • そんなことを考えてたけどまぁどうしようもないですね
      • Div1全体でもほとんど提出がないので諦めた
    • 500のテストケース考える
      • DivisionSummary見てたら、なんかめっちゃ500の再提出してる人が多い。あんな人やこんな人まで
      • さらにコーナーケースを考えるがそこまで変なのは見つからず、かえって不安になってしまった
      • 小さい数から足すのではなく中央を残しちゃってる人のために {1.5, 1.6, 1.7} とか
  • Challenge
    • うおっ、Challenge開始直後にサーバーが落ちた
    • ありゃーこれはノーコンテストになるかもね
    • Twitterの皆さんの様子を見てみよう
    • あれ、Twitterも落ちてる…?
    • うわーLANケーブルが抜けかかってただけやん
    • 何もできず
  • System Test
    • 2問とも通った
    • 部屋で撃墜されてない回答は全部通ってた。皆さんすごい
  • スコア:247.74 + 270.62 + 0.00 + (50*0-25*0) = 518.36
  • 順位:85位/651人
  • レート:1726→1829

そろそろ黄色中位に安定してきたと思って良さそう。そしてそびえたつ2000の壁

2010-02-14

[][]SRM461 16:22 はてなブックマーク - SRM461 - TopCoderの学習のお時間

2010-02-13 26:00-(JST

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

残念なマッチが続く


Levelタイトル試合中あとでひとこと
DIV1 300ColoringRectangleAC 26min-greedy、コピペミスで時間ロス
DIV1 500BuildingCitiesTLE 27minダイクストラ、最適化不足
DIV1 950FencingGardenOpened- 
  • Coding
    • 300
      • 大きい円から使っていけば良いだけでは…
      • 300だから何かトラップがあるんじゃないかと考えるも思いつかない
      • 仕方ない書くか
      • 赤から使う場合と青から使う場合と
      • サンプル合わない
      • デバッグするとしょうもないコピペミス発見
        • 今回みたいに、よくコピペで同じようなコードを二回書いちゃうことがあるけど、これ良くないスタイル
        • 多少めんどくても共通化してまとめるべきだ
      • サブミット
      • 問題の難易度的には250だと思う
    • 500
      • グラフっぽいなあ。
      • 出発点から始めて、街を作る数が少なくて済むところへ順次移動していくようなイメージ
      • 街と街との間を直接移動するときに新しい街を作らないといけない数を辺の重みとして、始点から終点までの最短距離を求めればよい、ということはダイクストラ
      • しかし移動距離の制約もあるので、もう一工夫必要
      • (現在位置、新しく街を作った数)の組をノードとして、状態ごとにそこに至るまでの最短移動距離を覚えておくとよいか。状態数は 50*数千 だからいけそう
      • 書けた、がサンプル合わない
      • ああ、maxTravelって通過する街の数だと思ってたけど、そうじゃなくて移動したユークリッド距離か。最高2000だからそりゃそうだ
      • 書き直すとサンプル合った
      • サブミット
      • ランダム最大ケースも一瞬で終わるからまぁ大丈夫かな?
    • 950
      • 開いたはいいが残り15分だし読解に時間がかかりそうなのでやめた
    • 300に戻ってトラップがないかを考える
      • 思いつかず
  • Challenge
    • 300で、円の直径が高さ以上かどうかを確認せずに計算しているせいでsqrt()に負数を渡してる人がいる
    • チャレンジしてみたら失敗
    • 後で赤い人が「C++ではsqrt()に負を渡しても例外は出ずにNaNが返るだけだよ。自分もたまにチャレンジする人へのトラップとして入れる」と解説してた。むきー
    • てかそれJavaでもそうじゃないか…。言語仕様に関わるとこへのチャレンジは確認してからやらないと
  • System Test
    • 300は通った
    • 500は落ちた
      • TLEでした。ランダム最大ケースと最悪ケースとの差はでかい
      • ほんのちょっとした最適化で通りました
  • スコア:184.17 + 0.00 + 0.00 + (50*0-25*1) = 159.17
  • 順位:276位/690人
  • レート:1705→1726

500通ってたら自己最高順位だったのにー。