トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
No.3009 異なる数字の最大の範囲
■■■問題■■■
N個の自然数が与えられます。
そこから、L番目からR番目の範囲の自然数を(R-L+1)個抜き出します。(1 <= L <= R <= N)
この時、その範囲に同じ自然数が出てこないようにうまくLとRを選ぶとすると、
最大で何個抜き出せるでしょうか?
■■■入力■■■
N
A1 A2 ・・・ AN
入力は全て整数で与えられます。
0 <= N <= 10万
1 <= Ak <= 100万
■■■出力■■■
抜き出せる最大の個数を求めてください。
最後に改行してください。
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "Input1";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5");
WillReturn.Add("1 2 3 1 2");
//3
//例えば 1,2,3と抜き出したら3個です
}
else if (InputPattern == "Input2") {
WillReturn.Add("5");
WillReturn.Add("1 2 3 4 5");
//5
//全ての数字を取ることが出来ます
}
else if (InputPattern == "Input3") {
WillReturn.Add("5");
WillReturn.Add("1 1 1 1 1");
//1
//全て同じ数字です
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
int UB = AArr.GetUpperBound(0);
//重複のあるデータを保持
IEnumerable<int> wkDupValEnum =
AArr.GroupBy(X => X).Where(X => X.Count() > 1).Select(X => X.Key);
var DupValSet = new HashSet<int>(wkDupValEnum);
int Answer = 0;
int L = 0;
for (int R = 0; R <= UB; R++) {
int CurrVal = AArr[R];
if (DupValSet.Contains(CurrVal)) {
//再登場の数値の場合
int wkInd = Array.FindIndex(AArr, L, R - L, X => X == CurrVal);
if (wkInd >= 0) {
L = wkInd + 1;
//下限値枝切り
int RestMaxCnt = UB - L + 1;
if (RestMaxCnt <= Answer) break;
}
}
if (Answer < R - L + 1)
Answer = R - L + 1;
}
Console.WriteLine(Answer);
}
}
解説
TLE対策で、
事前に、重複がありうる数値かを記憶するHashSetを用意しておき、
HashSetに存在した場合のみ、重複した数値かを調べてます。
また、現在の数値をコレクションに保持せず、都度Array.FindIndexで見てます。