Hatena::Grouptopcoder

hotpepsiの練習帳

2017-01-02

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

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