TopCoder SRM490 (Div. 2) 参加記

250と500のみ。

250 LuckyCounter

文字列の配列で、時刻が "HH:MM" の形で渡される。
それぞれの時刻に対し、"AA:BB" or "AB:AB" or "AB:BA" の形になっているものを数える問題。

やるだけ。
248.77 Passed System Test.
準備できてなくて、提出がかなり遅れた。

500 Starport

宇宙船が時間間隔Mでやってくる。時間間隔Nごとに、やってきてる宇宙船を転送する。
転送は、一度に何台でもできる。転送する時間と同時刻にやってきた宇宙船も転送される。
宇宙船の、転送までの待ち時間の平均を求める問題。

N=3,M=5だと、

N o--o--o--o--o--o--o--o--o--o--o　･･･
M o----o----o----o----o----o----o　･･･

となる。このときの待ち時間は、最初の宇宙船から順番に、
0, 2, 4, 1, 3, 0, 2, 4, 1, 3, ...
となっている。最初の0を除いて、左右の項を足し合わせると、5になる。
1サイクルの待ち時間合計は、5*2=10で、対象台数は5なので、10/5=2が平均待ち時間。
1サイクルの対象台数は、

・N<M のとき LCM(N,M) / MAX(N,M)
・N>M のとき LCM(N,M) / MIN(N,M)

となる。また、左右の項を足したときの値は、

・N<M のとき MIN(N,M)
・N>M のとき MAX(N,M)

となる。これで、待ち時間合計が次のように求まる。

・対象台数が偶数のとき 左右の項を足したときの値 * ( 対象台数 / 2 )
・対象台数が奇数のとき 左右の項を足したときの値 * ( ( 対象台数 - 2 ) / 2 ) + N / 2

後は、対象台数で割って返すだけ。
NMの場合分けがとっさに思い浮かばず、提出が30秒ほど間に合わなかった。
150.00 Challenge Succeeded

1000 Hieroglyphs

まだ見てない。

After System Test

oxx +6/-3 473.77
96位　1188 -> 1232
チャレンジでは、MEDIUMでTLEを狙って大きな素数をぶつけたり、大きな値をぶつけたりしてた。
2回ほど痛いミスをしてしまったけど、結果は+225なのでまあまあ。
最後の最後で、EASYで一人落とせたのがおいしかった。
そしてとうとう青になってしまった･･･！