ABC-069-C 4-adjacent

■■■問題■■■

長さNの数列 a= (a1 , a2 , ・・・ , aN) があります。各aiは正の整数です。

すぬけ君の目標は、aの要素を自由に並べ替え、次の条件が成り立つようにすることです。
●各 1 <= i <= N-1 について、aiと ai+1 の積は4の倍数である

すぬけ君が目標を達成できるか判定してください。

■■■入力■■■

N
a1 a2 ・・・ aN

●2 <= N <= 10万
●aiは整数である
●1 <= ai <= 10億

■■■出力■■■

すぬけ君が目標を達成できるならばYesを、できないならばNoを出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1 10 100");
            //Yes
            //例えば、(1,100,10) と並べ替えればよいです
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 2 3 4");
            //No
            //どのように並べ替えても、条件が成り立つようにできません
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("1 4 1");
            //Yes
            //最初から条件が成り立っています
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("2");
            WillReturn.Add("1 1");
            //No
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("6");
            WillReturn.Add("2 7 1 8 2 8");
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        int Cnt0 = 0; //2を因数に持たない数のカウント
        int Cnt2 = 0; //4を因数に持たないが、2を因数に持つ数のカウント
        int Cnt4 = 0; //4を因数に持つ数のカウント

        foreach (int EachInt in AArr) {
            if (EachInt % 4 == 0) Cnt4++;
            else if (EachInt % 2 == 0) Cnt2++;
            else Cnt0++;
        }

        int PrevInsuu = 0;
        bool IsOK = true;
        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            if (I == 0) { //1個目の値
                if (Cnt0 > 0) { Cnt0--; PrevInsuu = 0; }
                else if (Cnt2 > 0) { Cnt2--; PrevInsuu = 2; }
                else { Cnt4--; PrevInsuu = 4; }
            }
            else { //2個目以降の値
                if (PrevInsuu == 0) {
                    if (Cnt4 > 0) { Cnt4--; PrevInsuu = 4; }
                    else { IsOK = false; break; }
                }
                else if (PrevInsuu == 2) {
                    if (Cnt2 > 0) { Cnt2--; PrevInsuu = 2; }
                    else if (Cnt4 > 0) { Cnt4--; PrevInsuu = 4; }
                    else { IsOK = false; break; }
                }
                else if (PrevInsuu == 4) {
                    if (Cnt0 > 0) { Cnt0--; PrevInsuu = 0; }
                    else if (Cnt2 > 0) { Cnt2--; PrevInsuu = 2; }
                    else if (Cnt4 > 0) { Cnt4--; PrevInsuu = 4; }
                    else { IsOK = false; break; }
                }
            }
        }
        Console.WriteLine(IsOK ? "Yes" : "No");
    }
}

解説

まず、下記の3通りの数の個数を求めます。
●2を因数に持たない数
●4を因数に持たないが、2を因数に持つ数
●4を因数に持つ数

あとは、最適戦略をシュミレーションしてます。