読者です 読者をやめる 読者になる 読者になる

Codeforces Beta Round #64

xx---死亡

それはとっても悲しいなって。


[00:00] A読む。

んー、これはシミュレーションして小さいケースを列挙してOEIS使えばいいのでは

→組む。バグる。辛い気持ちになる。

→いやこれ手動でやった方が早いだろ。

→・・・どうみても3^(n-1)です。

→n=0がコーナーケースやな!よし!0出力するコード書いて提出や!(←大きな間違い)

[00:14] A passed pretest

とりあえずA Hackしよう。Lockしてっと・・・。

→0の時1返すソースだ!

→Hackしてみる。Unsuccessful hacking attempt

→・・・ぇ?0が正解じゃないの?

→うわ死んだ、やっちまった・・・絶望しながら500点くらい稼ごうとやっきになる。

→3人倒す。

→最後に余り取ってるソースとかあるので落とそうとしたら2連続くらいで他の人に取られる。

→悲しい気持ちになる。

[00:33]A was hacked.

よく20分も耐えたなーとか思いつつBを読みはじめる。

→なんか境界条件とか不明瞭なとこ多すぎやろ・・・。

→Clarとか使って30分くらいかけてやっと題意をきちんと理解。

→とりあえず先頭から貪欲に詰め込むだけだとなぜか駄目だと思い込み尺取法とか実装しまくる。

[01:37]B passed pretest

うーん、落ちそうだけどまあいいや。

→Dを見る。とりあえずTLE解法とかで書いて他の人Hackできないかな?

→TLE解法すら書けなかったので、BのHackを試みる。

→先頭から取っていくコードの反例を考えるも思いつかず、絶望。

[02:00] おわり

死んだ。

System Test

Bが落ちる。やはり落ちてしまうと結構悔しい。

結果

0.0 + 250.0(Hack) = 250.0.

680位/721 (最下位)

レート:18191706(-INF)

まあ元のレートに戻ったと言ったところ。CFだと下落したことによるあんまりショックは無いけど、Div2まで落ちなかったのはちょっとショック。(Div2でおいしい思いしたかった)

ソース

WAしたので載せる価値がないけど、一応載せる。BはなんでWAしたんだろう。

A

//間違った解答です
int main(){
        int n,m,ret=0;
        cin >> n;
        int dp[2000] = {0};
        dp[1] = 1;
        rep(i,n){
                dp[i+2] = (dp[i+1] * 3) % (1000000+3);
        }
        cout << dp[n] << endl;
}

B

//間違った解答です
bool f = true;
string t;
vector<string> text;
vector<int> sz;
int dp[10002] = {0};
int ans = 0 , n;

void split(int L ,int R){
    dp[0] = 0;
    int l = L , r = L;
    int mx = -1 , ml = 1, mr = 1;
    while(l <= r && r <= R){
        int tmp = dp[r] - dp[l-1] + (r-l);
        if( tmp > n){
            l++;
        }else{
            if(tmp > mx){
                mx = tmp;
                ml = l , mr = r;
            }
            r++;
        }
    }
    if(mx == -1){
        f = false;
        return;
    }else{
        ans++;
        if(ml > L) split(L,ml-1);
        if(mr < R) split(mr+1,R);
    }
}
int main(){
    cin >> n;
    getline(cin,t);
    getline(cin,t);
    int c = 0;
    for(int i=0;i<t.size();i++){
        if(t[i] == '.' || t[i] == '?' || t[i] == '!'){
            sz.push_back(c+1);
            c = 0;
            i++;
        }else{
            c++;
        }
    }
    rep(i,sz.size()) dp[i+1] = dp[i] + sz[i];
    split(1,sz.size());
    if(!f)cout << "Impossible" << endl;
    else cout << ans << endl;
}