AtCoder abc397 参加記

OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397) - AtCoder

A - Thermometer

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

int main() {
  double n; cin >> n;
  int ans = 1;
  if (n < 38.0) ans++;
  if (n < 37.5) ans++;
  cout << ans << endl;
  return 0;
}

B - Ticket Gate Log

#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; cin >> s;
  int n = s.size(), ans = 0;
  REP(i,n) {
    int now = i+ans;
    char c = now % 2 == 0 ? 'i' : 'o';
    if (s[i] != c) { ans++; i--; }
  }
  ans += (n+ans)%2;
  cout << ans << endl;
  return 0;
}

C - Variety Split Easy

左右からそれぞれの地点での種類数を求めておけば、地点 i で区切ったときの種類数の合計は、[左からみたときの地点 i までの種類数] + [右から見たときの地点 i+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 n; cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  auto f = [&]() {
    unordered_set<int> st;
    vector<int> res(n);
    REP(i,n) {
      st.insert(a[i]);
      res[i] = st.size();
    }
    return res;
  };

  auto l = f();
  reverse(a.begin(),a.end());
  auto r = f();
  reverse(r.begin(),r.end());

  int ans = 0;
  REP(i,n-1) ans = max(ans,l[i]+r[i+1]);
  cout << ans << endl;
  return 0;
}

D - Cubes

解けず。

E - Path Decomposition of a Tree

頂点 0 を木の根とし(どこが根でも良い)DFSで順に見ていく。 DFS の返り値を、部分木のまだ分解していない頂点数の合計とする。不可能な場合は -1 を返す。

現在みている頂点分 + その頂点の部分木でまだ分解していない頂点数 = k のとき分解可能。 ただし、部分木の数が 3 以上のときは不可能。2 のときは

#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,k; cin >> n >> k;
  int nk = n*k;
  vector g(nk,vector<int>());
  REP(i,nk-1) {
    int u,v; cin >> u >> v; u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  // DFS: まだ分解していない頂点 i の部分木のパスの長さを返す
  auto dfs = [&](auto& dfs, int i, int p) -> int {
    int len = 1, cnt = 0;
    for(auto v: g[i]) if (v!=p) {
      int res = dfs(dfs,v,i);
      if (res == -1) return -1;
      if (res > 0) { len+=res; cnt++; }
    }

    if (cnt <= 1) return len == k ? 0 : len;
    if (cnt == 2) return len == k ? 0 : -1;
    return -1;
  };

  cout << (dfs(dfs,0,-1) == 0 ? "Yes" : "No") << endl;
  return 0;
}

tic40さんのオムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）での成績：1494位
パフォーマンス：1391相当
レーティング：1286→1297 (+11) :)
#AtCoder #オムロンプログラミングコンテスト2025（ABC397） https://atcoder.jp/users/tic40/history/share/abc397?lang=ja 

AtCoder abc396 参加記

AtCoder Beginner Contest 396 - AtCoder

A - Triple Four

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

int main() {
  int n; cin >> n;
  vector<int> a(n);
  int ok = 0;
  REP(i,n) cin >> a[i];
  REP(i,n-2) ok |= (a[i] == a[i+1] && a[i] == a[i+2]);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

B - Card Pile

後入先出(LIFO) で管理すればよいので stack でカードの山を管理する

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

int main() {
  int q; cin >> q;
  vector<int> d(100);
  REP(i,q) {
    int t; cin >> t;
    if (t == 1) { int x; cin >> x; d.push_back(x); }
    if (t == 2) { cout << d.back() << endl; d.pop_back(); }
  }
  return 0;
}

C - Buy Balls

黒色のボールの個数を固定したときに、白色のボールをどれだけ取るといいかを考える。 価値の大きいボールから順に取るのが最良のため、価値の大きいものから順に取っていく。 白色は黒色の個数以下で、価値が正のものを取れるだけ取ればいい

#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,m; cin >> n >> m;
  vector<int> b(n),w(m);
  REP(i,n) cin >> b[i];
  REP(i,m) cin >> w[i];
  REP(i,n-m) w.push_back(0);
  sort(b.rbegin(),b.rend());
  sort(w.rbegin(),w.rend());

  ll ans = 0, now = 0;
  REP(i,n) {
    now += b[i] + max(0,w[i]);
    ans = max(ans,now);
  }
  cout << ans << endl;
  return 0;
}

D - Minimum XOR Path

N <= 10 と小さいことから、1からNまでのパスを全探索できる

