2010 TCO Algorithm - Qualification Round 1

TopCoder

出張中だけどTopCoderは参加してみるテスト。今回はTCOの初戦。

  • -

Easy(250) : GirlsAndBoys

問題：GとBからなる文字列を"G...GB...B"または"B...BG...G"の形にソートするために必要なスワップ回数を答える

  • 2通りやってみてスワップ回数の少ない方を返すだけの簡単なお仕事
  • 書いたらサンプル通ったので提出。240.78点。


Medium(500) : RobotSimulation

問題：ロボットを与えられた操作で移動させたときに通過するマスの個数を答える

  • 高々10の長さの命令列(LLとかLRDUとか)を高々200000000回繰り返す。
  • どうせ数回繰り返せば等差数列的に増えていくようになるんだ・・・
  • ということで、9回繰り返して，num[9]+(num[9]-num[8])*(times-9)を返した。
    • num[i]はi回繰り返し後の通過マス数，timesは繰り返し回数
    • 当然ながらtimes<9ならnum[times]を返す
  • 書いたらサンプル通ったので提出。454.57点。


Hard(1000) : SequenceMarger

問題：与えられた各種数列をつなぎあわせてソートした数列のi番目の要素を返すクエリを作る。

  • 数列の種類は，
    • 等差数列：初項A，等差B，項数Cの3つ組で表現される。
    • 等比数列：初項A，等比B，項数Cの3つ組で表現される。
    • 規則性のないランダムな数列。
  • A, B, Cは正整数だけど64bit整数に収まる保証もない。
  • クエリは要素数50で，1番目から10^9番目までが指定されうる。
  • か・・・。ナイーブに計算したら当然死亡。
  • そこで、考えるのをやめてコンピュータ将棋の調整(?)に専念する事に。
  • 反省はしていない。
  • -

Challenge Phase

  • 一応見てみる。
  • 1000くらいしか落とす問題なさそうだと思ってたら早々に部屋の1000が落ちて行ったので諦めた。
  • -

結果：AC(240.78) / AC(454.57) / -- ，68/956位
レーティング：1757 -> 1843

というわけで、何とか通過。
さ、将棋将棋・・・。