perogram

B. Circus (1138B)

Quiz

https://codeforces.com/contest/1138/problem/B

Submit

https://codeforces.com/contest/1138/submission/51062002

英語

  • 最初は問題の意図がよく分からなかった
  • 前半にピエロをX人
  • 後半にアクロバットをX人
  • にする必要がある。他の人は別のサポート役をすると捉えよう
  • 問題の設定だと、X=0もアリで、それはサーカスになっているのか?と思うけれどスルーする

解法(TLE ver)

  • 最初に後半の講演に全員を所属させる
    • 00 a人
    • 01 b人
    • 10 c人
    • 11 d人
  • 前半の講演にN/2人、条件を満たすように移籍させる
    • 00 a' 人
    • 01 b' 人
    • 10 c' 人
    • 11 d' 人
  • d, d' はNとの関係から消すことができる
  • 式変形していくと最終的に a + c = 2 * a' + b' + c'
  • を満たすa', b', c' が見つかればいいので総当たりする
  • ここでO(N3)となりTLEする

解法(AC ver)

  • 方針はほぼ同じ
  • 01の b'人、11の d'人を全探索する
  • これによりアクロバットの減少数が確定し、ピエロ数もそれに合わせる必要がある
  • ピエロ数を合わせるには 10 c' で調整するしかない
    • 00 a' を連れてきても増えないため
  • c' が決まれば a' も決まる
  • よってO(N2)で解くことができました

感想

  • Div2 Bとはいえ、4200人中815人しか解けていない

学び

  • O(N3)をループの順番を適切にすることでO(N2)にした