#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,ll>;
const ll LINF = numeric_limits<ll>::max();

int main() {
  int n,m; cin >> n >> m;
  vector g(n,vector<P>());
  REP(i,m) {
    int u,v; ll w; cin >> u >> v >> w; u--; v--;
    g[u].emplace_back(v,w);
    g[v].emplace_back(u,w);
  }

  vector<bool> visited(n);
  auto dfs = [&](auto& dfs, int i, ll cur) -> ll {
    if (i == n-1) return cur;

    ll res = LINF;
    for(auto [ni,w]: g[i]) if (!visited[ni]) {
      visited[ni] = true;
      res = min(res,dfs(dfs,ni,cur^w));
      visited[ni] = false;
    }
    return res;
  };

  visited[0] = true;
  cout << dfs(dfs,0,0) << endl;
  return 0;
}

E - Min of Restricted Sum

頂点 Xi, Yi を Zi 値を持つ辺で結ぶグラフとして考える。 スタートする点の値を 0 として、連結成分ごとに BFS で Axi ^ Ayi = Zi に矛盾がないかを調べる。 矛盾がなければ総和が最小となる数を見つける。これは各ビットごとに見ていき、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;

int main() {
  int n,m; cin >> n >> m;
  vector g(n,vector<pair<int,int>>());
  REP(i,m) {
    int x,y,z; cin >> x >> y >> z; x--; y--;
    g[x].emplace_back(y,z);
    g[y].emplace_back(x,z);
  }

  vector<ll> ans(n);
  vector<bool> visited(n);
  auto bfs = [&](int start) -> bool {
    queue<int> q;
    vector<int> comp;

    auto push = [&](int v) {
      q.push(v);
      comp.push_back(v);
      visited[v] = true;
    };

    push(start);
    while(q.size()) {
      int from = q.front(); q.pop();
      for (auto [to,z]: g[from]) {
        if (visited[to]) {
          if ((ans[from] ^ ans[to]) != z) return false;
        } else {
          ans[to] = ans[from] ^ z;
          push(to);
        }
      }
    }

    ll t = 0;
    REP(bit,31) {
      int one = 0;
      for (auto v: comp) one += (ans[v] >> bit) & 1;
      if (one > (int)comp.size() - one) t |= (1LL << bit);
    }
    for (auto v: comp) ans[v] ^= t;
    return true;
  };

  REP(i,n) if (!visited[i] && !bfs(i)) { cout << -1 << endl; return 0; }
  for(auto v: ans) cout << v << " ";
  return 0;
}

F - Rotated Inversions

まず BIT で k = 0 のときの転倒数を求めておく。 転倒数に変化が起こるのは、 (a[i] + k) % m == 0 となるときのみなので、差分を計算できないか考える。 (a[i] + k) % m == 0 となるときに寄与する転倒数は、増える分が i, 減る分が n-i-1 なのでこれをイベントとして持っておく。 あとは k = 1 から k = m-1 までに発生するイベントを処理しながら答えを求めていけばよい。

#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;

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  vector<ll> ans(m);
  fenwick_tree<int> fw(m);
  // k = 0 のときの転倒数を fenwich tree で求める
  REP(i,n) {
    ans[0] += i - fw.sum(0,a[i]+1);
    fw.add(a[i],1);
  }

  vector events(m,vector<ll>());
  REP(i,n) if (a[i] > 0) {
    // m-1 -> m となるとき(時刻t = m-a[i])に転倒数にどれだけ寄与するか
    // 増える転倒数 i
    // 減る転倒数 n-i-1
    events[m-a[i]].push_back(i-(n-i-1));
  }

  ll now = ans[0];
  for (int k = 1; k < m; k++){
    for (auto v : events[k]) now += v;
    ans[k] = now;
  }
  for(auto v: ans) cout << v << endl;
  return 0;
}

雑感

辛い戦いだ...

tic40さんのAtCoder Beginner Contest 396での成績：950位
パフォーマンス：1591相当
レーティング：1247→1286 (+39) :)
#AtCoder #ABC396 https://atcoder.jp/users/tic40/history/share/abc396?lang=ja 

Ghostty で != や <= が合字表示になる挙動を無効化したい

ターミナルソフトを iterm2 から Ghostty へ移行した。 快適な挙動で満足している、が一つ気に入らない点があった。

!= などの記号が合字表示される挙動がある。

