ABC122解説がしたかった

AtCoder 競技プログラミング

A - Double Helix

問題の通りに実装するだけ

using System;
using System.IO;
 
namespace Contest
{
    class Program
    {
        public void Solve()
        {
            var sc = new Scanner();
 
            string b = sc.Next();
            if (b == "A") Console.WriteLine("T");
            if (b == "T") Console.WriteLine("A");
            if (b == "C") Console.WriteLine("G");
            if (b == "G") Console.WriteLine("C");
        }
 
        static void Main(string[] args) => new Program().Solve();
    }
}

https://atcoder.jp/contests/abc122/submissions/4685518

B - ATCoder

for文でleftを0から|S|まで回す
[left,right)がACGT文字列を満たす間rightを増やす = S[right]がACGTじゃないならbreak
答えを更新
leftをrightにする
つまりやるだけ

using System;
using System.IO;
 
namespace Contest
{
    class Program
    {
        public void Solve()
        {
            var sc = new Scanner();
 
            var S = sc.Next();
            int ans = 0;
            for (int left = 0; left < S.Length; left++)
            {
                if (C(S[left]))
                {
 
                    int right;
                    for (right = left + 1; right < S.Length; right++)
                    {
                        if (!C(S[right])) break;
                    }
 
                    ans = Math.Max(ans, right - left);
                    left = right;
                }
            }
            Console.WriteLine(ans);
        }
 
        bool C(char c) => c == 'A' || c == 'T' || c == 'G' || c == 'C';
 
        static void Main(string[] args) => new Program().Solve();
    }
}

https://atcoder.jp/contests/abc122/submissions/4688335

C - GeT AC

sum[i]を[0,i)の'AC'の個数とする
[l-1,r-1]の'AC'の個数は
S[l-2...i-1]が'AC'ならsum[r] - sum[l]
じゃないならsum[r]-sum[l-1]

一文字目でACが成立することはありえないので上の条件分岐なしでsum[r] - sum[l]してよさそう

using System;
using System.IO;
using System.Text;
 
namespace Contest
{
    class Program
    {
        public void Solve()
        {
            var sc = new Scanner();
            int N = sc.NextInt();
            int Q = sc.NextInt();
            string S = sc.Next();
 
            var sum = new int[N + 1];
            for (int i = 1; i < N; i++)
            {
                sum[i + 1] = sum[i];
                if (S[i] == 'C' && S[i - 1] == 'A')
                {
 
                    sum[i + 1]++;
                }
 
            }
 
            var sb = new StringBuilder();
 
            for (int i = 0; i < Q; i++)
            {
                var l = sc.NextInt() - 1;
                if (l > 0 && S[l] == 'C' && S[l - 1] == 'A') l++;
                int r = sc.NextInt();
                sb.AppendLine((sum[r] - sum[l]).ToString());
            }
            Console.Write(sb.ToString());
        }
 
 
        static void Main(string[] args) => new Program().Solve();
    }
}

https://atcoder.jp/contests/abc122/submissions/4691877

D - We Like AGC

メモ化再帰
S_{i,j,k,l}...i文字で2個前がj、1個前がk、一番後ろがlで何通りか
条件を満たさないパターンは0

using System;
using System.IO;

namespace Contest
{
    class Program
    {
        private int Mod = 1000000007;
        private int[,,,] memo = new int[101, 4, 4, 4];
        public void Solve()
        {
            var sc = new Scanner();
            int N = sc.NextInt();
            long ans = 0;
            //memoを全部-1で初期化
            for (int i = 0; i <= N; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        for (int l = 0; l < 4; l++)
                        {
                            memo[i, j, k, l] = -1;
                        }
                    }
                }
            }
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        ans += C(N, i, j, k);
                        ans %= Mod;
                    }
                }
            }
            Console.WriteLine(ans);
        }

        int C(int index, int one, int two, int last)
        {
            //既に計算済み = memoが-1じゃないならmemoをそのまま返す
            if (memo[index, one, two, last] != -1) return memo[index, one, two, last];
            if (index == 3)
            {
                if (Check(-1, one, two, last)) return 1;
                else return 0;
            }
            else
            {
                int res = 0;
                for (int i = 0; i < 4; i++)
                {
                    if (Check(i, one, two, last))
                    {
                        res += C(index - 1, i, one, two);
                        res %= Mod;
                    }
                }

                memo[index, one, two, last] = res;
                return res;
            }
        }

        //i,j,k,lがAGC文字列ならfalse
        //Aを0、Cを1、Gを2、Tを3とする
        bool Check(int i, int j, int k, int l)
        {
            if (i == 0 && j == 2 && k == 1) return false;
            if (i == 0 && j == 1 && k == 2) return false;
            if (i == 2 && j == 0 && k == 1) return false;
            if (i == 0 && j == 2 && l == 1) return false;
            if (i == 0 && k == 2 && l == 1) return false;
            if (j == 0 && k == 2 && l == 1) return false;
            if (j == 0 && k == 1 && l == 2) return false;
            if (j == 2 && k == 0 && l == 1) return false;
            return true;
        }


        static void Main(string[] args) => new Program().Solve();
    }
}

https://atcoder.jp/contests/abc122/submissions/4700074

感想

Dで時間かかった
A 1:37 (1:37)
B 6:47 (5:10)
C 19:23 (12:36)
D 83:28 (64:05)