yukicoder 3323 岩井星式ジャンケン

問題へのリンク

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("2 3");
            WillReturn.Add("GGG");
            WillReturn.Add("CPC");
            //GPG
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 3");
            WillReturn.Add("PGC");
            WillReturn.Add("PCP");
            WillReturn.Add("PPG");
            WillReturn.Add("GGP");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 5");
            WillReturn.Add("PGCPC");
            WillReturn.Add("PPGGP");
            WillReturn.Add("CPGPC");
            WillReturn.Add("CGCCP");
            //CPPCP
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        List<string> TeList = new List<string>();
        TeList.AddRange(InputList.Skip(1));

        var ValidYSet = new HashSet<int>();
        for (int Y = 0; Y <= TeList.Count - 1; Y++) {
            ValidYSet.Add(Y);
        }

        var AnswerList = new List<char>();
        for (int X = 0; X <= TeList[0].Length - 1; X++) {
            var TeSet = new HashSet<char>();
            foreach (int EachY in ValidYSet) {
                TeSet.Add(TeList[EachY][X]);
            }

            if (TeSet.Count == 3) {
                Console.WriteLine(-1);
                return;
            }
            char WinTe = '\0';
            if (TeSet.Count == 2) {
                if (TeSet.Contains('C') && TeSet.Contains('G')) {
                    WinTe = 'G';
                }
                if (TeSet.Contains('C') && TeSet.Contains('P')) {
                    WinTe = 'C';
                }
                if (TeSet.Contains('G') && TeSet.Contains('P')) {
                    WinTe = 'P';
                }
            }
            if (TeSet.Count == 1) {
                if (TeSet.Contains('C')) WinTe = 'G';
                if (TeSet.Contains('G')) WinTe = 'P';
                if (TeSet.Contains('P')) WinTe = 'C';
            }
            if (TeSet.Count == 0) {
                WinTe = 'C';
            }
            AnswerList.Add(WinTe);

            var ExceptSet = new HashSet<int>();
            foreach (int EachY in ValidYSet) {
                if (WinTe == 'C' && TeList[EachY][X] == 'P') {
                    ExceptSet.Add(EachY);
                }
                if (WinTe == 'G' && TeList[EachY][X] == 'C') {
                    ExceptSet.Add(EachY);
                }
                if (WinTe == 'P' && TeList[EachY][X] == 'G') {
                    ExceptSet.Add(EachY);
                }
            }
            ValidYSet.ExceptWith(ExceptSet);
        }

        if (ValidYSet.Count == 0) {
            AnswerList.ForEach(pX => Console.Write(pX));
            Console.WriteLine();
        }
        else {
            Console.WriteLine(-1);
        }
    }
}

解説

場合に分けて考えます。

●場合1
残ってる人の手が、グー、チョキ、パーの3通りある場合
-1を出力して終了

●場合2
残ってる人の手が、2通りある場合
グー、チョキの場合は、グーを出すしかないです。
グー、パーの場合は、パーを出すしかないです。
チョキ、パーの場合は、チョキを出すしかないです。

●場合3
残ってる人の手が、1通りの場合
勝つ手を出すのが最適です。

以上の要領で、場合分けしつつ、貪欲法で進めていき、
残った人が、0人かを判定すれば解けます。