ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです!

【プログラミングコンテスト】早稲田大学プログラミングコンテスト2019①

マルイで行われていたねこぺん日和展で癒されてきました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/wupc2019)にて開催されました、早稲田大学プログラミングコンテスト2019の第1回目です。

今回は、A問題「A - WAsedAC」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語C#を使用しています。

1.問題文

WUPC 2019の開催を記念して、カトーくんは文字列 s をプレゼントとしてもらいました。

しかしながら、カトーくんは WA という文字列が嫌いなので、 WA という文字列がなくなるまで以下の行動をすることにしました。

  • 文字列 s を先頭から見ていき、連続する2文字が WA である場合、これを AC という文字列に置換する。
  • 1回の置換を行った場合、文字列の先頭から再び上記の行動を行い、置換が行われなかった場合、終了する。

カトーくんが行動を終了したときの文字列を答えよ。

2.入力例

  • 入力
WWA
  • 出力
ACC

3.初見の感想

  • Substringで部分文字列を作って'WA'のところだけ'AC'に変更して連結させてみる→無事TLEで死亡

4.学びポイント

  • 文字列連結や切り出しが重そう
  • char配列に直すというのが速さを出すコツだとわかった
  • 前から順番に走査すると先頭に戻るコストが大きい→後ろから走査することで計算時間を短縮!

5.全コード

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        char[] input = Console.ReadLine().ToArray();
        for(int i = input.Length - 1; i >=1; i--)
        {
            if (input[i-1] == 'W' && input[i] == 'A')
            {
                input[i-1] = 'A';
                input[i] = 'C';
            }
        }
        Console.WriteLine(input);     
    }
}

6.最後に

シンプルですがいい問題ですね(^^)