初めての競プロ - zeronosu77108’s blog

本日初めて AtCoder Grand Contest 029 に参加しました．

なんだかんだで初めての競プロです．

大学入ってすぐに，何ヶ所か競プロのサイトに登録していたのに
1回も参加した事が無かった…

気付いたときには始まっててちょっと焦った

結果は惨敗でした．
~~Grand じゃなくて Beginners に参加したかった…~~

不慣れということと，1回目でタイムアウトが出てしまってとても焦ってしまった．
結局時間内に1問も解けなかった．

落ち込んでいても仕方が無いので，
次のためのお勉強をし（他の人が出した物を読み解き）ます．

A - Irreversible operation

問題文はこちら

「黒白の並びならひっくり返す」を繰り返して何回ひっくり返せるかという問題．

最初は，1週「黒白」をひっくり返しつつ探して，というのを繰り返すプログラムを書いた．
（時間制限が 2sec だったから無理な気はしていた）

次に， string.h の strstr を使ったら早いんじゃないかと使ってみた．
結果はタイムアウト変わらず…

最後らへんに「黒白」を見つけたときに，その前の黒を数えたら良いのではないかと考えた．
「黒黒白」なら 2回ひっくり返せるみたいな．

これ実装して提出したら，いくつか不正解に．タイムアウトではなくなったものの，何が間違ってるのか分からなくて，
悩んでる間に終了してしまった．

ということで，一番最初に解いていた方のソースコードを参考にする．

まず，準備具合が違いますね．

#define sqr(x) ((x)*(x))

とか

#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)

とか用意している．

求解のアルゴリズム的には，黒ならカウントの変数をインクリメントして，白が来たらそれを解用の変数に足すもの．

僕のアルゴリズムの上位互換みたいな感じがする…

確かに黒が連続の後に白が来た場合，1つずれるだけなので，ひっくり返せる回数は増えていく．

僕が最後に考えていたアルゴリズムは，
黒を数えつつ白に変えていったけど，最後の黒 1つだけを白にすれば良くて，
ルールを表現できていなかったみたい．

ということで書き直してみたのだけど，これを提出してもタイムアウト…

#include <stdlib.h>
#include <stdio.h>

#define BUF_SIZE 200010
int main(void){
    unsigned long long count = 0;
    char s[BUF_SIZE];
    int i;
    int j;
    fgets(s, BUF_SIZE, stdin);
    for(i=0; i<BUF_SIZE; i++) {
        if( s[i] == '\n' || s[i] == '\0') {
            break;
        }
        
        if( s[i] == 'B' && s[i+1] ==  'W' ){
            count++;
            
            for( j = 1;  (i-j) >= 0; j++) {
                if( s[i-j] == 'B') {
                    count++;
                } else {
                    s[i-j+1] = 'W';
                    break;
                }
            }
            
            if( j == 1) {
                s[i] = 'W';
            }
            s[i+1] = 'B';
        }
    }
    printf("%llu",count);
}