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