合字はあまり聞き慣れない言葉だが英語では Ligature と言い複数文字を合成して1文字にすることを指す

合字 - Wikipedia

例えば vim で以下のように入力をすると

a != b
a <= b
a === b

表示は以下の画像のように合字になる。

合字表示を無効化するには config に以下を追加すればよい

font-feature = -dlig,-liga,-calt

しばらく不満ながら使っていたがリファレンスにしっかり記載があった。よく読みましょう。 https://ghostty.org/docs/config/reference#font-feature

私の config 設定 dotfiles/ghostty/config at main · tic40/dotfiles · GitHub

AtCoder abc384 参加記

Toyota Programming Contest 2024#12（AtCoder Beginner Contest 384） - AtCoder

A - aaaadaa

#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; char c1,c2; string s;
  cin >> n >> c1 >> c2 >> s;
  for(auto c: s) cout << (c == c1 ? c : c2);
  return 0;
}

B - ARC Division

#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,r; cin >> n >> r;
  REP(i,n) {
    int d,a; cin >> d >> a;
    if (d==1 && r >= 1600 && r <= 2799) r+=a;
    if (d==2 && r >= 1200 && r <= 2399) r+=a;
  }
  cout << r << endl;
  return 0;
}

C - Perfect Standings

bit 全探索ですべてのケースを列挙してソートする。 スコアの降順、文字列の昇順だが、スコアを負に反転しておけば昇順ソートするだけ良くなる

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

int main() {
  const int n = 5;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  vector<pair<int,string>> ans;
  REP(bit,1<<n) {
    int score = 0;
    string s;
    REP(i,n) if (bit >> i & 1) {
      score += a[i];
      s += char('A'+i);
    }
    ans.emplace_back(-score,s);
  }
  sort(ans.begin(),ans.end());
  for(auto [_,s]: ans) if (s.size()) cout << s << endl;
  return 0;
}

D - Repeated Sequence

• s は 数列aの合計数の剰余にしていい
• 累積和を数列aの2倍の長さ分取っておく
• a[i] からスタートしたときにちょうど s になる位置があるか累積和から二分探索で求める

#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; ll s; cin >> n >> s;
  vector<int> a(n);
  REP(i,n) cin >> a[i];
  vector<ll> sum(n*2+1);
  REP(i,n*2) sum[i+1] = sum[i] + a[i%n];

  s %= accumulate(a.begin(),a.end(),0LL);
  int ok = 0;
  REP(i,n) ok |= binary_search(sum.begin(),sum.end(),sum[i]+s);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

E - Takahashi is Slime 2

優先度付きキューで強さの小さい順に、隣接しているまだ取り込んでいないスライムを管理する。 新しくスライムを吸収したときには、そのスライムのマスに隣接しているまだ取り込んでいないスライムをキューに追加していく。

#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 T = pair<ll,pair<int,int>>;
const vector<int> di = {-1,0,1,0};
const vector<int> dj = {0,1,0,-1};

int main() {
  int h,w,x; cin >> h >> w >> x;
  int p,q; cin >> p >> q; p--; q--;
  vector s(h,vector<ll>(w));
  REP(i,h) REP(j,w) cin >> s[i][j];

  priority_queue<T, vector<T>, greater<T>> pq;
  vector visited(h,vector<int>(w));

  ll power = 0;
  auto push = [&](int i, int j) -> void {
    visited[i][j] = 1;
    power += s[i][j];
    REP(k,4) {
      int ni = i+di[k], nj = j+dj[k];
      if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
      if (visited[ni][nj]) continue;
      pq.emplace(s[ni][nj], P{ni,nj});
    }
  };
  push(p,q);

  while(pq.size()) {
    auto [_, pos] = pq.top(); pq.pop();
    auto [i,j] = pos;
    if (visited[i][j]) continue;
    if ((double)s[i][j] >= (double)power/x) continue;
    push(i,j);
  }
  cout << power << endl;
  return 0;
}

雑感

E は最初 set で隣接の未吸収スライムマスだけを管理する方針で実装した。Nが小さいのでいけそうに思ったがTLEで通らず。優先度付きキューに実装し直しでタイムロス。 F は最近よく見る二重 Σ の計算量をなんとかする問題。相変わらずこういうのは苦手。

あとタイトルの「参加メモ」というのは変に思えてきたので今回から「参加記」に変更した。

