ABC015 D 高橋くんの苦悩 典型DP
ABC015 D 高橋くんの苦悩
問題概要
リンク参照
考察
- dp[j][k]をj枚すでに貼っていて，現在の幅がkの時の価値の最大としてdp
- 遷移は幅と枚数に余裕がある場合に以下の遷移を行う
dp[j+1][k+a[i]]=max(dp[j+1][k+a[i]],dp[j][k]+b[i]) (k+a[i] <= w && j+1 <= n)
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ARRAY_MAX 100005 const int INF = INT32_MAX / 3; const ll MOD = 1e9 + 7; /******************************************************************************************/ int dp[55][10005]; int main() { int w, n, k; cin >> w >> n >> k; vector<pii> v(n); for (int i = 0; i < n; i++) { cin >> v[i].first >> v[i].second; } sort(v.begin(), v.end()); for (int i = 0; i < n; i++) { for (int k = n - 1; k >= 0; k--) { for (int j = w; j >= 0; j--) { if (j + v[i].first > w) { continue; } dp[k + 1][j + v[i].first] = max(dp[k + 1][j + v[i].first], dp[k][j] + v[i].second); } } } int ans = 0; for (int i = 0; i <= k; i++) { for (int j = 0; j <= w; j++) { ans = max(ans, dp[i][j]); } } cout << ans << endl; return 0; }
ABC092 C Traveling Plan 累積和を取って計算量削減
ABC092 C Traveling Plan
問題概要
リンク参照
考察
- 愚直に計算すると
かかるので計算量削減が必要．どう減らすか？
- 観光スポットを削除する部分以外は毎回コストは変わらないので毎回計算するのは無駄
- 今回は観光スポットを消さない場合のコストの総和(sumとする)を前処理で求めておいて，観光スポットiを消す場合について，sum-（観光スポットをiとi+1の間のコスト）-（観光スポットをiとi-1の間のコスト）+（観光スポットをi-1とi+1の間のコスト）を出力すれば
で間に合う
なお，バグりました
うく
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ARRAY_MAX 100005 const int INF = INT32_MAX / 3; const ll MOD = 1e9 + 7; int dx[4] = { 1,0,0,-1 }; int dy[4] = { 0,1,-1,0 }; /******************************************************************************************/ int main() { int n; cin >> n; vector<int> a; a.push_back(0); ll sum = 0; for (int i = 0; i < n; i++) { int c; cin >> c; a.push_back(c); } a.push_back(0); n += 2; for (int i = 0; i <= n - 2; i++) { sum += abs(a[(i + 1) % n] - a[i]); } for (int i = 1; i <= n - 2; i++) { cout << sum - abs(a[(i + 1) % n] - a[i]) - abs(a[i] - a[(i + n - 1) % n]) + abs(a[(i + 1) % n] - a[(i + n - 1) % n]) << endl; } return 0; }
第１回日本最強プログラマー学生選手権予選 B Kleene Inversion 転倒数
第１回日本最強プログラマー学生選手権予選 B Kleene Inversion
問題概要
リンク参照
考察
- 転倒数といえばここらへんでも過去に出題されている
https://atcoder.jp/contests/chokudai_s001/tasks/chokudai_S001_j
https://atcoder.jp/contests/kupc2018/tasks/kupc2018_e
- 今回は
- 整数列内の転倒数については愚直に計算してK倍すれば求まる
- 問題は連結した場合の転倒数について．これについては，整数列内の転倒数＊整数列ブロックの選び方(K*(K-1))の積で求まる
ぐぬぬ(´・ω・｀)
通したかった
300に見えない・・・・
ソースコード（考察1）
#define _USE_MATH_DEFINES #include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #include<bitset> #include<stack> #include<fstream> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) #define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef tuple<ll, ll, ll> lltpl; typedef tuple<int, int, int> tpl; int dy8[8] = { 2,2,-2,-2,1,1,-1,-1 }; int dx8[8] = { 1,-1,1,-1,2,-2,2,-2 }; int dx4[4] = { 1,0,0,-1 }; int dy4[4] = { 0,1,-1,0 }; /******************************************************************************************/ template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template<typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) { t = v; } template<typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } // vector template <typename T> istream& operator>>(istream & is, vector<T> & vec) { for (T& x : vec) is >> x; return is; } // pair template <typename T, typename U>ostream& operator<<(ostream & os, pair<T, U> & pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // vector template <typename T>ostream& operator<<(ostream & os, const vector<T> & vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); }os << "}"; return os; } // map template <typename T, typename U>ostream& operator<<(ostream & os, map<T, U> & map_var) { os << "{"; repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; }os << "}"; return os; } // set template <typename T>ostream& operator<<(ostream & os, set<T> & set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; }os << "}"; return os; } const int IINF = 1e9 + 7; const ll LINF = 1e18 + 7; constexpr ll MOD = 1e9 + 7; //ここから書くこと int main() { cin.tie(nullptr); ios::sync_with_stdio(false); ll n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } ll right = 0; ll total = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (a[i] > a[j]) { right++; } } for (int j = 0; j < n; j++) { if (a[i] > a[j]) { total++; } } } ll ans = 0; ans += right * k; ans %= MOD; ans += (((k * (k - 1) / 2) % MOD) * total) % MOD; ans %= MOD; cout << ans << endl; return 0; }
ABC145 D Knight
ABC145 D Knight
問題概要
リンク参照
考察1
- 全探索は厳しそうなので別の手段を考える
- 通常の縦横移動の遷移の組み合わせならnCr的なアプローチが使えたのでこれを発展させる
- (+1,+2)の遷移をN回，と(+2,+1)の遷移をM回とするとき，(N+M)回の中N回(+1,+2)の遷移が起こればいいので，
通り
- 答えがないケースについてはN<0，M<0,(x+y)が３の倍数でない場合を除いて終了
ぐぬぬ(´・ω・｀)
通したかった
ソースコード（考察1）
#define _USE_MATH_DEFINES #include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #include<bitset> #include<stack> #include<fstream> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) #define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef tuple<ll, ll, ll> lltpl; typedef tuple<int, int, int> tpl; int dy8[8] = { 2,2,-2,-2,1,1,-1,-1 }; int dx8[8] = { 1,-1,1,-1,2,-2,2,-2 }; int dx4[4] = { 1,0,0,-1 }; int dy4[4] = { 0,1,-1,0 }; /******************************************************************************************/ template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template<typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) { t = v; } template<typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } // vector template <typename T> istream& operator>>(istream & is, vector<T> & vec) { for (T& x : vec) is >> x; return is; } // pair template <typename T, typename U>ostream& operator<<(ostream & os, pair<T, U> & pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // vector template <typename T>ostream& operator<<(ostream & os, const vector<T> & vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); }os << "}"; return os; } // map template <typename T, typename U>ostream& operator<<(ostream & os, map<T, U> & map_var) { os << "{"; repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; }os << "}"; return os; } // set template <typename T>ostream& operator<<(ostream & os, set<T> & set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; }os << "}"; return os; } const int IINF = 1e9 + 7; const ll LINF = 1e18 + 7; constexpr ll MOD = 1e9 + 7; //ここから書くこと struct Combination { vector<ll> fact, rfact; Combination(ll sz) : fact(sz + 1), rfact(sz + 1) { fact[0] = 1; for (ll i = 1; i < fact.size(); i++) { fact[i] = fact[i - 1] * i % MOD; } //逆元 rfact[sz] = inv(fact[sz]); for (ll i = sz - 1; i >= 0; i--) { rfact[i] = rfact[i + 1] * (i + 1) % MOD; } } ll inv(ll x) { return pow(x, MOD - 2); } ll pow(ll x, ll n) { ll ret = 1; while (n > 0) { if (n & 1) (ret *= x) %= MOD; (x *= x) %= MOD; n >>= 1; } return (ret); } ll P(ll n, ll r) { if (r < 0 || n < r) return (0); return (fact[n] * rfact[n - r] % MOD); } ll C(ll p, ll q) { if (q < 0 || p < q) return (0); return (fact[p] * rfact[q] % MOD * rfact[p - q] % MOD); } ll H(ll n, ll r) { if (n < 0 || r < 0) return (0); return (r == 0 ? 1 : C(n + r - 1, r)); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int x, y; cin >> x >> y; int n = (2 * x - y) / 3; int m = -(x - 2 * y) / 3; if ((x + y) % 3 != 0) { cout << "0" << endl; return 0; } if (n < 0 || m < 0) { cout << "0" << endl; } else { Combination comb(n + m + 10); cout << comb.C(n + m, n)%MOD << endl; } return 0; }
yukicoder No.698 ペアでチームを作ろう
yukicoder No.698 ペアでチームを作ろう
問題概要
リンク参照
考察
- dp[i]:=状態iがペアを作っている時の最大値としてbitDPする
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #include<bitset> #include<stack> using namespace std; /******************************************************************************************/ int dp[1 << 15]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } for (int i = 0; i < (1 << N); i++) { for (int j = 0; j < N; j++) { if ((i >> j) & 1)continue; for (int k = 0; k < N; k++) { if ((i >> k) & 1)continue; dp[i | (1 << j) | (1 << k)] = max(dp[i | (1 << j) | (1 << k)], dp[i] + (A[j] ^ A[k])); } } } cout << dp[(1 << N) - 1] << endl; }
ABC063 C Bugged
ABC063 C Bugged
問題概要
リンク参照
考察1
- 合計が10の倍数でない→合計値が答え
- そうでない場合→合計値から10の倍数でない最小の整数を引いたものが最大
考察2
- dp[i]:=整数iを作れるか（作れる場合は1）とし，dp[0]=1で初期化
- dp[j]==1の場合はdp[j + A[i]]=1と遷移できる（配列外参照に注意）
- 最終的に答えはループで回して10の倍数でなく，かつフラグの立っているものの中で最大のものとなる
ソースコード（考察1）
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> using namespace std; /******************************************************************************************/ int main() { int n; cin >> n; vector<int> a(n); int sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } sort(a.begin(), a.end()); if ((sum % 10) != 0) { cout << sum << endl; return 0; } for (int i = 0; i < n; i++) { if (a[i] % 10) { cout << sum - a[i] << endl; return 0; } } cout << "0" << endl; return 0; }
ソースコード（考察2）
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #include<bitset> #include<stack> using namespace std; int dp[10005]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } dp[0] = 1; for (int i = 0; i < N; i++) { for (int j = 10000; j >= 0; j--) { if (dp[j] == 0)continue; if (j + A[i] <= 10000) { dp[j + A[i]] = 1; } } } int maxi = 0; for (int i = 0; i <= 10000; i++) { if (dp[i] == 1 && ((i % 10) != 0)) { maxi = max(maxi, i); } } cout << maxi << endl; }
yukicoder No.183 たのしい排他的論理和（EASY）
yukicoder No.183 たのしい排他的論理和（EASY）
問題概要
リンク参照
考察
- dp[i]:=整数iを作れるか（作れる場合は1）とし，dp[0]=1で初期化
- dp[j]==1の場合はdp[j^A[i]]=1と遷移できる（配列外参照に注意）
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #include<bitset> #include<stack> using namespace std; int dp[1<<16]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); int maxi = 0; int X = 0; for (int i = 0; i < N; i++) { cin >> A[i]; } dp[0] = 1; for (int i = 0; i < N; i++) { for (int j = (1 << 15); j >= 0; j--) { if (dp[j] == 0)continue; dp[j ^ A[i]] = 1; } } int sum = 0; for (int i = 0; i < (1 << 15); i++) { sum += dp[i]; } cout << sum << endl; }
