yukicoder contest 241

yukicoder.me

ゆきこ〜
最近ゆきこ好きになってきた

No.1009 面積の求め方

区分求積法を実装する
誤差を考えてN = 1e-5くらいで
1/6公式が使えるらしい…

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double a, b;
    cin >> a >> b;
    auto f = [&](double x) -> double{
        return abs((x - a) * (x - b));
    };
    double ans = 0;
    double N = 1e6;
    double h = (b - a) / N;
    for(double i=1;i<=N;i++){
        ans += f(a+h*i);
    }
    ans *= h;
    printf("%.12lf\n", ans);
}

No.1010 折って重ねて

貪欲でいいらしい
貪欲出来るかわからなかったのでDPをした
dp[i][j] := 縦にi回、横にj回半分にできるかどうか
奇数の時半分にするのに困ってdouble型にしたけど切り上げてよかったね

提出コード

int dp[40][40];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double x, y, h;
    cin >> x >> y >> h;
    x *= 1000, y *= 1000;
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    REP(i,40) REP(j,40){
        if(~dp[i][j]){
            double H = h;
            int cnt = i + j;
            while(cnt > 0) H *= 2, cnt--;
            double X = x;
            cnt = i;
            while(cnt > 0) X /= 2, cnt--;
            double Y = y;
            cnt = j;
            while(cnt > 0) Y /= 2, cnt--;
            if(X > H) dp[i+1][j] = dp[i][j] + 1;
            if(Y > H) dp[i][j+1] = dp[i][j] + 1;
        }
    }
    int ans = 0;
    REP(i,40) REP(j,40) if(dp[i][j] != -1) chmax(ans, dp[i][j]);
    cout << ans << endl;
}

No.1011 Infinite Stairs

これはDP
なんだけど愚直にやるとくらいで間に合わない

REP(i,N) REP(k,K+1){
    for(int d=1;i<=D;d++){
        dp[i+1][k+d] += dp[i][j];
    }
}

愚直コードを睨むとdについてのループが毎回同じ区間の処理をしていることに気づく
こういうときは累積和で高速化出来る
そうするとでこの問題を解くことが出来る

提出コード

using mint = Fp<MOD>;
mint dp[333][90909];
mint sum[333][90909];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, d, K;
    cin >> N >> d >> K;

    dp[0][0] = 1;
    sum[0][0] = 1;
    REP(i,N){
        REP(j,K+1){
            if(j - d > 0) dp[i+1][j] = sum[i][j] - sum[i][j-d];
            else dp[i+1][j] = sum[i][j] - sum[i][0];
            sum[i][j+1] = sum[i][j] + dp[i][j];
        }
    }
    cout << dp[N][K] << endl;
}

No.1012 荷物収集

ほとんど解説通りだった
を考えると 絶対値が外せると累積和を取っておくことで各クエリに高速で答えられる
そのため、予めxについてソートしておき との累積和を前処理しておく
そうすると各クエリに対して、Xで二分探索するとで答えられる

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    vector<pair<ll,ll>> v(N);
    REP(i,N){
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());
    vector<ll> sumX(N+1), sumW(N+1);
    REP(i,N) sumX[i+1] = sumX[i] + v[i].first * v[i].second, sumW[i+1] = sumW[i] + v[i].second;
    REP(i,Q){
        ll X;
        cin >> X;
        int idx = lower_bound(v.begin(), v.end(), make_pair(X,0LL)) - v.begin();
        //cout << idx << endl;
        ll ans = (X * sumW[idx] - sumX[idx]);
        //cout << ans << " ";
        ans += (sumX[N] - sumX[idx]) - X * (sumW[N] - sumW[idx]);
        cout << ans << endl;
    }
} 

No.1013 〇マス進む

CとDで時間使っちゃってコンテスト中間に合わなかった、残念
ダブリングするだけなので余り書くことがない

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<int> P(N);
    REP(i,N){
        cin >> P[i];
    }
    vector<vector<ll>> to(33, vector<ll>(N));
    REP(i,N) to[0][i] = P[i];
    REP(i,32) REP(j,N) to[i+1][j] = to[i][j] + to[i][(j+to[i][j])%N];

    REP(i,N){
        ll cur = i;
        REP(j,32){
            if((K >> j) & 1){
                cur += to[j][cur%N];
            }
        }
        cout << cur + 1 << endl;
    }
}

おわりに

ゆきこ結構典型が出るので楽しい（解けるので）
過去問埋めもしようかなあと考え中