htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Grand Contest 016 参戦記

o---- 1293 -> 1300 (+7)

A - Shrinking

結果:AC
Submission #1360112 - AtCoder Grand Contest 016 | AtCoder

うだうだ考えないでシミュレーションしましょう。高々100文字しかないのだしどう見ても計算量的に間に合うのに無い頭で考えようとするから早解きできないんだよ!!うえーん

B - Colorful Hats

結果:わかんなかった

諦めた時点のコード
f:id:htkb:20170621225028j:plain
割とあと一歩じゃん!!と思ったけどコンテスト中はこんな場合分けするのはきっと想定解と違う……などとスットコドッコイなこと考えてたし最後のelse節の部分を思いつくのは無理だっただろう。というか解説見てもよくわからんのです。

  • max(a)min(a)の差が1より大きい場合はNo。これは自明。
  • max(a) == min(a)の場合は以下のどちらかに当てはまるならYes
    • 全ての猫が違う色ケース。必ずみんなN-1と言う。
    • aloneな猫が1匹もいないケース。1色につき少なくとも2匹の猫が存在するため N//2 >= 色数

で問題は max(a) == min(a)+1のケース。解説に載ってる式とちょっと違うけど、↓の理解で通った。

f:id:htkb:20170621225303j:plain

ACコード:Submission #1369417 - AtCoder Grand Contest 016 | AtCoder

C - +/- Rectangle

あとでやる