hotpepsiの練習帳

Codeforces #398 (Div. 2)

00:13

A. Snacktower

問題

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

方針

• いちばん大きくてまだ置いていないものを覚えておき、そこに降ってきたら連続しているものを埋める
• https://github.com/firewood/topcoder/blob/master/codeforces_3xx/cf_398/a.cpp

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