Tenka1 Programmer Beginner Contest 2019 C - Stones
平成最後の一週間と聞いてビックリしました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/tenka1-2019-beginner)にて開催されました、Tenka1 Programmer Beginner Contest 2019 C問題「C - Stones」の問題と僕との戦闘記です。
0.はじめに
1.問題文
N 個の石が一列に並んでおり、すべての石は白か黒で塗られています。 石の状態は長さ N の文字列 S で表され、 S の i 文字目が" . "のとき左から i 個目の石が白であり、"#" のとき左から i 個目の石が黒であることを表します。
高橋君は、 0 個以上の石の色を黒または白に変更し、黒い石のすぐ右に白い石があるような箇所がないようにしたいです。 色を変更する必要のある石の個数の最小値を求めてください
2.制約
- 1 ≤ N ≤ 2 × 105
- S は "." , "#" のみからなる長さ N の文字列である
3.入力例
- 入力
5 #.##.
- 出力
2
4.初見の感想
- 白と黒の二種類しかないので、最終形が予想できそう? →「All白」or「All黒」or「白連続→黒連続の順」という3パターン
5.学びポイント
- 厄介なのはどこで白連続と黒連続の境界を設けるか、という問題
→最初に白黒の総数を計算しておくことで、ループの途中でも後ろに続く列の中に何個白や黒があるかがわかる!
- 「境界の左側にある黒色の数+境界の右側にある白色の数」が変更する回数となる
6.コードの簡単な解説
- まず、入力の値のパースを行う
string input = Console.ReadLine(); int N = int.Parse(input); input = Console.ReadLine(); char[] S= input.ToCharArray();
- 白色の総数を計算
int white_all = 0; int black = 0; for(int i = 0; i < N; i++) { if (S[i] == '.') { white_all++; } }
- 白や黒のみの場合の例外処理、白や黒のカウンタの用意
int ans = white_all; int counter = 0; int white = white_all; if (white_all == S.Length || white_all == 0) ans = 0;
- 境界の左の黒の数と教会の右にある白の数をカウント
else { for (int i = 0; i < N; i++) { if (S[i] == '#') { black++; } else { white--; } counter = black + white; if (counter < ans) { ans = counter; } } } Console.WriteLine(ans);
7.全コード
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main(string[] args) { string input = Console.ReadLine(); int N = int.Parse(input); input = Console.ReadLine(); char[] S= input.ToCharArray(); int white_all = 0; int black = 0; for(int i = 0; i < N; i++) { if (S[i] == '.') { white_all++; } } int ans = white_all; int counter = 0; int white = white_all; if (white_all == S.Length || white_all == 0) ans = 0; else { for (int i = 0; i < N; i++) { if (S[i] == '#') { black++; } else { white--; } counter = black + white; if (counter < ans) { ans = counter; } } } Console.WriteLine(ans); } }
8.最後に
本番解けなかったのが悔しいですね…