from 競技プログラミングで解法を思いつくための典型的な考え方 agc026_c https://atcoder.jp/contests/agc026/tasks/agc026_c
- 考えたこと
- 18C9はいくらか…
- 計算量の見積もり
- 13なら余裕で15だと無理目なので18はダメだね
- 追加: 36C18だった
- 必ず偶数、左端は赤と仮定して良い(赤青反転したものが必ず存在するので)
- 18C9はいくらか…
- 公式解説
- なるほど、10枚のコインの原理か。
- 青文字がN、右半分もNなので「左にある青文字数と右にある赤文字数は一致する」が言える
- 半分になれば2^18、これなら全探索してもまあ大丈夫
- 半分全列挙の一種か
- なるほど、10枚のコインの原理か。