ARC 096 C-E

昨日ARC096に出ました.

順位:212位

パフォーマンス:2008

レーティング:1608→1662(+54)

早どきに失敗した割には黄パフォ出て良かったかな.今年ICPCでチームを組むolpheしゃんは黄だしferinしゃんも黄になりそうなので,僕もちゃんとコンテストに出てレート上げないとね.明日から何やろう.

・C問題 Half and Half

Aピザ,Bピザ,ABピザ(Aピザ半分とBピザ半分ずつからなるピザ)があり,それぞれ1枚A円,B円,C円である.AピザX枚とBピザY枚を購入したい.最小で何円必要?という問題.

こういう問題はへんにかんがえるより,全て試してしまうのが安全.ABピザを何枚買うか決めると,自動的にAピザ,Bピザを何枚買うことになるかが決まる.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int main() {
    int A, B, C;
    cin >> A >> B >> C;
    int X, Y;
    cin >> X >> Y;
    int ans = 1 << 30;
    for (int i = 0; i <= max(X, Y); i++) {
        int x = max(X - i, 0);
        int y = max(Y - i, 0);
        ans = min(ans, A*x + B*y + C*2*i);
    }
    cout << ans << endl;
}

・D問題 Static Sushi

外周の長さがCメートルのカウンターがあり,中橋くんはカウンター上のある点にいる.カウンター上にN貫の寿司が置かれている.i番目の寿司のカロリーはv[i]キロカロリーで,中橋くんがいる点からx[i]メートルだけ時計周りに進んだ位置に置いてある.中橋くんはカウンターの外周を自由に歩き回ることができ,寿司のある位置まで来るとそれを食べることができる.ただし,中橋くんは1メートル歩くごとに1キロカロリー消費する.中橋くんは好きな位置で店を出ることが出来るとしたとき,中橋くんが摂取できる正味のカロリーの最大値を求めよ.という問題.

動き方としては時計周りに何メートルか進んで反時計周りに引き返す,またはその逆があり得て,寿司のない所まで歩くのはカロリーの無駄なので歩く区間の端は寿司のある位置だとしてよい.ということで,時計周り/反時計周りにk番目の寿司まで食べたときの差し引きのカロリーを求めた上で累積maxを取っておくと,時計周りにk番目の寿司まで食べてから反時計周りに引き返したときに摂取できる最大カロリーが分かって終わり.本番ではにぶたんとかを使ったもっとめんどうなコードを書いた.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL x[100010], v[100010];
LL a[100010], b[100010];
int main() {
    int N;
    LL C;
    cin >> N >> C;
    for (int i = 1; i <= N; i++) cin >> x[i] >> v[i];
    x[N + 1] = C;
    for (int i = 1; i <= N; i++) a[i] = a[i - 1] + v[i] - (x[i] - x[i - 1]);
    for (int i = 1; i <= N; i++) a[i] = max(a[i], a[i - 1]);
    for (int i = N; i >= 1; i--) b[i] = b[i + 1] + v[i] - (x[i + 1] - x[i]);
    for (int i = N; i >= 1; i--) b[i] = max(b[i], b[i + 1]);
    LL ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, a[i]);
        ans = max(ans, b[i]);
        ans = max(ans, a[i] + b[i + 1] - x[i]);
        ans = max(ans, b[i] + a[i - 1] - (C - x[i]));
    }
    cout << ans << endl;
}

E問題 Everything on it

N個のトッピングがあり,そのうち好きなものを選んでラーメンに乗せることができる.このときラーメンの種類は2^N通りある.これらのラーメンからいくつかのラーメンを選ぶとき,「同じ種類のラーメンを2個以上選ばない」「全てのトッピングが選んだラーメンのうち2個以上に乗っている」という二つの条件を満たすような選び方は何通りあるか.という問題.

「全てのトッピングについて,それが乗っているラーメンが2個以上」というのは数えにくいので余事象である「あるトッピングがあって,乗っているラーメンが2個未満である」場合を数えることにする."A(k)=トッピングkが乗っているラーメンが2個未満である選び方の集合"とすると包除原理から求めたい場合の数は|A(1)|+|A(2)|+...+|A(N)|-(|A(1)∩A(2)|+|A(1)∩A(3)|+...)+...となる.で,よくかんがえると"k個のトッピングがあって,それらの乗っているラーメンが2個未満である選び方"というのは,それがどのk個だろうとかわらないことに気づく.よって"f(k)=トッピング1~kについて,それらが乗っているラーメンが2個未満(それ以外のトッピングはなんでもいい)である選び方"とすると,先ほどの包除原理の式はシンプルにΣ[k=1...N]combination[N,k]・f(k)・(-1)^(k-1)と書くことができる.また,実は全体の場合の数はf(0)と書けるからこれを含めると,答えはΣ[k=0...N]combination[N,k]・f(k)・(-1)^kとなる.

さて,あとはf(k)の計算方法.トッピング1~kからいくつか選んでdistinctなグループをx個作る場合の数をg(k,x)とする.各グループについてのこりのトッピングの選び方が2^(N-k)通りある.また,何個のグループを作る場合でも,のこりのトッピングの中では好きにグループを作れるから結局f(k)=Σ2^(2^(N-k))・g(k,x)・2^(x(N-k))となる.

ではg(k,x)は?これはスターリング数というのに似ているらしく,DPが出来る.トッピングkをグループに含めない場合,トッピングkだけのグループを作る場合,トッピング1~k-1まででグループを作ってそのどれかに入れる場合にわかれるのでg(k,x)=g(k-1,x)+g(k-1,x-1)+g(k-1,x)*xとなる.

学びのある問題だった.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL dp[3010][3010];
LL comb[3010][3010];
LL mod_pow(LL a, LL b,LL mod) {
    if (b == 0) return 1;
    if (b % 2 == 0) {
        LL t = mod_pow(a, b / 2, mod);
        return (t*t) % mod;
    }
    return (a*mod_pow(a, b - 1, mod)) % mod;
}
LL f(int N,int k,LL mod) {
    LL ans = 0;
    LL a = mod_pow(2, N - k, mod);
    LL b = 1;
    for (int i = 0; i <= k; i++) {
        LL t = (dp[k][i] * b) % mod;
        (b *= a) %= mod;
        (ans += t) %= mod;
    }
    (ans *= mod_pow(2, mod_pow(2, N - k, mod - 1), mod)) %= mod;
    return ans;
}
int main() {
    int N, M;
    cin >> N >> M;
    dp[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            (dp[i][j] += dp[i - 1][j]) %= M;
            (dp[i][j] += dp[i - 1][j] * j) %= M;
            (dp[i][j] += dp[i - 1][j - 1]) %= M;
        }
    }
    comb[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; j++) {
            (comb[i][j] += comb[i - 1][j]) %= M;
            (comb[i][j] += comb[i - 1][j - 1]) %= M;
        }
    }
    LL ans = 0;
    LL minus = 0;
    for (int i = 0; i <= N; i++) {
        LL t = f(N, i, M);
        (t *= comb[N][i]) %= M;
        if (minus) (t *= M - 1) %= M;
        minus ^= 1;
        (ans += t) %= M;
    }
    cout << ans << endl;
}