AtCoder abc369 参加メモ
AtCoder Beginner Contest 369 - AtCoder
A - 369
O(1) でミスなく解く自信がなかったので全探索
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' int main() { int a,b; cin >> a >> b; int ans = 0; for(int c = -100; c <= 200; c++) { vector<int> t = { a,b,c }; sort(t.begin(),t.end()); if (t[1]-t[0] == t[2]-t[1]) ans++; } cout << ans << endl; return 0; }
B - Piano 3
L, R の最後のポジションを持って差分を計算する
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' int main() { int n; cin >> n; vector<int> p(2,-1); int ans = 0; REP(i,n) { int a; char s; cin >> a >> s; int idx = s == 'L' ? 0 : 1; if (p[idx] != -1) ans += abs(p[idx] - a); p[idx] = a; } cout << ans << endl; return 0; }
C - Count Arithmetic Subarrays
難しいかった。
尺取法の要領で l から等差数列になっている最大の長さを求める。 長さを n と置いたとき、nC2 通りの組み合わせがあるのでそれを足して行く。
#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; cin >> n; vector<int > a(n); REP(i,n) cin >> a[i]; ll ans = n; int l = 0; while (l < n - 1) { int r = l + 1; int d = a[r] - a[l]; while(r < n-1) { if (a[r+1] - a[r] != d) break; r++; } // len := l から等差数列になっている最大の長さ int len = r - l + 1; // len から2つの位置を決めたときの組み合わせ数 lenC2 if (len > 1) ans += (ll)len * (len - 1) / 2; l = r; } cout << ans << endl; return 0; }
D - Bonus EXP
DP。 dp[i][j] := i 番目までみたとき、j=0 倒したのが偶数、j=1 倒したのが奇数回 のときの最大の経験値
#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(); template<class T> void chmax(T& a, T b) { a = max(a,b); } int main() { int n; cin >> n; vector<int> a(n); REP(i,n) cin >> a[i]; // dp[i][j] := i 番目までみたとき、j=0 倒したのが偶数、j=1 倒したのが奇数回 のときの最大の経験値 vector dp(n+1,vector<ll>(2,-LINF)); dp[0][0] = 0; REP(i,n) { // 倒さない chmax(dp[i+1][0], dp[i][0]); chmax(dp[i+1][1], dp[i][1]); // 倒す chmax(dp[i+1][1], dp[i][0]+a[i]); chmax(dp[i+1][0], dp[i][1]+a[i]*2); } cout << max(dp[n][0],dp[n][1]) << endl; return 0; }
E - Sightseeing Tour
複数テクニックが求められ実装が重かった。
まずワーシャルフロイドで全点対最短経路を求めておく。 Q 回のクエリでは、B の順列(k!)すべてで橋を渡すことを試す。その際、橋はどちら側からでも渡れるためすべての向きの方向を試す。
計算量が心配になるが( n3 + k! * 2k * q )、最大で 4003 + 5! * 25 * 3,000 = 75,520,000 程度のため制限時間には間に合う。
#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(); struct Bridge { int e1,e2; ll cost; }; int main() { int n,m; cin >> n >> m; vector dp(n, vector<ll>(n,1e18)); REP(i,n) dp[i][i] = 0; vector<Bridge> bridges; REP(i,m) { int u,v; ll t; cin >> u >> v >> t; u--; v--; dp[u][v] = min(dp[u][v],t); dp[v][u] = min(dp[v][u],t); bridges.emplace_back(u,v,t); } // ワーシャルフロイド REP(k,n) REP(i,n) REP(j,n) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); int q; cin >> q; REP(_,q) { int k; cin >> k; vector<int> x(k); REP(i,k) { cin >> x[i]; x[i]--; } ll ans = LINF; vector<int> b(k); iota(b.begin(),b.end(),0); do { auto dfs = [&](auto self, int i, int now, ll tot) { if (i == k) return tot + dp[now][n-1]; auto [e1,e2,cost] = bridges[x[b[i]]]; return min( self(self, i+1, e1, tot+dp[now][e2] + cost), self(self, i+1, e2, tot+dp[now][e1] + cost) ); }; ans = min(ans,dfs(dfs,0,0,0)); } while (next_permutation(b.begin(), b.end())); cout << ans << endl; } return 0; }
雑感
やっと水色復帰が見えてくるところまできた。嬉しい。
tic40さんのAtCoder Beginner Contest 369での成績:1583位 パフォーマンス:1359相当 レーティング:1163→1184 (+21) :) #AtCoder #ABC369 https://atcoder.jp/users/tic40/history/share/abc369?lang=ja