AtCoder abc346 参加メモ

UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346) - AtCoder

B - Piano

w, b の制約が 100 以下のため十分な長さの s を用意しておいて全探索する

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

const string t = "wbwbwwbwbwbw";

int main() {
  int w,b; cin >> w >> b;
  string s;
  REP(i,100) s += t;
  REP(i,12) {
    int cw = 0, cb = 0;
    int j = i;
    while(1) {
      if (cw == w && cb == b) { cout << "Yes" << endl; return 0; }
      if (cw > w || cb > b) break;
      if (s[j] == 'w') cw++;
      if (s[j] == 'b') cb++;
      j++;
    }
  }
  cout << "No" << endl;
  return 0;
}

C - Σ

1 〜 k までの等差数列の和を最初に求めておいて、a の数列から k 以下の値のうち、重複を取り除いたものを引く

#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,k; cin >> n >> k;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  ll ans = (ll)(1+k)*k/2;
  unordered_set<int> st;
  REP(i,n) if (a[i] <= k) st.insert(a[i]);
  for(auto v: st) ans -= v;
  cout << ans << endl;
  return 0;
}

D - Gomamayo Sequence

以下のような 3次元の DP で遷移

dp[i][j][k]
- i: 何文字目までみたか
- j: 良い文字列フラグ
- k: 最後の文字 0 or 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 chmin(T& a, T b) { a = min(a,b); }

int main() {
  int n; cin >> n;
  string s; cin >> s;
  vector<int> c(n);
  REP(i,n) cin >> c[i];
  vector<int> si(n);
  REP(i,n) si[i] = s[i]-'0';

  // dp[i][j][k]
  // i: 何文字目までみたか
  // j: 良い文字列フラグ
  // k: 最後の文字 0 or 1
  vector dp(n+1,vector(2,vector<ll>(2,LINF)));
  dp[1][0][si[0]] = 0;
  dp[1][0][si[0]^1] = c[0];

  auto f = [&](int i, int j, int k, int now, int cost) {
    if (now == k && j == 0) chmin(dp[i+1][1][now], dp[i][j][k] + cost);
    if (now != k) chmin(dp[i+1][j][now], dp[i][j][k] + cost);
  };

  for(int i = 1; i < n; i++) REP(j,2) REP(k,2) {
    if (dp[i][j][k] == LINF) continue;
    f(i,j,k,si[i],0); // 操作しない
    f(i,j,k,si[i]^1,c[i]); // 操作する
  }

  ll ans = min(dp[n][1][0], dp[n][1][1]);
  cout << ans << endl;
  return 0;
}

E - Paint

最後に操作したものは確定となるので、操作を後ろから見ていく

#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 h,w,m; cin >> h >> w >> m;
  vector<tuple<int,int,int>> tp(m);
  REP(i,m) {
    int t,a,x; cin >> t >> a >> x;
    t--; a--;
    tp[i] = {t,a,x};
  }
  const int mx = 2e5;
  const ll tot = (ll)h*w;

  vector<ll> col(mx+1);
  vector used(2,vector<int>(mx+1));
  // 操作を後ろから見ていく
  reverse(tp.begin(),tp.end());
  for(auto [t,a,x]: tp) {
    if (used[t][a]) continue;
    used[t][a] = 1;

    if (t == 0) { col[x] += w; h--; }
    else { col[x] += h; w--; }
  }

  ll sum = accumulate(col.begin(),col.end(),0LL);
  col[0] += tot - sum; // 初期の色0分を足す
  vector<pair<int,ll>> ans;
  REP(i,mx+1) if (col[i] > 0) ans.emplace_back(i,col[i]);

  cout << ans.size() << endl;
  for(auto [k,v]: ans) cout << k << " " << v << endl;
  return 0;
}