mayoko’s diary

プロコンとかいろいろ。

yukicoder No.285〜No.287

解法

No.285 はタネあかしすると簡単で, 元の値段に 108 を掛けたあと, それを 100 で割った商が整数部分, 100 で割った余りが少数部分になります。
本番は何も考えず 1.08 を掛けたら通ってしまいました。

int main() {
    ll n;
    cin >> n;
    n *= 108;
    ll tmp = n%100;
    printf("%lld.%lld%lld\n", n/100, tmp/10, tmp%10);
    return 0;
}

No.286 は bitDP で解けます。dp[s] = (s で表される分の商品を購入した時の最小負担額) とすると, 今までに買った商品の合計価格は s にのみ依存して決まるので, 割引される値段もわかり, bitDP で解けることがわかります。

const int MAXN = 16;
const int INF = 1e9;
int M[MAXN];
int dp[1<<MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> M[i];
    for (int i = 0; i < 1<<N; i++) dp[i] = INF;
    dp[0] = 0;
    for (int s = 0; s < 1<<N; s++) {
        if (dp[s] == INF) continue;
        int sum = 0;
        for (int i = 0; i < N; i++) if ((s>>i)&1) sum += M[i];
        sum %= 1000;
        for (int i = 0; i < N; i++) {
            if ((s>>i)&1) continue;
            int ns = s|1<<i;
            int now = M[i]-sum;
            now = max(now, 0);
            dp[ns] = min(dp[ns], dp[s] + now);
        }
    }
    cout << dp[(1<<N)-1] << endl;
    return 0;
}

No.287 は dp します。dp[m][sum] = (m 個目の時点で合計数が sum になっているような場合の数)としてがんばります。

ll dp[10][830];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    dp[0][0] = 1;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j <= 6*n; j++) {
            if (dp[i][j] == 0) continue;
            for (int k = 0; k <= n; k++) {
                dp[i+1][j+k] += dp[i][j];
            }
        }
    }
    cout << dp[8][6*n] << endl;
    return 0;
}