CFのつらい思ひ出 Code forces #257(div2)

こんばんは。chigichanです。
今日はタイトルどおり、つらぽよを決めた話をします。

今日、わたしはCodeforces #257に参加していました。

結果は3つpretest通って、1つしか通らなかったです。
なぜ、ほかの二つが通らなかったのか等をわたしのエクストリーム日本語訳とともに
これから綴っていきたいと思います。

A

キャンディーを配るはなし。
それぞれの子どもたちはキャンディーを一定個数以上をもらわない限り、
キャンディーおじさんのもとに並ぶ。
こうした時に、一番最後にキャンディーをわたす子どもは最初の状態で何番目に並んでいた子か？

解法->queueを使ってほいほいシミュレートした。

int main(){
    int n,m;
    int candy[128];
    scanf("%d%d",&n,&m);
    queue < int > Q;
    rep(i,n){
        Q.push(i);
    }
    rep(i,n){
        scanf("%d",&candy[i]);
    }
    int ans = -1;
    while(!Q.empty()){
        int d = Q.front();Q.pop();
        if(candy[d]>m){
            candy[d] -= m;
            Q.push(d);
        }
        ans = d;
    }
    printf("%d\n",ans+1);
    return 0;
}

490pointだったのでよかったと思う。

B

なんかの漸化式が与えられるので、n番目のmod1000000007を答えてくれ。

解法->普通にループとか回していたら、死ぬのでどうしようと思って、
とりあえずノートにsampleのf1~f9までを書いてみたら、mod6で場合分け出来そうだったので書く。
負の数のmodがわからんなぁとか思いながら適当に

if(x < 0) x+= MOD;

みたいなのを入れた。
が、一文だけ+MODしちゃいけないのにしてたとこあったのでWA。
その後、それ訂正したけどWAでなんでかなとか思ってたら、
最初の入力で与えられる、x,yのMODを取るのをあとでしてたのでバグっていた。

int main(){
    int a,b;
    int n;
    scanf("%d%d%d",&a,&b,&n);
    int x = n%6;
    int c = a;
    if(c < 0)c += MOD;
    int e = b;
    if(e < 0)e += MOD;
    int d = e-c;
    if(d < 0)d += MOD;

    if(x == 1){
        printf("%d\n",c);
    }
    else if(x == 2){
        printf("%d\n",e);
    }
    else if(x == 3){
        printf("%d\n",d);
    }
    else if(x == 4){
        if(-c < 0)printf("%d\n",-c+MOD);
        else printf("%d\n",-c);
    }
    else if(x == 5){
        if(-e < 0)printf("%d\n",-e+MOD);
        else printf("%d\n",-e);
    }
    else{
        if(-d < 0)printf("%d\n",-d+MOD);
        else printf("%d\n",-d);
    }
    return 0;
}

これ変数の順番がちょっとおかしいのは、dとbを見間違えることが以前あったから。

C

n*mの板チョコ的ななにかがあってそれをk回だけ、縦か横にザクッと切れる。
この時に切った破片たちのそれぞれの面積の中で最も最小のものを最大化した時の、
面積をどうなるのん？

解法->いろいろ考えたけど
・nの約数をまず求める。
・一辺が約数個になるように切ってみる
・次にk-(上で切った回数)回 mの辺を切ってみる

というのをnの約数個回 調べる。

同様にmの約数についても同じようにして調べる。

そして最後にmaxをとった。

が

この方針を立てていたのに、なぜかこのような一文を入れていた

if((n-1)*(m-1)<k)puts("-1");

これは

2 2 2

のケースで見事に散りました。(頭がない)

別にこれをしなくても、上の方針だけでACします。(答えの変数を-1で初期化しておけば)

vi div(ll n){
    vi res;
    for(ll i = 1; i * i <= n; i++){
        res.PB(i);
        if(n/i != i)res.PB(n/i);
    }
    return res;
}
int main(){
    ll n,m;
    ll k;
    scanf("%lld%lld%lld",&n,&m,&k);
    if(n<m)swap(n,m);
    ll ma = -1;
    vi x = div(n);
    vi y = div(m);
    reverse(x.begin(),x.end());
    rep(i,x.size()){
        if(n/x[i]-1>k)continue;
        if((k-(n/x[i]-1))>=m){
            continue;
        }
        ma = max(ma,x[i]*(m/(k-(n/x[i]-1)+1)));
    }
    reverse(y.begin(),y.end());
    rep(i,y.size()){
        if(m/y[i]-1>k)continue;
        if((k-(m/y[i]-1))>=n){
            continue;
        }
        ma = max(ma,y[i]*(n/(k-(m/y[i]-1)+1)));
    }    
    printf("%lld\n",ma);
    return 0;
}

まとめ

・冷静になろう。
・変なミスは精神的にかなり来るのでやめよう。
・rating自体は上がったので神とかに感謝しよう。
・翻訳に一度もかけなかったのは良い。
・Dはグラフらしかったので解けばよかった感(問題を飛ばす勇気)。