Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-12-09

SRM490

| 15:33 | はてなブックマーク -  SRM490 - cafelier@SRM

SRM490 の成績・ソース (要ログイン) : AC/AC/- : 期待値怖い

250開く

  • 入力
    • Nd :: int に収まる程度の正整数
    • Na :: int に収まる程度の正整数
  • 出力
    • E[ -X mod Nd ] where X={0, Na, 2Na, ...}
  • 『Na分おきに港に宇宙船が到着します。Nd分おきに出発できます。待機時間の期待値は?』

  • 期待値…ぐぐぐ
  • 愚直にやると?
  • lcm(Nd, Na) までに到着する宇宙船を考えれば、そこからあとは同じ事の繰り返しなので
  • そこまでの待機時間の平均を求めればそれが答え

  • lcm(Nd, Na) まで Na 分おきに来る宇宙船を数えると、最悪 Nd 隻あります。
  • それはTLE

  • なにか規則性があって和の公式とかそういうので求まるんだよね、きっと。
  • 具体例で考えよう。Nd=5, Na=3。
    • 0, 3, 6, 9, 12, 15...
  • に着くので、待機時間は
    • 0, 2, 4, 1, 3, 0...
  • という繰り返し。答えは (0+2+4+1+3) / 5。

  • もしかしてこれは、0~Nd-1まで全部の総和/Nd、で終わりだったりしない?
  • 他のサンプルではどうだろう。
  • はい全然成り立ちませんでした。

  • むう
    • 0, 2, 4, 1, 3, 0...
  • というのは、0 から Na ずつ減っていって、また 0 に戻るまでのループ
  • という形をしているのは確かなので、等差数列の和の公式っぽいんですよ、絶対。

  • でもなあ。0-Na-2Na-3Na-4Na-... を求めて、mod Nd した分適当に調整、というのも難しそうだ

  • わからない。期待値怖い。
  • いや待て
    • 0, 2, 4, 1, 3, 0...
  • この数列は、0 に戻るまでは絶対に重複がない。あったとするとそこでグルグルループしてしまっておかしなことに。
  • ということは
    • 0 ~ Nd-1 のうち、ここに出てくる物だけを足し算 / 出てくる個数
  • が答え!
  • なにが出てくるかというと、
  • gcm(Nd,Na) の倍数が全部出てくる!

  • 解けた
  • 0~Nd/gcd(Nd,Na)-1 までの総和 * (Nd/gcd(Nd,Na))
  • よし、サンプルと合う。submit!

550開く

  • 問題長い…
  • IMEみたいなもので文字を入力してます。
    • → を押すと未確定部分を確定
    • C を押すと未確定部分があれば確定したあと、1文字Backspaceで削除
    • * を押すと、現在の変換候補を辞書順で一つ先に進める。一周したら一番早いのに戻る
    • 2~9 を押すと、未確定部分に1文字追加。2はaかbかc、3はdかeかf、…みたいにアルファベットが割り当てられてて、変換辞書に入ってる単語のprefixのうち、辞書順最速でこれにマッチする文字列が未確定部分となる。
  • 入力したい文字列を入力する最短手数を求めよ』
    • 最長50文字
    • 辞書は2500文字でスペース区切りで来る

  • 実装するだけ問題じゃなイカ
  • キーの押し方を再帰で全探索するので十分。
    • 確定部分が目標にあってないときはCで消しまくるしかないし、
    • 未確定部分は必ず入力辞書のprefixなので
    • 目標文字列の長さ × 辞書単語のprefixの個数
  • くらいしか探索空間がない。メモ化したら終わる。

  • C や * で同じ状態に戻ってくる遷移があるので、それで無限ループしないように
    • if( state in memo ) return memo[state];
    • memo[state] = -1; // ここ重要
    • return memo[state] = 普通に計算;
  • と普通のメモ化再帰に一行入れれば完璧

  • できた。
  • submit。かなり時間食ってしまった…

1000開く

  • 『最大20×20のパターンが縦に無限に繰り返される迷路があります。(x1,y1)から(x2,y2)の最短経路の長さはなーに?』
    • y1,y2はlong longに収まる程度

  • y1とy2が近ければ本当にただの最短路
  • 遠ければ… y1<y2 として
    • y1から、今いるマップの20x20の下の最上位ラインにいく
    • さらにその下の最上位ラインにいく
    • ...
    • 繰り返し
    • ...
    • y2のある20x20の最上位ラインに。
    • そこからy2へ

  • という動きをするはずで
  • 20x20を縦に3枚くらい並べて (x1,20+y1%20) から (*, 40) への最短路
  • (*,20) から (x2,20+y2%20) への最短路
  • (*,20) から (*, 40) への最短路
  • を求めて最短の繰り返しパターンを求めれば

  • 上の3つを求めたところでタイムアップ

撃墜タイム

  • 250をTLEする人がいることを想定しておくべきだった…
  • 互いに素な巨大な数2つ、を探している間に全部落とせるの落とされた

感想

  • 次まともな成績取れればJapanの国レート超えと総合ランキング1枚目入り行けそう。
  • がんばるぞー
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20101209
 | 

presented by cafelier/k.inaba under CC0