トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

東工大プロコン2015 C おおおかやま

■■■問題■■■

okayama国の首都ookayamaでは、
ookayamaの先頭に1個以上の任意の個数のoが付加された文字列のことを良い文字列と呼ぶ。

あなたの仕事は文字列Sを次のルールで処理するプログラムを書くことである。

●手順1. Sの部分文字列に良い文字列が存在するならば手順2へ、存在しないならば処理を終了する。
●手順2. 良い文字列であるようなSの部分文字列のうち、長さが最長のものを選びこれをTとして手順3へ、
         最長のものが複数ある場合は最も左側にあるものを選ぶ。
●手順3. Tにooという部分文字列が存在するならば、そのうち最も左側にあるものをOへ置換して手順4へ、
         存在しないならば手順1へ。
●手順4. TにOOという部分文字列が存在するならば、そのうち最も左側にあるものをoへ置換する。
         存在するかどうかにかかわらず手順3へ。

処理終了後のSを求めよ。

ある文字列TがSのi(1 <= i <= |S|)文字目からj(i <= j <= |S|)文字目までを取り出したものであるとき、
TはSの部分文字列であると呼ぶ。ここで|S|は文字列Sの長さを表す。 

■■■入力■■■

S

1行目に処理すべき文字列S(1 <= |S| <= 100)が与えられる。Sは英小文字のみからなることが保証される。

■■■出力■■■

処理終了後のSを1行に出力せよ。改行を忘れないこと。


C#のソース

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("ooookayama");
            //okayama
            //文字列ooookayamaに対し、処理を行うと、以下のような順序で扱われる。
            //●手順1においてSの部分文字列に良い文字列は存在する。
            //●手順2において良い文字列であってSの部分文字列であるようなもののうち
            //  長さが最長のものは1番目のoから始まる部分文字列である、ooookayamaである。
            //  これをTとする。
            //●手順3においてTに存在するooという部分文字列のうち、最も左側にあるものをOに置換する。
            //  TはOookayamaとなる。
            //●手順4においてTにOOという部分文字列は存在しない。
            //●手順3においてTに存在するooという部分文字列のうち、
            //  最も左側にあるものをOに置換する。TはOOkayamaとなる。
            //●手順4においてTに存在するOOという部分文字列のうち、最も左側にあるものをoに置換する。
            //  Tはokayamaとなる。
            //●手順3においてTにooという部分文字列は存在しない。
            //●手順1においてSはokayamaである。Sの部分文字列に良い文字列は存在しない。処理を終了する。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("ooookayamaoooookayama");
            //okayamaOkayama
            //Sの部分文字列には、良い文字列が複数存在することもある。
            //最長のものかつ最も左側にあるものから処理する必要があることに注意せよ。
            //また、与えられる入力には英大文字は含まれないものの、
            //答えや処理の過程には現れる可能性があることに注意せよ。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("okayama");
            //okayama
            //文字列okayamaの部分文字列には良い文字列は存在しない
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("ookayama");
            //ookayama
            //文字列ookayamaの部分文字列には良い文字列は存在しない。
            //良い文字列とはookayamaの先頭に1個以上の任意の個数のoが付加された文字列のことであるため
            //ookayamaは条件を満たさない。
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("ooookayamakenooooookayamashiookayama");
            //okayamakenOokayamashiookayama
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        while (true) {
            Regex Pattern = new Regex("o{3,}kayama");
            if (Pattern.IsMatch(S) == false) break;

            S = Pattern.Replace(S,
            pMatch =>
            {
                string MatchStr = pMatch.Value;

                while (true) {
                    int wkInd1 = MatchStr.IndexOf("oo");
                    if (wkInd1 == -1) break;

                    MatchStr = MatchStr.Remove(wkInd1, 2);
                    MatchStr = MatchStr.Insert(wkInd1, "O");

                    int wkInd2 = MatchStr.IndexOf("OO");
                    if (wkInd2 >= 0) {
                        MatchStr = MatchStr.Remove(wkInd2, 2);
                        MatchStr = MatchStr.Insert(wkInd2, "o");
                    }
                }
                return MatchStr;
            }
            );
        }
        Console.WriteLine(S);
    }
}


解説

正規表現o{3,}kayamaで検索し、
置換ロジックを問題文にそって実装してます。

o{3,}kayamaが複数マッチしたとしても、
最も左のマッチから処理して問題ないです。
(複数の良い文字列があったとしても、置換前後で必ずkayamaで分断されているため)