tic40さんのトヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384）での成績：2526位
パフォーマンス：1058相当
レーティング：1322→1298 (-24) :(
#AtCoder #トヨタ自動車プログラミングコンテスト2024#12（ABC384） https://atcoder.jp/users/tic40/history/share/abc384?lang=ja 

AtCoder abc382 参加メモ

AtCoder Beginner Contest 382 - AtCoder

A - Daily Cookie

#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,d; string s; cin >> n >> d >> s;
  for(auto c: s) if (c == '@') n--;
  cout << n+d << endl;
  return 0;
}

B - Daily Cookie 2

#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,d; string s; cin >> n >> d >> s;
  for(int i = n-1; i >= 0; i--) if (d && s[i] == '@') s[i] = '.', d--;
  cout << s << endl;
  return 0;
}

C - Kaiten Sushi

寿司はどの順番で流しても結果に変わりはない。

寿司の美味しさの降順に処理することにすれば、美味しさが大きいものは先頭から取っていくので、a[cur] 以降の人だけをチェックしていくだけで良くなる。

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

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(n),b(m);
  REP(i,n) cin >> a[i];
  REP(i,m) cin >> b[i];
  vector<P> pb;
  REP(i,m) pb.emplace_back(b[i],i);
  sort(pb.rbegin(),pb.rend());

  vector<int> ans(m,-1);
  int cur = 0;
  REP(i,m) {
    while(cur < n) {
      if (a[cur] <= pb[i].first) {
        ans[pb[i].second] = cur+1;
        break;
      }
      cur++;
    }
  }
  for(auto v: ans) cout << v << endl;
  return 0;
}

D - Keep Distance

DFS がうまく書けますかという問題。DFS の計算量怪しいなと思いつつも i <= m で投げて TLE を出してしまった。 達成不可能な数列をちゃんと枝刈りすれば間に合った。

#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,m; cin >> n >> m;
  vector<int> a;
  vector<vector<int>> ans;

  auto dfs = [&](auto dfs) -> void {
    int sz = a.size();
    if (sz == n) { ans.push_back(a); return; }

    for(int i = sz ? a.back()+10 : 1; i <= m-(10*(n-1-sz)); i++) {
      a.push_back(i);
      dfs(dfs);
      a.pop_back();
    }
  };

  dfs(dfs);
  cout << ans.size() << endl;
  for(auto v: ans) {
    for(auto w: v) cout << w << " ";
    cout << endl;
  }
  return 0;
}

E - Expansion Packs

期待値問題。難しい。

#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,x; cin >> n >> x;
  vector<double> p(n);
  REP(i,n) cin >> p[i], p[i] /= 100.0;

  // dp[i][j] := パック内の i 枚目まででレアカードを j 枚持つ確率
  vector<double> dp(n+1);
  dp[0] = 1.0; // レアカード 0 枚は 100 %
  REP(i,n) {
    vector<double> prev(n+1);
    swap(dp,prev);
    REP(j,i+1) {
      dp[j] += prev[j] * (1.0 - p[i]); // レアカードが出ない
      dp[j+1] += prev[j] * p[i]; // レアカードが出る
    }
  }

  // f[i] := レアカードが x 枚になるまで必要なパック数の期待値
  vector<double> f(x+1);
  for(int i = 1; i <= x; i++) {
    double sum = 0.0;
    for(int j = 1; j <= min(i-1,n); j++) sum += dp[j] * f[i-j];
    sum += 1.0;
    // f[i] = dp[0] * f[i] + sum
    // f[i] = sum / (1 - dp[0])
    f[i] = sum / (1.0 - dp[0]);
  }

  printf("%.10f\n", f[x]);
  return 0;
}

F - Falling Bars

hの大きい(下にある)バーから順に処理。 遅延セグ木で range 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'
using T = tuple<int,int,int>;
const int INF = numeric_limits<int>::max();

using S = int;
using F = int;
S op(S a, S b) { return min(a,b); }
S e() { return INF; }
S mapping(F f, S x) { return min(x,f); }
F composition(F f, F g) { return min(f,g); }
F id() { return INF; }

int main() {
  int h,w,n; cin >> h >> w >> n;
  vector bars(h,vector<T>());
  REP(i,n) {
    int r,c,l; cin >> r >> c >> l; r--; c--;
    bars[r].emplace_back(c,l,i);
  }

  lazy_segtree<S, op, e, F, mapping, composition, id> seg(w);
  seg.apply(0,w,h-1);
  vector<int> ans(n);
  for(int r = h-1; r >= 0; r--) {
    for(auto [c,l,id]: bars[r]) {
      int now = seg.prod(c,c+l);
      ans[id] = now;
      seg.apply(c,c+l,now-1);
    }
  }

  REP(i,n) cout << ans[i]+1 << endl;
  return 0;
}

