TLEの時の落とし穴。
ABC372_c でどうしてもTLEから抜け出せない。
解法も解説と同じ考え方で書いている。
他の方の回答見に行ってもロジック部分は特に大きな違いがない。
皆さんはどこが悪いかわかりますか?
私の最初の回答
namespace AtCoder
{
using AtCoder;
using System;
using System.Linq;
using System.Security.Cryptography;
public class Program
{
public static void Main()
{
SourceExpander.Expander.Expand();
int[] NQ = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();
int N = NQ[0];
int Q = NQ[1];
char[] S = Console.ReadLine()!.ToCharArray();
int[] ans = new int[N - 2];
Func<int, bool> checkString = (start) => (S[start] == 'A' && S[start + 1] == 'B' && S[start + 2] == 'C');
int answer = 0;
for (int i = 0; i < N - 2; i++)
{
if (checkString(i))
{
ans[i] = 1;
answer++;
}
else
{
ans[i] = 0;
}
}
string ansString = string.Empty;
for (int i = 0; i < Q; i++)
{
var XC = Console.ReadLine()!.Split(' ').ToArray();
int X = int.Parse(XC[0]);
int x = X - 1;
S[x] = XC[1][0];
for (int j = 0; j < 3; j++)
{
int start = x - j;
if (0 <= start && start < N - 2)
{
bool res = checkString(start);
if (ans[start] == 1 && res == false)
{
answer--;
ans[start] = 0;
}
else if (ans[start] == 0 && res == true)
{
answer++;
ans[start] = 1;
}
}
}
if (ansString.Length == 0)
{
ansString = answer.ToString();
}
else
{
ansString += "\r\n" + answer;
}
}
Console.WriteLine(ansString);
}
}
}
文字列結合に気を付けよう
はい。
そうですね。
ansString
をループの中でstring +=
としていますね!
知らなかったんですが、多くの文字列を結合する場合は演算子+
を使うと処理時間が大幅に遅くなります。
参考元
というわけで、以下のようにしたらACでした。
using System.Diagnostics;
namespace AtCoder
{
using System;
using System.Linq;
using System.Text;
public class Program
{
public static void Main()
{
SourceExpander.Expander.Expand();
int[] NQ = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();
int N = NQ[0];
int Q = NQ[1];
char[] S = Console.ReadLine()!.ToCharArray();
int[] ans = new int[N - 2];
Func<int, bool> checkString = (start) => (S[start] == 'A' && S[start + 1] == 'B' && S[start + 2] == 'C');
int answer = 0;
for (int i = 0; i < N - 2; i++)
{
if (checkString(i))
{
ans[i] = 1;
answer++;
}
else
{
ans[i] = 0;
}
}
StringBuilder ansString = new();
for (int i = 0; i < Q; i++)
{
var XC = Console.ReadLine()!.Split(' ').ToArray();
int X = int.Parse(XC[0]);
int x = X - 1;
S[x] = XC[1][0];
for (int j = 0; j < 3; j++)
{
int start = x - j;
if (0 <= start && start < N - 2)
{
bool res = checkString(start);
if (ans[start] == 1 && res == false)
{
answer--;
ans[start] = 0;
}
else if (ans[start] == 0 && res == true)
{
answer++;
ans[start] = 1;
}
}
}
if (i == Q - 1)
{
ansString.Append(answer);
}
else
{
ansString.AppendLine(answer.ToString());
}
}
Console.WriteLine(ansString);
}
}
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander