hotpepsiの練習帳

SRM 700

22:04

https://competitiveprogramming.info/topcoder/srm/round/16821/div/1

Div1 Easy (300) FindingFriend

問題

• 友人がプログラミングコンテストに参加している
• 部屋がroomCount個あり、各部屋にはそれぞれroomSize人が割り当てられる
• 各部屋の一位の順位leadersと、友人の順位friendPlaceが与えられる
• 友人が割り当てられた可能性のある部屋の総数を求める

方針

• leadersのどれかに含まれていれば1で終了
• ある部屋Tに配置できる可能性があるかどうかを求める。
• 順位の高い(小さい)順にroomSize人ずつ詰めていく
• friendPlace人まで詰めたが、まだTでない場合、友人を飛ばして、次の人を詰める
• 最後まで詰めることができればOK
• 全ての部屋について調べる
• Failed System Test
• Ekaingさんの解説を読む
• friendPlaceより前の部分がきっちり詰まっているときは、そこには詰められない
• 余裕がある部屋の数をansとして数えていく
• 順位の高い(小さい)順にroomSize人ずつ詰める
• きっちり詰まっている場合、余裕がないとしてansをリセットする
• friendPlaceまで来たらansが答え
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_700/FindingFriend.cpp

結果

x-- -1 -25pt 239th/255 rating 1474 -> 1317 (-157)

友人を飛ばす・飛ばさないで場合分けしたりして複雑になってしまった。

https://togetter.com/li/1032595