雑感

hightest 更新！順位も過去最高だった。G は手も足も出ず。

tic40さんのAtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）での成績：325位
パフォーマンス：1911相当
レーティング：1233→1322 (+89) :)
Highestを更新しました！
#AtCoder #AtCoderプログラミングコンテスト2024（ABC382） https://atcoder.jp/users/tic40/history/share/abc382?lang=ja 

AtCoder abc376 参加メモ

AtCoder Beginner Contest 376 - AtCoder

A - Candy Button

最後に飴をもらった時刻を記憶しておく

#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,c; cin >> n >> c;
  int p = -1e4, ans = 0;
  REP(_,n) {
    int t; cin >> t;
    if (t-p >= c) { ans++; p = t; }
  }
  cout << ans << endl;
  return 0;
}

B - Hands on Ring (Easy)

愚直にシミュレーションしたが、B にしては実装が重かった。 L or R、左 or 右回りで場合分けがあり、これをそのまま書くと煩雑になってしまう。

• R を動かす場合は swap(l,r) をし、コード上は常に L を動かすだけにする
• 左 or 右回りは dir で動く方向を +1 or -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 n,q; cin >> n >> q;
  int l = 0, r = 1;
  auto f = [&](int dir, int pos, int t)  {
    int cost = 0;
    while(pos != t) {
      if (pos == r) { cost = 1e9; break; }
      cost++;
      pos = ((pos+dir) % n + n) % n;
    }
    return cost;
  };

  int ans = 0;
  REP(_,q) {
    char h; int t; cin >> h >> t; t--;
    if (h == 'R') swap(l,r);
    ans += min(f(1,l,t),f(-1,l,t));
    l = t;
    if (h == 'R') swap(l,r);
  }
  cout << ans << endl;
  return 0;
}

C - Prepare Another Box

追加する箱のサイズを二分探索で求めた。 おもちゃの入れ方は、一番小さいおもちゃから、一番小さい箱に貪欲に入れていくのが最適となる。

#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),b(n-1);
  REP(i,n) cin >> a[i];
  REP(i,n-1) cin >> b[i];
  sort(a.begin(),a.end());

  auto f = [&](int x) -> bool {
    auto c = b;
    c.push_back(x);
    sort(c.begin(),c.end());
    REP(i,n) if (a[i] > c[i]) return false;
    return true;
  };

  int ok = 1e9+5, ng = 0;
  while(ok-ng>1) {
    int mid = (ok+ng)/2;
    if (f(mid)) ok = mid;
    else ng = mid;
  }
  cout << (ok > 1e9 ? -1 : ok) << endl;
  return 0;
}

D - Cycle

頂点1 から BFS して頂点 1 に最短で戻る経路を探索する。 ED問題にしては？とくに捻りはなくBFSするだけだった。

#include <bits/stdc++.h>
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 main() {
  int n,m; cin >> n >> m;
  vector g(n,vector<int>());
  REP(i,m) {
    int a,b; cin >> a >> b; a--; b--;
    g[a].push_back(b);
  }

  vector<int> dist(n,INF);
  queue<int> q;
  q.push(0);
  dist[0] = 0;

  while(q.size()) {
    auto now = q.front(); q.pop();
    for(auto v: g[now]) {
      if (v == 0) { cout << dist[now]+1 << endl; return 0; }
      if (dist[v] <= dist[now]+1) continue;
      dist[v] = dist[now]+1;
      q.push(v);
    }
  }

  cout << -1 << endl;
  return 0;
}

E - Max × Sum

{a,b} のペアを昇順ソートして a が小さい値から順番に見ていく。 a は昇順に見ていけば今の a が常に最大の値となる。 Σb は、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;
using P = pair<int,int>;
const ll LINF = numeric_limits<ll>::max();

int main() {
  int t; cin >> t;
  REP(_,t) {
    int n,k; cin >> n >> k;
    vector<P> items(n);
    REP(i,n) cin >> items[i].first;
    REP(i,n) cin >> items[i].second;
    sort(items.begin(),items.end());

    priority_queue<int> pq;
    ll sumb = 0, ans = LINF;
    for(auto [a,b]: items) {
      pq.push(b);
      sumb += b;
      if ((int)pq.size() == k) {
        ans = min(ans,(ll)a * sumb);
        sumb -= pq.top(); pq.pop();
      }
    }
    cout << ans << endl;
  }
  return 0;
}

