ARC128-B Balls of Three Colors

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1 2 2");
            WillReturn.Add("1 2 3");
            WillReturn.Add("1 2 4");
            //2
            //-1
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int R = wkArr[0];
            int G = wkArr[1];
            int B = wkArr[2];
            int Result = Solve(R, G, B);
            Console.WriteLine(Result);
        }
    }

    static int Solve(int pR, int pG, int pB)
    {
        var Mod3List = new List<int>();
        Mod3List.Add(pR % 3);
        Mod3List.Add(pG % 3);
        Mod3List.Add(pB % 3);

        if (Mod3List.Distinct().Count() == 3) {
            return -1;
        }

        var AnswerKouho = new List<int>();
        if (pR % 3 == pG % 3) {
            AnswerKouho.Add(Math.Max(pR, pG));
        }
        if (pR % 3 == pB % 3) {
            AnswerKouho.Add(Math.Max(pR, pB));
        }
        if (pB % 3 == pG % 3) {
            AnswerKouho.Add(Math.Max(pB, pG));
        }
        return AnswerKouho.Min();
    }
}

解説

RGBの色を変化させた場合の個数を考えると
Rが-1
Gが-1
Bが+2
ですので、mod3で考えると -1 ≡ +2 (mod 3) なので
Rが+2
Gが+2
Bが+2
となります。

最終的に、RGBの2つを0にするので最終的には、
RGBの少なくとも2つを 0 (mod 3)
にする必要があるので、RGBのmod 3 が全て異なっていたら、
解なしとなります。

(R,G,B) = (3,9,5)で5に全て移動させる手順を考えると下記のようになります。
 3  9  5
 0  6 11
 2  5 10
 4  4  9
 0  0 17
Gが単調減少しているので、これが最適解だと分かります。

(R,G,B) = (5,17,0)で0に全て移動させる手順を考えると下記のようになります。
 5 17  0
 0 12 10
 2 11  9
 4 10  8
 6  9  7
 8  8  8
 0  0 16
Gが単調減少しているので、これが最適解だと分かります。

最終的に0にする色の2つで大きい数が移動回数と分かるので
この2つの組み合わせを全探索してます。