cafelier@SRM

SRM490

SRM | 15:33 |

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 を押すと未確定部分があれば確定したあと、１文字Backspaceで削除
  • * を押すと、現在の変換候補を辞書順で一つ先に進める。一周したら一番早いのに戻る
  • 2～9 を押すと、未確定部分に１文字追加。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を縦に３枚くらい並べて (x1,20+y1%20) から (*, 40) への最短路
• (*,20) から (x2,20+y2%20) への最短路
• (*,20) から (*, 40) への最短路
• を求めて最短の繰り返しパターンを求めれば

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

撃墜タイム

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

感想

• 次まともな成績取れればJapanの国レート超えと総合ランキング1枚目入り行けそう。
• がんばるぞー