AtCoder abc352 参加メモ

B - Typing

s の何文字目まで進んだかを記録しながら t を全探索する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  string s,t; cin >> s >> t;
  int n = s.size();
  int now = 0;
  REP(i,(int)t.size()) {
    if (now < n && s[now] == t[i]) { cout << i+1 << " "; now++; }
  }
  return 0;
}

C - Standing On The Shoulders

(頭 - 肩) の差が最も大きい巨人を一番上になるようにすれば最大

#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;
using P = pair<int,int>;

int main() {
  int n; cin >> n;
  vector<int> a(n),b(n);
  REP(i,n) cin >> a[i] >> b[i];
  vector<P> pa;
  REP(i,n) pa.emplace_back(b[i]-a[i],i);

  sort(pa.begin(),pa.end());
  ll ans += b[pa.back().second];
  REP(i,n-1) ans += a[pa[i].second];
  cout << ans << endl;
  return 0;
}

D - Permutation Subsequence

各番号が現れる index を記録しておき、segtree の range max, range min で i, i+k-1 の max - min の差が最小のものが答え。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
const int INF = numeric_limits<int>::max();

int op1(int a, int b) { return max(a, b); }
int e1() { return 0; }
int op2(int a, int b) { return min(a, b); }
int e2() { return INF; }

int main() {
  int n,k; cin >> n >> k;
  segtree<int, op1, e1> seg_max(n);
  segtree<int, op2, e2> seg_min(n);
  REP(i,n) {
    int p; cin >> p; p--;
    seg_max.set(p,i);
    seg_min.set(p,i);
  }

  int ans = INF;
  REP(i,n-k+1) {
    int l = i, r = i+k-1;
    int mx = seg_max.prod(l,r+1);
    int mi = seg_min.prod(l,r+1);
    ans = min(ans,mx-mi);
  }
  cout << ans << endl;
  return 0;
}

E - Clique Connect

辺の数が O(N²) となるため、すべての辺をチェックすることはできない。全域木を作るうえで u < v のすべての辺を調べる必要はなく、一番小さい値の頂点から、各頂点への辺だけを調べれば良い。例えば a = { 1, 2, 3, 4, 5 } のときは、1->2, 1->3, 1->4, 1->5 の辺だけで十分。

あとはコストの低いい辺からクラスカル法で全域木を作っていけばいい。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;
using P = pair<int,int>;

int main() {
  int n,m; cin >> n >> m;
  vector g(n,vector<int>());
  vector<P> pa(m);
  vector a(m,vector<int>());
  REP(i,m) {
    int c,k; cin >> k >> c;
    pa[i] = {c,i};
    REP(j,k) {
      int x; cin >> x; x--;
      a[i].push_back(x);
    }
  }

  sort(pa.begin(),pa.end());
  dsu d(n);
  ll ans = 0;
  for(auto [cost,i]: pa) for(auto to: a[i]) {
    int from = a[i][0];
    if (d.same(from,to)) continue;
    d.merge(from,to);
    ans += cost;
  }

  cout << (d.size(0) == n ? ans : -1) << endl;
  return 0;
}

雑感

解く速度が遅すぎた。 D は問題読解に時間がかかりすぎ。E は TLE が痛かった。

tic40さんのAtCoder Beginner Contest 352での成績：2415位
パフォーマンス：1142相当
レーティング：1041→1051 (+10) :)
#AtCoder #ABC352 https://atcoder.jp/users/tic40/history/share/abc352?lang=ja