ARC-040-B 直線塗り

■■■問題■■■

イカの高橋君は床を塗るのが大好きです。
床はN個のマスが左右に1列に並んでいるような形をしています。
左からi個目のマスをマスiと呼ぶことにします。

すでにいくつかのマスは塗られていますが、
いくつかのマスは塗られていません。
高橋君はインクを発射できる射程がRの銃を使って全てのマスを塗ろうとしています。

高橋君は最初マス1にいます。
そして、1秒の間に以下のいずれか1つの行動が行えます。

●1つ右のマスに移動する。すなわち、マスiからマスi+1に移動する。
  ただし、マスNにいるときは行えない。
●銃を撃って床を塗る。
  マスiにいるときに銃を撃つと、マスiからマスi+R-1までのマスを全て塗ることができる。
  ただし、i+R-1がNより大きい場合は、マスiからマスNまでのマスが塗られる。

高橋君が全てのマスを塗るためにかかる時間の最小値を求めてください。

■■■入力■■■

N R
S

●1行目には、マス目の個数を表す整数 N(1 <= N <= 100)と
  銃の射程を表す整数 R(1 <= R <= N) が空白区切りで与えられる。
●2行目には、長さNの文字列Sが与えられる。
  このうち i(1 <= i <= N) 文字目は、マスiの情報を以下のように表す。
●.の場合：このマスがまだ塗られていないことを表す。
●oの場合：このマスがすでに塗られていることを表す。

■■■出力■■■

高橋君が全てのマスを塗るためにかかる時間の最小値を1行に出力せよ。
出力の末尾に改行を入れること。

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("7 3");
            WillReturn.Add("...o.o.");
            //6
            //銃を撃つ → 4歩前進 → 銃を撃つ、
            //という行動をとると時間が最小となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 4");
            WillReturn.Add("...o.ooo");
            //3
            //銃を撃つ → 1歩前進 → 銃を撃つ、
            //という行動をとると時間が最小となります。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 4");
            WillReturn.Add("oooo");
            //0
            //最初から全てのマスが塗られています
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mR;

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

        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        mR = wkArr[1];
        char[] SArr = InputList[1].ToCharArray();

        int CurrInd = 0;
        int Tesuu = 0;
        while (Array.IndexOf(SArr, '.') >= 0) {
            Tesuu++;

            //優先順位1 塗って終わるなら塗る
            char[] PaintedBan = DerivePaintedBan(CurrInd, SArr);
            if (Array.IndexOf(PaintedBan, '.') < 0) break;

            //優先順位2 現在のマスが、塗られてないなら塗る
            if (SArr[CurrInd] == '.') {
                SArr = PaintedBan;
                continue;
            }

            //優先順位3 右に移動
            CurrInd++;
        }
        Console.WriteLine(Tesuu);
    }

    //現在位置で塗った場合の盤面を返す
    static char[] DerivePaintedBan(int pCurrInd, char[] pSArr)
    {
        char[] WillReturn = (char[])pSArr.Clone();

        int UB = pSArr.GetUpperBound(0);
        for (int I = pCurrInd; I <= pCurrInd + mR - 1; I++) {
            if (UB < I) break;
            WillReturn[I] = 'o';
        }
        return WillReturn;
    }
}

解説

行動に優先順位を付けて、シュミレーションしてます。