hotpepsiの練習帳

SRM 680

22:43

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

Div1 Easy (250) BearFair

問題

• 森で熊に出会った
• 熊が配列Xに関するクイズを出す
• Xの要素は全て異なる
• XはN個の数値からなり、Nは偶数である
• Xの全ての要素は1以上b以下である
• Xの半分は偶数で半分は奇数である
• q個のヒントが与えられる
• Xの要素のうちupTo[i]以下の個数はquantity[i]個である
• 熊が嘘をついているかどうかを求める

方針

• 番兵としてb以下がN個という情報を足す
• bでソートして昇順に処理する。ありうる偶数奇数の総数をカウントする。
• quantityがNを超えていたら不正
• upTo[i]がupTo[i-1]と同じでquantityが異なるとき、不正
• そうでないときは、upTo[i-1]+1からupTo[i]までの数について、(quantity[i]-quantity[i-1])個を超えない範囲で、偶数奇数のカウントを増やす
• 最終的に偶数奇数どちらもN÷2個以上の可能性があればOK
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_680/BearFair.cpp

結果

o-- 134.51pt 175th/439 rating 1365 -> 1427 (+62)

番兵を使えば場合分け不要だった。

http://togetter.com/li/931414