ABC032-C 列

■■■問題■■■

長さNの非負整数列 S=s1,s2, ・・・ ,sN と整数Kがあります。
あなたの仕事は、以下の条件を満たすSの連続する部分列のうち、
最も長いものの長さを求めることです。
部分列の長さは1以上の列でないといけません。

●その部分列に含まれる全ての要素の値の積は、K以下である。

もし条件を満たす部分列が一つも存在しないときは、0を出力してください。

■■■入力■■■

N K
s1
s2
・
・
sN

●1行目には、数列の長さを表す整数 N(1 <= N <= 10万) と
  問題文中の整数 K(0 <= K <= 10億) が空白区切りで与えられる。
●2行目からの N行には、数列の各要素の値が与えられる。
  そのうち i(1 <= i <= N) 行目には、si(0 <= si <= 10億) が書かれている。

■■■出力■■■

1行目に、含まれる全ての要素の値の積がK以下となる連続する部分列のうち最長のものの長さを出力せよ。
もし条件を満たす部分列が一つも存在しないときは、0を出力せよ。末尾の改行を忘れないこと。

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 6");
            WillReturn.Add("4");
            WillReturn.Add("3");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("10");
            WillReturn.Add("2");
            //4
            //部分列 S[2..5]=s2,s3,s4,s5 を選ぶと、
            //積は 3×1×1×2 = 6 となり、K以下になります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 10");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("0");
            WillReturn.Add("10");
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 9");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("10");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4 0");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("4");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();
        long K = wkArr[1];
        long[] SArr = InputList.Skip(1).Select(X => long.Parse(X)).ToArray();
        int UB = SArr.GetUpperBound(0);

        if (SArr.Contains(0)) {
            Console.WriteLine(SArr.Length);
            return;
        }

        long Answer = 0;
        int L = 0;
        long ProdVal = 1;
        for (int R = 0; R <= UB; R++) {
            ProdVal *= SArr[R];

            while (ProdVal > K) {
                if (L < R) {
                    ProdVal /= SArr[L];
                    L++;
                }
                else break;
            }
            if (ProdVal <= K) {
                if (Answer < R - L + 1)
                    Answer = R - L + 1;

                // 下限値枝切り
                int RestMaxCnt = UB - L + 1;
                if (RestMaxCnt <= Answer) break;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

尺取法で、IF文を使って、LがRを超えないようにしてます。