CodeForces 354Div2

　今回もダメでした。
http://codeforces.com/contest/676
A : Nicholas and Permutation
　コードをみたらpairとminとmaxが書いてあったので、そういう感じの問題らしいです。
B : Pyramid of Glass
　ピラミッド状に並べたワイングラスにワインを一秒ごとに一杯分流す。t秒で何杯埋まるか、という問題。
　真ん中の方が先に埋まるので頭を使って計算するのは大変です。入力が小さいので愚直解でも余裕でしょ、とメモリを大きめにとってDFSを書いたら意外と遅くて焦りましたがまあ通ってよかったです。

const int full = 1 << 12;
int glass[11][11];
void dfs(int h, int y, int w){
    int temp = glass[h][y];
    glass[h][y] += w;
    if(glass[h][y] >= full){
        glass[h][y] = full;
        w -= full - temp;
        if(w == 0) return;
        dfs(h + 1, y, w / 2);
        dfs(h + 1, y + 1, w / 2);
    }
}
int main(){
    int n, t;
    scanf("%d%d", &n, &t);
    memset(glass, 0, sizeof(glass));
    rep(i, t) dfs(0, 0, full);
    int ans = 0;
    rep(i, n) rep(j, i + 1) if(glass[i][j] == full) ans++;
    printf("%d\n", ans);
    return 0;
}

C : Vasya and String
　aとbだけからなる文字列。k回変更していい時、最長の単独文字部分列の長さを求めよ、という問題。
　累積和とかでもできるっぽいですけどまあ凡人の発想はしゃくとり法を二回やって大きい方ですよね。
　ところがk = 0の場合を忘れていて落ちました。CodeForcesパイセン、どう考えてもk = 0とかの意味不明なコーナーケースで落としにくるパターンが多すぎます。いや、僕もそろそろ学習しろよという話なんですが……。

int k, n; string s;
int solve(char aim){
    int ub = 0, lb = 0, cnt = 0, res = 0;
    bool updated = false;
    if(k == 0){
        rep(i, n){
            if(s[i] == aim) cnt = 0;
            else cnt++;
            res = max(cnt, res);
        }
        return res;
    }
    rep(i, n){
        if(s[i] == aim) cnt++;
        if(cnt >= k){
            ub = i;
            updated = true;
            break;
        }
    }
    if(!updated) return n;
    res = max(res, ub - lb + 1);
    ub++;
    for(; ub < n; ub++){
        if(s[ub] == aim)
          for(; ; lb++)
            if(s[lb] == aim){
                lb++;
                break;
            }
        res = max(res, ub - lb + 1);
    }
    return res;
}
int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n >> k >> s;
    cout << max(solve('a'), solve('b')) << endl;
    return 0;
}

D : Theseus and labyrinth
　これは拡張ダイクストラしなくても普通の幅優先で解ける！なぜなら遷移のコストがすべて１だから！
　というのはすぐわかったんですがこのブロックの種類はちょっとやりすぎでしょ……。なんだよドアって。普通に終わりませんでした。

　今回はわりと楽しく参加できましたが、相変わらずさっぱりレートが上がりませんね。コーナーケースに気をつけなくては……。