NEC Programming Contest 2022 (AtCoder Beginner Contest 267) - AtCoder
B - Split?
- 1番のピンが立っていたらNo
- 各レーンで1本でもピンが立っているレーン番号の集合を取る
- ピンが立っているレーン番号を昇順にみていって間が空いていたらYes
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' const vector<vector<int>> g = { { 6 }, { 3 }, { 1,7 }, { 0,4 }, { 2,8 }, { 5 }, { 9 } }; const int l = g.size(); int main() { string s; cin >> s; if (s[0] == '1') { cout << "No" << endl; return 0; } vector<int> on; REP(i,l) for(int v: g[i]) { if (s[v] == '1') { on.push_back(i); break; } } bool ok = false; int last = -1; for(int v: on) { if (last == -1) last = v; if (v - last > 1) ok = true; last = v; } cout << (ok ? "Yes" : "No") << endl; return 0; }
C - Index × A(Continuous ver.)
- 配列aの累積和を取っておく
- 0からmまでの連続部分列を計算しておく
- 1から1+mまでの連続部分列の計算は差分を取っていく。2で求めた値に、0〜mの累積和を引いて、a[1]*m を足すことで求められる
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' using ll = long long; int main() { int n,m; cin >> n >> m; vector<ll> a(n); REP(i,n) cin >> a[i]; vector<ll> ac(n+1); // 累積和 REP(i,n) ac[i+1] = ac[i] + a[i]; ll now = 0; REP(i,m) now += a[i] * (i+1); ll ans = now; for(int i = 1; i < n-m+1; i++) { now -= ac[i+m-1] - ac[i-1]; now += a[i+m-1] * m; ans = max(ans,now); } cout << ans << endl; return 0; }
D - Index × A(Not Continuous ver.)
- dpする。dp[i][j] := i番目までみたときにj個選んだときの最大値
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' using ll = long long; const ll LINF = numeric_limits<ll>::max(); int main() { ll n,m; cin >> n >> m; vector<ll> a(n); REP(i,n) cin >> a[i]; vector<ll> dp(m+1, -LINF); dp[0] = 0; REP(i,n) { vector<ll> p(m+1, -LINF); p[0] = 0; swap(dp,p); REP(j,m) { if (p[j] == -LINF) continue; dp[j+1] = max(p[j+1], p[j] + a[i] * (j+1)); } } cout << dp[m] << endl; return 0; }