CodeForces #262(Div2)

おはようございます。
昨日のCFの話です。

追記

フォロワーさんのおかげでB問題が通らないことは解決しました。

memo[sum+i] = (ll)b*(ll)pow(sum+i,a)+c; //before
memo[sum+i] = (ll)b*(ll)pow(sum+i,a+EPS)+c; //after

というようにpowの誤差をlong longに丸めるときに死んでいたようです。

A

問題

靴下をn足もっててm日ごとに母が買ってくる。
毎日少年は靴下を脱ぎ捨てる。
一体いつになったらなくなる？？？

解法

シミュレーションした

int main(){
    int n,m;
    cin >> n >> m;
    int cnt = 0;
    int ans = 0;
    while(true){
        if(n == 0){
            break;
        }
        if(cnt%m==0)n++;
        n--;
        cnt++;
    }
    printf("%d\n",cnt-1);
    return 0;
}

484Point

B

ちょっとした愚痴

なんでBが通らなかったのかわかりませんでした。
更にそれを考えていたら寝落ちしてました。

朝になって、pretestの結果を見たら手元の実行と解が違いました。
こんなことは初めてです。

g++のバージョンとかの違いで変わるものなのでしょうか？

自分のコードが合ってるかになったので、testcaseを手元で走らせてみたら、
全部通っていました。

通っていればratingは多分上がってたと思うのでつらいです。

問題

を満たすを求めよ。
ただし、とはの各桁の和である。
は入力で与えられる。

解法

例えば1 と 1000 と1000000のはどれも同じです。
これを利用してまず、探索量を減らすことができると考えました。
が同じと言うことは問題で与えられた、数式の右辺の結果は変わらないと
言うことがわかるので、先に各桁の和として考えられるものをすべて計算しておきます。

そして、その計算された数のが配列のindexと等しければ答えです。

ll memo[1024]={0};
bool vis[10][1024];
int a,b,c;
void solve(int n,int depth,int sum){
    if(depth==9){
        return ;
    }
    reps(i,n,10){
        if(!vis[depth][sum+i]){
            vis[depth][sum+i] = true;
            memo[sum+i] = (ll)b*(ll)pow(sum+i,a)+c;
            solve(i,depth+1,sum+i);
        }
    }
}
int main(){
    cin >> a >> b >> c;
    vector < ll >  ans;
    solve(0,0,0);
    rep(i,82){
        int x=0;
        int t=memo[i];
        rep(j,15){
            x+=t%10;
            t/=10;
        }
        if(x == i && memo[i] != 0 && memo[i]<1000000000){
            ans.PB(memo[i]);
        }
    }
    if(ans.size() == 0){
        puts("0");
    }
    else{
        printf("%ld\n",ans.size());
        rep(i,ans.size()){
            printf("%lld ",ans[i]);
        }
        puts("");
    }
    return 0;
}

まとめ

つらかった