Hatena::Grouptopcoder

hotpepsiの練習帳

2017-03-08

Codeforces #398 (Div. 2)

00:13

A. Snacktower

問題

  • 1からNまでの大きさのN個のスナックが順不同で落ちてくる
  • 大きいものの上にそれより小さいものが置ける
  • 1つずつ落ちてきたものを手戻りしないように置くとき、どれを置くかを求める

方針

B. The Queue

問題

  • パスポートを発行してもらいに旅券課に行く
  • 受付には1人だけいて、真夜中からS分後から業務を開始し、F分間だけ窓口業務を行う
  • 一人あたりT分かかる
  • 終了までの残り時間がT分未満のときは受けつけない
  • 自分以外にN人が窓口に並ぶ
  • 各人の到着時刻が与えられ、時刻はすべて異なる
  • 自分と同時に到着したときは自分でない人の方が先になる
  • 必ず受け付けてもらい、かつ、待ち時間を最小にするために、何分後に並ぶ必要があるかを求める

方針

  • 仮の到着時刻をWとする
  • 次の人が受け付けてもらえる時刻をXとして、初期値をSとしてXを更新していく
  • N人を一人ずつ見ていく
  • 次の人Aが、Xよりもあとに来るならば、並ばなくて良いので、時刻Xが答え
  • そうでなければ、Aの直前に来るのが候補(ただし、Xが受け付けてもらえる時刻であること)
  • その場合、(X-(A-1))だけ待つことになる
  • Wよりも待たないのなら、Wを更新する
  • N人処理した結果、Xがまだ受け付けてもらえる時刻なら、Xが答え
  • https://github.com/firewood/topcoder/blob/master/codeforces_3xx/cf_398/b.cpp

結果

ox--- 278pt 2524th/7223 rating 1716 -> 1621 (-95)

最後の場合分けが足りていなくて死んだ。ABともそんなに簡単ではなかった。


https://togetter.com/li/1082440

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170308