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)にした