雑感

B 問題でかなり時間かけてしまい大焦り。 D 問題もスタートが頂点1 というのを見落として、全体で最小サイクルを探索するコードを書いてしまった。 F問題は場合分けを考えていたら頭がおかしくなってきたので諦め。

D 問題解いた時点ではかなり遅かったが、E が解けたおかげで Highest 更新。まだいつ緑に落ちてもおかしく水準なのでヒヤヒヤする。

tic40さんのAtCoder Beginner Contest 376（Promotion of AtCoder Career Design DAY）での成績：1469位
パフォーマンス：1409相当
レーティング：1214→1235 (+21) :)
Highestを更新しました！
#AtCoder #ABC376（PromotionofAtCoderCareerDesignDAY） https://atcoder.jp/users/tic40/history/share/abc376?lang=ja

AtCoder abc372 参加メモ

UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372) - AtCoder

A - delete .

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

int main() {
  string n; cin >> n;
  for(auto c: n) if (c != '.') cout << c;
  return 0;
}

B - 3^A

m を 3 進数に変換する

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

int main() {
  int m; cin >> m;
  vector<int> ans;
  for(int i = 0; m > 0; i++) {
    while(m%3 != 0) { m--; ans.push_back(i); }
    m /= 3;
  }
  cout << ans.size() << endl;
  for(auto v: ans) cout << v << " ";
}

C - Count ABC Again

最初にすべての ABC となる部分文字列を数え上げておき、各クエリでは、影響のある部分の差分を考える

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

int f(string& s, int idx) { return s.substr(idx,3) == "ABC"; }

int main() {
  int n,q; cin >> n >> q;
  string s; cin >> s;

  int ans = 0;
  REP(i,n-2) ans += f(s,i);

  REP(_,q) {
    int x; char c; cin >> x >> c; x--;
    for(int i = max(0,x-2); i <= x; i++) ans -= f(s,i);
    s[x] = c;
    for(int i = max(0,x-2); i <= x; i++) ans += f(s,i);

    cout << ans << endl;
  }
  return 0;
}

D - Buildings

難しい。 右端からスタートし、スタックで直近の数え上げ対象となるビルの情報を持っておくようにする。

#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> h(n);
  REP(i,n) cin >> h[i];

  vector<int> ans(n), st;
  for(int i = n-1; i >= 0; i--) {
    ans[i] = st.size();
    // 現在のビルが stack のトップより高い場合
    // stack のトップにあるビルは数え上げ対象にならないため pop する
    while(st.size() && h[st.back()] < h[i]) st.pop_back();
    st.push_back(i);
  }

  for(auto v: ans) cout << v << " ";
  return 0;
}

E - K-th Largest Connected Components

手持ちの UnionFind 構造体に頂点番号管理する処理を追加。 ac library 頼りだったので久々にライブラリを持ち出した。

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

struct UnionFind {
  vector<int> d;
  vector<set<int>> st;
  UnionFind(int n = 0): d(n,-1), st(n) {
    REP(i,n) st[i].insert(i);
  }
  int root(int x) {
    return d[x] < 0 ? x : d[x] = root(d[x]);
  }
  int unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return 0;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;

    st[x].insert(st[y].begin(),st[y].end());
    while(st[x].size() > 10) st[x].erase(st[x].begin());
    return 1;
  }
  int kth_largest(int u, int k) {
    u = root(u);
    if ((int)st[u].size() < k) return -1;
    auto it = st[u].rbegin();
    advance(it,k-1);
    return *it+1;
  }
};

int main() {
  int n,q; cin >> n >> q;
  UnionFind uf(n);
  REP(_,q) {
    int t,u,v; cin >> t >> u >> v;
    u--; v--;
    if (t == 1) uf.unite(u,v);
    if (t == 2) cout << uf.kth_largest(u,v+1) << endl;
  }
  return 0;
}

雑感

D 問題に詰まって大ブレーキ。典型問題なんだろうけど頭がこんがらがってしまった。

tic40さんのユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372）での成績：1935位
パフォーマンス：1212相当
レーティング：1184→1187 (+3) :)
#AtCoder #ユニークビジョンプログラミングコンテスト2024秋（ABC372） https://atcoder.jp/users/tic40/history/share/abc372?lang=ja