SHIINBLOG

初めての競プロ

本日初めて 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);
}

やっぱり,こっちアルゴリズムを考えつく必要がありそうだ


次までに,今回の AGC029 の別な問題とか,前の大会の問題を解いて高速に求解できるようにならないといけないなぁと実感した.