典型90問
次の典型90問へ
前の典型90問へ
典型90問 084 There are two types of characters(★3)
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("4");
WillReturn.Add("ooxo");
//5
}
else if (InputPattern == "Input2") {
WillReturn.Add("5");
WillReturn.Add("oxoxo");
//10
}
else if (InputPattern == "Input3") {
WillReturn.Add("5");
WillReturn.Add("ooooo");
//0
}
else if (InputPattern == "Input4") {
WillReturn.Add("7");
WillReturn.Add("xxoooxx");
//16
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
string S = InputList[1];
int UB = S.Length - 1;
var IndList1 = new List<int>();
var IndList2 = new List<int>();
for (int I = 0; I <= UB; I++) {
if (S[I] == 'o') IndList1.Add(I);
if (S[I] == 'x') IndList2.Add(I);
}
if (IndList1.Count == 0 || IndList2.Count == 0) {
Console.WriteLine(0);
return;
}
long Answer = 0;
// 始点を全探索
for (int I = 0; I <= UB; I++) {
if (S[I] == 'o') {
int ResultInd = ExecNibunhou_UpperBound(I, IndList2);
if (ResultInd > -1) {
Answer += UB - IndList2[ResultInd] + 1;
}
}
if (S[I] == 'x') {
int ResultInd = ExecNibunhou_UpperBound(I, IndList1);
if (ResultInd > -1) {
Answer += UB - IndList1[ResultInd] + 1;
}
}
}
Console.WriteLine(Answer);
}
// 二分法で、Val超えで最小の値を持つ、添字を返す
static int ExecNibunhou_UpperBound(int pVal, List<int> pList)
{
// 最後の要素がVal以下の特殊ケース
if (pVal >= pList.Last()) {
//return pArr.GetUpperBound(0) + 1;
return -1;
}
// 最初の要素がVal超えの特殊ケース
if (pVal < pList[0]) {
return 0;
}
int L = 0;
int R = pList.Count - 1;
while (L + 1 < R) {
int Mid = (L + R) / 2;
if (pList[Mid] > pVal) {
R = Mid;
}
else {
L = Mid;
}
}
return R;
}
}
解説
区間の始点を全探索して、
始点ごとの終点の最小値を二分探索してます。