【プログラミングコンテスト】早稲田大学プログラミングコンテスト2019①
マルイで行われていたねこぺん日和展で癒されてきました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/wupc2019)にて開催されました、早稲田大学プログラミングコンテスト2019の第1回目です。
今回は、A問題「A - WAsedAC」の問題と僕との戦闘記です。
0.はじめに
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.最後に
シンプルですがいい問題ですね(^^)