Codingame『Scrabble』クリア

ScrabbleScrabble / DavidMartynHunt


 Scrabbleのルール?フフン!英語が読めないからサッパリわかりませんね!

っていう思考放棄をしても解決出来たら文句ないんですがねぇ……。


 簡単にルールを言うと、
・文字にはポイントが決められている
・レターズにある文字だけが使える
・単語の文字を調べて得点を計算
・最高得点の単語はどれだ?
こんな感じ。


 細かいところだと、こういうものもある。
・レターズに無い文字は使えない(使った単語ははじく)
・同ポイントの単語があれば、最初に出現した方を選ぶ
・レターズがgggeepだったら、gを3回、eを2回、pを1回使うことができる(gepとか、ggpとか。ppeは使用回数越え)


using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    static void Main(string[] args)
    {
        //文字とポイントまとめ
        Dictionary<char, int> LettersPoints = new Dictionary<char, int>() {
            {'e',1},
            {'a',1},
            {'i',1},
            {'o',1},
            {'n',1},
            {'r',1},
            {'t',1},
            {'l',1},
            {'s',1},
            {'u',1},
            {'d',2},
            {'g',2},
            {'b',3},
            {'c',3},
            {'m',3},
            {'p',3},
            {'f',4},
            {'h',4},
            {'v',4},
            {'w',4},
            {'y',4},
            {'k',5},
            {'j',8},
            {'x',8},
            {'q',10},
            {'z',10},
        };

        //Lettersが含む文字の出現数を集計したもの(マスター用)
        Dictionary<char, int> MHistogram = new Dictionary<char, int>();
        //Lettersが含む文字の出現数を集計したもの(コピー用)
        Dictionary<char, int> CHistogram = new Dictionary<char, int>();

        //単語
        string[] Words;

        //最大ポイント
        int maxPoint;
        //最大ポイントを得た単語の番号
        int maxPointNumber;

        //単語の総数を取得
        int N = int.Parse(Console.ReadLine());
        //配列確保
        Words = new string[N];

        //単語取得
        for (int i = 0; i < N; i++)
        {
            Words[i] = Console.ReadLine();
        }

        //Letters取得
        string LETTERS = Console.ReadLine();

        //Lettersが含む、文字と、文字の出現回数を調べる
        for (int i = 0; i < LETTERS.Length; i++)
        {
            //文字が既にあるのかどうか判定する
            if (MHistogram.ContainsKey(LETTERS[i]) == true)
            {
                //文字が既にあるのなら+1
                MHistogram[LETTERS[i]]++;
            }
            else {
                //無いのなら新しく作る
                MHistogram[LETTERS[i]] = 1;
            }
        }

        //ポイントと番号の初期化
        maxPoint = 0;
        maxPointNumber = 0;

        //単語集は尻から調べる(同ポイントなら番号の若い方を選ぶため)
        for (int i = N - 1; i >= 0; i--)
        {
            //単語ごとのポイント
            int sum = 0;

            //マスターからコピーへ、ディープコピーする
            foreach (var t in MHistogram)
            {
                CHistogram[t.Key] = t.Value;
            }

            //単語のポイントを調べる
            for (int j = 0; j < Words[i].Length; j++)
            {
                //ヒストグラムに文字が存在するなら
                if (CHistogram.ContainsKey(Words[i][j]) == true)
                {
                    //文字使用量として度数を1引く
                    CHistogram[Words[i][j]]--;
                    //ポイントを加算
                    sum += LettersPoints[Words[i][j]];

                    //文字使用回数がマイナスを振り切ったら失敗単語
                    if (CHistogram[Words[i][j]] < 0)
                    {
                        //強制的にループを終了させて次の単語へ
                        j = Words[i].Length;
                        //ポイント使用不可の処理
                        sum = -1;
                    }
                }
                else {
                    //ヒストグラムに文字が無い場合も失敗単語として処理
                    j = Words[i].Length;
                    sum = -1;
                }
            }

            //最高得点の比較
            if (maxPoint <= sum)
            {
                //最高点の更新
                maxPoint = sum;
                //最高点をマークした単語の番号を記録
                maxPointNumber = i;
            }
        }

        // Write an action using Console.WriteLine()
        // To debug: Console.Error.WriteLine("Debug messages...");

        //結果
        Console.WriteLine(Words[maxPointNumber]);
    }

}