1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

TLEから抜け出すのに1時間かけた話

Posted at

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
1
0
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?