構築方法が分からないならまず判定問題を考える

構築問題とは

• 条件を満たすもの（配列やグラフ）の一例を答えとして出力するもの
• constructiveと言われることも

具体例

• Quiz
  • C.Balance the Bits
  • https://codeforces.com/contest/1504/problem/C
• AC
  • https://codeforces.com/contest/1504/submission/111935280
  • 嘘解法っぽさがあるのでここでは解説しない
• 強い人の解法

Codeforces Round 712 (Div. 1)．
凡人には辛いセットだった気がする．

A，
0と1は両方偶数個でないと不可能．
1は前半は(，後半は)を配置．
0は(と)，)と(を交互に使用．
とするのが最適なはずで，それで条件をちゃんと満たしているか最後にチェックした． pic.twitter.com/UQokYNe3CH

— laycrs (@laycrs) April 3, 2021

• 強い人の考え方

実装力は無になってるけど、考察力もかなり下がっていました。「とりあえず自明な場合 n = 1, 2, 3 を考えてみましょう」「構成問題が分からないならまず判定問題を考えてみましょう」みたいな基本動作がなかなか出てこない

— kimiyuki@うさぎ🐇 (@kimiyuki_u) April 3, 2021

補足

• 今回の問題では、0,1が両方偶数個でないと不可能（判定問題）
• 両方偶数個であるなら左右の半分に割るという発想が自然と出てきて、解法に導かれる