AtCoder abc340 参加メモ

KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340） - AtCoder

B - Append

問題文をそのまま実装

#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> v;
  while(q--) {
    int t,x; cin >> t >> x;
    if (t == 1) v.push_back(x);
    else cout << v[v.size() - x] << endl;
  }
  return 0;
}

C - Divide and Divide

メモ化DFS

#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() {
  ll n; cin >> n;
  map<ll,ll> memo;
  auto dfs = [&](auto self, ll x) -> ll {
    if (x < 2) { return 0LL; }
    if (memo.count(x)) return memo[x];
    return memo[x] = x + self(self, x/2) + self(self, (x+1)/2);
  };
  cout << dfs(dfs, n) << endl;
  return 0;
}

D - Super Takahashi Bros.

重み付き有向グラフにしてダイクストラ

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

struct Edge {
  int to, cost;
  Edge(int to, int cost): to(to), cost(cost) {}
};

int main() {
  int n; cin >> n;
  vector g(n,vector<Edge>());
  REP(i,n-1) {
    int a,b,x; cin >> a >> b >> x;
    x--;
    g[i].emplace_back(i+1,a);
    g[i].emplace_back(x,b);
  }

  vector<ll> dist(n,LINF);
  priority_queue<P, vector<P>, greater<P>> q;
  auto push = [&](ll cost, int to) {
    if (dist[to] <= cost) return;
    dist[to] = cost;
    q.emplace(dist[to], to);
  };

  push(0,0);
  while (q.size()) {
    auto [cost,v] = q.top(); q.pop();
    if (dist[v] != cost) continue;
    for (Edge e: g[v]) push(dist[v]+e.cost, e.to);
  }

  cout << dist[n-1] << endl;
  return 0;
}

E - Mancala 2

周期を考えて累積和する。累積和を毎回集計するため Fenwick Tree で高速化した

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

  fenwick_tree<ll> fw(n+1); // 累積和
  REP(i,m) {
    ll t = fw.sum(0,b[i]+1);
    ll now = a[b[i]] + t;
    ll r = now / n; // 何周するか
    ll rem = now % n; // r周した余り分

    a[b[i]] = 0;
    fw.add(b[i],-t);
    fw.add(b[i]+1,t);
    fw.add(0,r);

    if (b[i] + rem < n) {
      fw.add(b[i]+1,1);
      fw.add(b[i]+rem+1,-1);
    } else {
      fw.add(b[i]+1,1);
      fw.add(0,1);
      fw.add((rem+b[i])%n+1, -1);
    }
  }

  REP(i,n) cout << (ll)a[i] + fw.sum(0,i+1) << " ";
  return 0;
}

今回はここまで