AtCoder abc271 参加メモ

KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271） - AtCoder

B - Maintain Multiple Sequences

• 隣接リストで持つ

#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,q; cin >> n >> q;
  vector<vector<int>> g(n);
  REP(i,n) {
    int l; cin >> l;
    REP(j,l) {
      int x; cin >> x;
      g[i].push_back(x);
    }
  }

  REP(i,q) {
    int s,t; cin >> s >> t;
    s--; t--;
    cout << g[s][t] << endl;
  }
  return 0;
}

C - Manga

• シミュレーションで解けるが実装がごちゃつく
• こちらの 解説 のように二分探索を使うと楽だった

[シミュレーション解]

#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> a(n);
  set<int> st;
  REP(i,n) {
    cin >> a[i];
    st.insert(a[i]);
  }

  int dup = n - st.size();
  vector<int> b;
  for(int v: st) b.push_back(v);

  int ans = 0, now = 0;
  int bsz = b.size();

  for(int i = 1; i <= n; i++) {
    if (now < bsz && b[now] == i) {
      now++;
    } else {
      int need = 2;
      need -= min(2,dup);
      dup -= min(2,dup);
      bsz -= need;
      if (now > bsz) break;
    }
    ans++;
  }

  ans += dup/2;
  cout << ans << endl;
  return 0;
}

[二分探索解]

#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> a(n);
  set<int> st;
  REP(i,n) {
    cin >> a[i];
    st.insert(a[i]);
  }

  int ok = 0, ng = n+1;
  while(abs(ok-ng) > 1) {
    int mid = (ok+ng)/2; // mid巻まで読めるかどうか
    int sell = n - st.size();
    sell += distance(st.upper_bound(mid), st.end());

    for(int i = 1; i <= mid; i++) {
      if (st.count(i) == 0) sell -= 2;
    }
    if (sell >= 0) ok = mid;
    else ng = mid;
  }

  cout << ok << endl;
  return 0;
}

D - Flip and Adjust

• DP経路復元

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

vector<int> a(100),b(100);
vector dp(101, vector<bool>(10001));
string ans;

void dfs(int i, int now, string str) {
  if (ans.size()) return;
  if (i == 0) {
    if (now == 0) ans = str;
    return;
  }

  int na = now - a[i-1];
  int nb = now - b[i-1];
  if (na >= 0 && dp[i-1][na]) dfs(i-1, na, "H" + str);
  if (nb >= 0 && dp[i-1][nb]) dfs(i-1, nb, "T" + str);
  return;
}

int main() {
  int n,s; cin >> n >> s;
  REP(i,n) cin >> a[i] >> b[i];

  dp[0][0] = true;
  REP(i,n) REP(j,s+1) {
    if (j - a[i] >= 0) dp[i+1][j] = dp[i+1][j] || dp[i][j - a[i]];
    if (j - b[i] >= 0) dp[i+1][j] = dp[i+1][j] || dp[i][j - b[i]];
  }

  if (dp[n][s]) {
    cout << "Yes" << endl;
    dfs(n, s, ""); // 経路復元
    cout << ans << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}