AtCoderのAGC
次のAGCの問題へ
前のAGCの問題へ
AGC039-A Connection and Disconnection
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("issii");
WillReturn.Add("2");
//4
}
else if (InputPattern == "Input2") {
WillReturn.Add("qq");
WillReturn.Add("81");
//81
}
else if (InputPattern == "Input3") {
WillReturn.Add("cooooooooonteeeeeeeeeest");
WillReturn.Add("999993333");
//8999939997
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
string S = InputList[0];
long K = long.Parse(InputList[1]);
// 全部同じ文字なら等差数列にならない
if (S.ToCharArray().Distinct().Count() == 1) {
long StrLen = S.Length * K;
Console.WriteLine(StrLen / 2);
return;
}
var CntDict = new Dictionary<long, long>();
string ConnS = "";
for (int I = 1; I <= 10; I++) {
ConnS += S;
CntDict[I] = DeriveCnt(ConnS);
}
if (K <= 7) {
Console.WriteLine(CntDict[K]);
return;
}
long ModK = K % 3;
if (ModK == 2) {
long Kousuu = (K + 1) / 3;
long Syokou = CntDict[2];
long Kousa = CntDict[5] - CntDict[2];
long Makkou = Syokou + Kousa * (Kousuu - 1);
Console.WriteLine(Makkou);
}
if (ModK == 0) {
long Kousuu = K / 3;
long Syokou = CntDict[3];
long Kousa = CntDict[6] - CntDict[3];
long Makkou = Syokou + Kousa * (Kousuu - 1);
Console.WriteLine(Makkou);
}
if (ModK == 1) {
long Kousuu = (K - 1) / 3;
long Syokou = CntDict[4];
long Kousa = CntDict[7] - CntDict[4];
long Makkou = Syokou + Kousa * (Kousuu - 1);
Console.WriteLine(Makkou);
}
}
// 文字列を引数として、同じ2文字が連続しないのに必要なReplace回数を返す
static long DeriveCnt(string pStr)
{
long ReturnItem = 0;
for (int I = 1; I <= pStr.Length - 1; I++) {
if (pStr[I] == pStr[I - 1]) {
ReturnItem++;
I++;
}
}
return ReturnItem;
}
}
解説
まず、場合に分けます。
全ての文字が同じ場合は、
a なら 0回必要
aa なら 1回必要
aaa なら 1回必要
aaaa なら 2回必要
aaaaa なら 2回必要
aaaaaa なら 3回必要
aaaaaaa なら 3回必要
で(文字数 / 2) 回必要だと分かります。
全ての文字が同じでない場合で、両端が異なる場合、例えば
a???b と a???b
の場合は、Kを項番号とした等差数列になると分かります。
全ての文字が同じでない場合で、両端が同じ場合、例えば
a?b?a と a?b?a
の場合も、Kを項番号とした等差数列になりそうな気がします。
コーナーケースを踏みそうなので、
K=2からK=7までの解を求めて、
mod3で分類して、末項を求めてます。