たくあんポリポリ

勉強したことを載せていきます。最近、技術系の記事はZennに書いています。(https://zenn.dev/chittai)

【C#】 Tenka1 Programmer Beginner Contest 2019 に参加してみた

Tenka1 Programmer Beginner Contest 2019に参加してみた。

atcoder.jp

結果

C問題が解けなかった。
f:id:c_taquna:20190421000216p:plain

コンテストが終わったあとに解説みてなんとか回答できました。
f:id:c_taquna:20190421024818p:plain

振り返り

A問題とB問題は特段難しくなかった。C問題はコードが良い解法が思いつかなかった。解説動画で説明されていた、累積和を使用すると導き出せるとのこと。右側に黒、左側に白となるのはわかったけど、解法までもっていけなかった。やはり、ある程度多くの種類の問題を解いて、解法を勉強しないと厳しいなと思いました。

累積和

ここの説明がわかりやすかった。
qiita.com

C問題の実装

解法の考え方はYoutubeの解説をみてください。同じ考えで実装しています。

using System;
using System.Linq;

namespace T1PBC
{
    class Program
    {
        static void Main(string[] args)
        {
            int input = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();

            int Rwhite = s.Count(x => x == '.');
            int RBlack = s.Count(x => x == '#');

            int LBlack = 0;

            int result = Rwhite + LBlack;
            for (int i = 0; i < input; i++)
            {
                if (s[i] == '.')
                {
                    Rwhite--;
                }
                else
                {
                    LBlack++;
                }

                if ((LBlack + Rwhite) < result)
                {
                    result = LBlack + Rwhite;
                }

            }
            Console.WriteLine(result);
        }
    }
}

まず、最後に表示する変数result の初期化をしてください。これをしておかないとすべてが黒の時に0より大きい値が入ってしまう可能性があり、NGとなります。この時点でのRwhiteはすべての白の数が入ってます。 Rwhite = s.Count(x => x == '.');で求めています。

int result = Rwhite + LBlack;

ここで累積和の計算をしています。Rwhiteは すべての白の数をもっているので、見つかった白の値を引いていけば右側にある白の数を求めることができます。左側の黒は1ずつ足せばOKです。

if (s[i] == '.')
{
    Rwhite--;
}
else
{
    LBlack++;
}

あとは、左側の黒の数と右側の黒の数を足して一番小さい値を出力すればOKです。

if ((LBlack + Rwhite) < result)
{
    result = LBlack + Rwhite;
}

感想

もっと引き出しを作らないと厳しいなと思いました。