TopCoder SRM 479 (Div 1)

TopCoder 参加記録

あ、ニコ生オープンの参加記録書いてないや……
今回レート上がったのはいいんだけど内容は微妙。

Result

75.00 / 248.18 / Unopened
1撃墜0ミス


65位
1868->1971

Easy TheCoffeeTimeDivOne

問題

1番からn番まで番号のついた一列に並んだ座席がある。全ての座席には乗客が座っていて、スチュワーデスが全ての客にコーヒーまたはお茶を配る。
お茶を希望する客の座席の番号のリストが与えられ、それ以外の客はコーヒーを希望している。


スチュワーデスは1番の座席の隣にあるサーバーから出発して、飲み物を配る。
スチュワーデスはポットを一つだけ持っており、7人分のコーヒーまたはお茶の一種類だけが入る。

  • 隣の座席に移動するのに1秒
  • 客に飲み物を注ぐのに4秒
  • ポットに飲み物を入れるのに47秒

かかるとき、全ての乗客に希望の飲み物を注ぎ、サーバーまで戻るのにかかる時間を求めよ。


お茶を希望する乗客の数は47人以下であり、
n≦47777777とする。

試行錯誤

250からnがでかいなー。お茶の客が少ないからそこを上手く使うのだろうか。
配り方は遠い客から貪欲に配る方法でよさそうだけど、すげー場合わけめんどくさそう……


あれ、でもこれループ間に合わないか？TopCoderでは5000万は間に合う。
あ、配列もboolならメモリ制限間に合うから、お茶の客も全部配列に入れてしまおう。
んで、7人ずつ配る……


大分方針立てるのに苦戦したけど取り合えず書けた。
最大ケースでも時間が間に合うことを確認して送信。

Medium TheAirTripDivOne

問題開ける前にstandingsを眺める。みんなやっぱり250苦戦してるなー。

問題

1番の都市からn番の都市まで飛行機を乗り継いで行く。
飛行機の便のリストが
A B F T P
のような形式で与えられる。A,Bはそれぞれ出発・到着する都市の番号を表し、Fはその便が最初に出発する時刻を、PはF以降便が出る間隔を、Tは到着までにかかる時間を表す。
（最初の便はFに出発し、F+Pに二番目の便が、以下同様）


飛行機を乗り継ぐには、乗り継ぎ時間があるため、到着時刻をta,そこから搭乗する便の出発時刻をtbとするとtb＞taでなければならない。
tb-taをその乗り継ぎの安全度とするとき、使う便全ての安全度の最小値をその旅の安全度とする。


今、ある時間以下でn番の都市に行きたい。このときに可能な安全度の最大値を求めよ。
n≦477,
便のリストは47個以下、
F,T,Pは10億以下である。

試行錯誤

安全度を決めうちした後でダイクストラっぽい感じ？
ある空港Aに一番早い時間で着けば、それ以降の便には全て乗れるので、そのような解のみを考えればいい。だからダイクストラでおｋ.


で、安全度を二分探索してやれば多分時間も間に合う。
次の便の時間を求めるのに苦戦しつつ、書いた。なんかこう切り上げ書くのが苦手orz


サンプル合わない。
二分法間違えた？いや合ってる。ダイクストラ初期ノード入れてなかったorz
その他数箇所バグを直してサンプル合った！でかいケースも間に合うっぽい。送信。


その後Easy見直し。
うげえええええええコーナーケース間違ってる！！！！！
直したorzリサブミット。。。またかよ。。。酷い。


Medium見直し。
あれ、次の便の時刻の出し方本当にこれであってる？なんかサンプルは通ってるけど。
tmpがpで割り切れる場合・・・間違ってないか！？
やばい時間切れorz

Hard

あけてない

Challenge

Easyミスってる人一人落とした。
コーディング0点なのに5撃墜くらいしてる奴がいて撃墜するものがなくなった。

System Test

あれ？両方通った。