Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

Codeforces Round #121(Div.2)

結果

ooo--(+0/-0)2184pts 135th
Rate:1501->1588

A

意外とめんどい。とりあえず10^9以下の三角数を列挙してsetに突っ込んで
それらに対して入力からある三角数を引いたものが集合内にあるかどうかでやった。

初め全列挙とかしてたら意外と時間かかった。

B

前にあったAtCoderに引きずられてBinarySearch+BFSとかめんどい実装をした上に
BFSで既にqueueに突っ込まれてるのを追加しないとかいうのを忘れたために一回MLEする。

連続する2セルが到達不能になっていなければ到達可能なのでそれをみればよかった。
Lockして、初めのセルを考え落としてる人はいないかなーと思ったけどいなかった。

C

Readforcesェ…
要は与えられた文字列をしりとりのように繋いでいってできる文字列で、初めと終わりが同じ文字であるような文字列のうち最長のものの長さを求めろ、という問題。
初め読む気失せてBのhackとかをぼーっと眺めていたけどこれではまずいと思いとりかかる。

dp[i][j][k] := i-1番目までの文字列を使ってできる文字列のうち、jで始まってkで終わるものの最長の長さ

としてみる。
i-thの文字列がsで始まってtで終わる場合、任意のaに対して

dp[i+1][a][t] = max(dp[i][a][t], dp[i][a][s] + str[i].size());

と更新することができる。(sで終わっている文字列にs(.*)tを繋いで末尾をtにするような感じ)

これでO(5*10^5*26*26) -> O(10^8)だからまぁ間に合うかなーと思う。

  • >TLE

入力数が多いのでcinが遅いのかなと思い

std::ios_base::sync_with_stdio(false);

を追加してみるととりあえずpretestは通った。これもうテンプレに書いておくべきですね!
残り時間も少ないのでこれでTLEしたら後で考えようと思い放置

  • >結局通った。一番かかっていたので1300msecぐらいだった。

後で考えるとDPテーブルのiは要らないっぽい。

dp[i][j] := iで始まってjで終わる文字列の最大の長さ

でよくて、こうするとDPテーブルの更新はO(5*10^5*26)でもっと余裕で間に合う。

加えて、初めはdp[500002][26][26]と取っていて、compileがすげー遅かった。
使い回せばdp[2][26][26]で良い。

以下ソース

int dp[2][26][26];

int main(){
    std::ios_base::sync_with_stdio(false);
    string str;
    int n,len;
    int hd,tl;
    cin >> n;
    vector<string> vs(n);
    memset(dp, -1, sizeof(dp));
    for(int i=0;i<n;i++){
        cin >> vs[i];
    }

    int cur = 0, nxt = 1;
    for(int i=0;i<vs.size();i++){
        hd = vs[i][0] - 'a';
        tl = vs[i][vs[i].size()-1] - 'a';
        len = vs[i].size();
        dp[nxt][hd][tl] = max(len, dp[cur][hd][tl]);
        //printf("dp[%d][%d][%d] = %d\n",i+1,hd,tl,dp[nxt][hd][tl]);
        for(int l=0;l<26;l++){
            if(dp[cur][l][hd] != -1){
                dp[nxt][l][tl] = max(dp[cur][l][tl], dp[cur][l][hd] + len);
                //printf("dp[%d][%d][%d] = %d\n",i+1,l,tl,dp[nxt][l][tl]);
            }
        }

        for(int j=0;j<26;j++){
            for(int k=0;k<26;k++){
                dp[nxt][j][k] = max(dp[nxt][j][k], dp[cur][j][k]);
            }
        }

        cur = 1 - cur;
        nxt = 1 - nxt;
    }
    int ret=-1;
    
    for(int i=0;i<26;i++){
        ret = max(ret, dp[cur][i][i]);
    }
    if(ret == -1) ret = 0;
    cout << ret << endl;  
}

感想

レート1600は欲しいですねー。