ABC 069 C問題 4-adjacent
なるべく一日一題を目標に…（三日坊主になってしまいそうですが）
問題
すぬけくん登場！
考察の流れ
となりあった要素をかけたら全部4の倍数になるようにうまく並べ替える方法があるか？
数列の各数を「奇数」「2の倍数だが4の倍数でない」「4の倍数」の3つに分類したとき，奇数と隣り合う数は絶対4の倍数でないとだめであるため，それらを前から詰めていくことを考える．
奇数がある場合
- (奇数の個数)+1 <(4の倍数の個数)なら，前から奇数と4の倍数を交互につめればいい．
- (奇数の個数)+1 = (4の倍数の個数)ときうまく並び替えられるのは (奇数の個数)+(4の倍数の個数)=(数列のサイズ)になる場合．もし，(奇数の個数)+(4の倍数の個数)<(数列のサイズ)になる場合は，奇数と4の倍数を交互に詰めていったとき，「奇数」「2の倍数だが4の倍数でない」という並びができてしまい，実現不可能．
奇数がない場合
全て偶数なため，どんな並べ方をしても，隣り合う要素をかければ4の倍数となる
というわけで，「奇数」と「4の倍数」の個数を入力受取時にカウントすれば，ループを回さなくてもO(1)で解くことができる！
コード
Submission #2794671 - AtCoder Beginner Contest 069
1発AC 所要時間20minくらい
反省
- Cなのに400点問題なので解けるか不安でしたがなんとか1発ACをいただきました．O(1)解にたどり着くことができてよかった．
- 場合分けのところで本当にこれで網羅できてるのかな？と混乱してしまいました．サンプルのテストケースを見てパターンを導き出した感じですが，場合分けの力は磨いていきたいところです．特に解説を読むとよりシンプルな場合分けをしています．
