C++の練習を兼ねて, AtCoder Grand Contest 020 の 問題C (Median Sum) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 苦手なdpの訓練を積めたこと, および, bitsetの使い方を訓練できたのが非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 020 解説 を ご覧下さい.
■C++版プログラム(問題C／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// 解き直し. // https://img.atcoder.jp/agc020/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int a[2020]; int main(){ // 1. 入力情報. int N, aSum = 0; scanf("%d", &N); rep(i, N){ scanf("%d", &a[i]); aSum += a[i]; } // 2. dp更新. bitset<4040404> dp; rep(i, N){ // 2-1. dpのコピー作成. bitset<4040404> pd = dp; // 2-2. dpを左シフトしたものを考慮. dp |= (pd <<= a[i]); // 2-3. 数列の値を, true に 設定. dp[a[i]] = true; } // 3. 中央値を探索. int ans = 0; repx(i, (aSum + 1) / 2, 4040404){ if(dp[i]){ ans = i; break; } } // 4. 出力. printf("%d\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
[入力例] 3 1 2 1 [出力例] 2 ※AtCoderテストケースより [入力例] 1 58 [出力例] 58 ※AtCoderテストケースより [入力例] 5 2 17 3 5 25 [出力例] 27 [入力例] 15 18 3 52 9 32 6 47 24 32 61 2 30 11 7 30 [出力例] 182 [入力例] 50 1129 874 831 311 622 469 1696 1673 489 989 1643 1090 1805 1352 1775 1811 1454 301 17 82 1456 912 765 879 220 1582 1634 1907 1924 1563 1710 426 1709 113 112 415 685 1922 767 658 492 1721 247 677 1186 538 1095 1231 319 1024 [出力例] 25151 |
■参照サイト
AtCoder Grand Contest 020