Tenka1 Programmer Contest/Tenka1 Programmer Beginner のC問題を解いてみた
昨日の天下一コンテストお疲れ様でした。 色々と課題の残るコンテストで学ぶ部分も多いコンテストでした。
今回のCのような問題が一番苦手なのかもしれません。。結構自分はデータ構造系の問題が得意なのですが、複雑なアルゴリズムを考える部分が苦手なんでここを磨き上げていきたいです。
では、以下問題
Stones
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
N 個の石が一列に並んでおり、すべての石は白か黒で塗られています。 石の状態は長さ N の文字列 S で表され、S の i 文字目が . のとき左から i 個目の石が白であり、# のとき左から i 個目の石が黒であることを表します。 高橋君は、0 個以上の石の色を黒または白に変更し、黒い石のすぐ右に白い石があるような箇所がないようにしたいです。 色を変更する必要のある石の個数の最小値を求めてください。
制約
* 1 ≤ N ≤ 2 × 10^5
* S は ., # のみからなる長さ N の文字列である
とこんな感じですね 解いてた時、しゃくとり法で反転区間が最小になるものを算出するのかなと思っていたのですが、それだと 不連続な場合の問題が解けないため却下という感じです。 また愚直にシミュレーションを行い比較を行うとO(2N)となるのでとても現実的でないことがわかります。
考えたこと
先に結果の形から考えてみましょう結果のパターンとして3つのパターンが考えられます。
* "白 白 ... 黒 黒" この時 (白は連続し黒との境界以降白は出てこないものとする)
* "白 白 白 ... 白 白"
* "黒 黒 黒 ... 黒 黒"
となります。 そして今回の問題の肝は反転回数が最小の値を求めよとのことなので、上記の3パターンに帰着するための反転回数の最小を算出することになります。
ではどうすれば良いか 白の数を数え上げ、白の反転の個数と黒の反転の個数の和の最小を求めることで解決します。 黒の反転の個数を0とし白の反転の個数を白の数とします。 ではここでルールを決めます(例として".#..#"の文字列を使用します)
* 最初に数え上げた白の個数を右の値に入れます
* 無視できるのは右にある黒の個数と左にある白の個数
* 文字列を線形探索するとき
* 今の要素が黒ならば、右にある黒を+1します。
* それ以外ならば右にある白を左に移動させます。
1 回目
黒
| 左 | 右 |
|---|---|
| 0 | 0 |
白
| 左 | 右 |
|---|---|
| 1 | 2 |
この時は 2
2回目
黒
| 左 | 右 |
|---|---|
| 1 | 0 |
白
| 左 | 右 |
|---|---|
| 1 | 2 |
この時は 3
3回目
黒
| 左 | 右 |
|---|---|
| 1 | 0 |
白
| 左 | 右 |
|---|---|
| 2 | 1 |
この時は 2
4回目
黒
| 左 | 右 |
|---|---|
| 1 | 0 |
白
| 左 | 右 |
|---|---|
| 2 | 0 |
この時は 1
5回目
黒
| 左 | 右 |
|---|---|
| 2 | 0 |
白
| 左 | 右 |
|---|---|
| 2 | 0 |
この時は 2
結局5回の中で最小は 1 つまり、"....#" という文字列になります このアルゴリズムで問題なく解けそうですね。
フロー
* 入力の受け取り
* 文字列に対してループ
* その要素が"."ならば白の個数を+1
* 右にある白を白の個数に黒を0にし、答えを白の個数に定義
* 文字列に対してループ
* その要素が"#"ならば 黒の個数 を+1
* それ以外の場合 白の個数を - 1
* 答えに答えと白と黒の個数の最小を代入
* 答えを出力
とこんな感じ 2回目の文字列ループの際に前述したルールが組み込まれています
プログラム
#include <iostream> #include <vector> #include <string> #include <cstdlib> #include <algorithm> using namespace std; int main(void){ long long N; string S; cin >> N >> S; long long w = 0; for(long long i = 0; i < N; i++){ if(S[i] == '.'){ w++; } } long long BL = 0; long long WR = w; long long ans = w; for(long long i = 0; i < N; i++){ if(S[i] == '#'){ BL++; }else{ WR--; } ans = min(ans,BL + WR); } cout << ans << endl; return 0; }
とこんな感じでAC取れました。 このようなアルゴリズムの問題にめっぽう弱いので慣れていきたいです。。
