AtCoder abc349 参加メモ

Tasks - AtCoder Beginner Contest 349

B - Commencement

英小文字の出現回数を数える。その出現回数毎の回数を数えて、すべて 0 または 2 回であれば Yes

#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;
  vector<int> cnt1(26);
  for(auto c: s) cnt1[c-'a']++;
  vector<int> cnt2(101);
  REP(i,26) cnt2[cnt1[i]]++;

  int ok = 1;
  for(int i = 1; i <= 100; i++) ok &= (cnt2[i] == 0 || cnt2[i] == 2);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

C - Airport Code

S の先頭から T の文字とマッチするものがあるか貪欲に調べていけばよい。文字数が足りない場合は末尾に X を足して、T とマッチすれば Yes

#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;
  REP(i,3) t[i] = tolower(t[i]);

  int now = 0;
  string ns = "";
  for(auto c: s) if (c == t[now]) { now++; ns += c; }

  if (ns.size() == 2) ns += 'x';
  cout << (ns == t ? "Yes" : "No") << endl;
  return 0;
}

D - Divide Interval

L の値からシミュレーションする。 - 奇数の場合は 2⁰ * L, 2⁰ * (L+1) しかあり得ない - 偶数の場合は、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 P = pair<ll,ll>;

int main() {
  ll l,r; cin >> l >> r;
  vector<P> ans;
  while(l < r) {
    if (l%2) {
      ans.emplace_back(l,l+1);
      l = l+1;
    } else {
      for(ll i = 60; i >= 0; i--) {
        ll p = 1LL<<i;
        if (l % p) continue;
        ll nl = p * (l / p + 1);
        if (nl > r) continue;

        ans.emplace_back(l,nl);
        l = nl;
        break;
      }
    }
  }

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

E - Weighted Tic-Tac-Toe

お互い利益が最大になるように動く必要がある。こういうときはミニマックス法が使える。 ミニマックス法 - Wikipedia

#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 = 1e18;

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

  // used[i][j] := takahashi が置いたときは 1, aoki が置いたときは -1
  vector used(3,vector<int>(3));
  // マス{i,j}にターン t が置いたとき、タテ・ヨコ・ナナメいずれかが揃って勝てるか？
  auto win = [&](int i, int j, int t) {
    int res = 0, s = 3*t;
    used[i][j] = t;
    REP(i,3) res |= used[i][0] + used[i][1] + used[i][2] == s;
    REP(j,3) res |= used[0][j] + used[1][j] + used[2][j] == s;
    res |= used[0][0] + used[1][1] + used[2][2] == s;
    res |= used[0][2] + used[1][1] + used[2][0] == s;
    used[i][j] = 0;

    return res;
  };

  auto dfs = [&](auto self, int cnt, ll score) -> ll {
    if (cnt == 9) return score;
    // takahashi のターンは 1, aoki のターンは -1
    int t = cnt % 2 ? -1 : 1;

    ll res = -t*LINF;
    REP(i,3) REP(j,3) {
      if (used[i][j] != 0) continue; // 既に使われている
      if (win(i,j,t)) return t*LINF; // 3マス揃って勝てる場合

      used[i][j] = t;
      res = (t == 1) ?
        max(res,self(self,cnt+1,score+a[i][j]))
        : min(res,self(self,cnt+1,score-a[i][j]));
      used[i][j] = 0;
    }
    return res;
  };

  ll ans = dfs(dfs,0,0);
  cout << (ans > 0 ? "Takahashi" : "Aoki") << endl;
  return 0;
}

AtCoder abc348 参加メモ

Tasks - Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）

B - Farthest Point

max 値とその index を管理しながら全探索する

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

  REP(i,n) {
    P mx = {-1,-1};
    REP(j,n) {
      int dx = x[i]-x[j], dy = y[i]-y[j];
      int now = dx*dx+dy*dy;
      if (now > mx.first) mx = {now,j};
    }
    cout << mx.second+1 << endl;
  }
  return 0;
}

C - Colorful Beans

問題文がやや難解に思えた。 ビーンズの色が最大 10⁹ と大きいため、map で色毎のおいしさの最小値を持って、その中から最大のおいしさの値が答え

#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;
  unordered_map<int,int> mp;
  REP(i,n) {
    int a,c; cin >> a >> c; c--;
    mp[c] = mp.find(c) == mp.end() ? a : min(mp[c],a);
  }
  int ans = -1;
  for(auto [k,v]: mp) ans = max(ans,v);
  cout << ans << endl;
  return 0;
}

D - Medicines on Grid

迷路探索。実際に嵌ったポイントが２つあった。

一度通った道をもう一度通ることがあるか

最短経路ではなく寄り道して薬を取得するのが最適なケースもあるため、一度通った道を通ることはある

薬をどのように使うか

よく考えると薬は今のエネルギーより大きくなる場合、必ず使うのが最適であり薬を使うかどうかの分岐は必要ないことがわかる。

優先度付きキューで最大のエネルギー値の頂点から BFS すると高速に解けた。

#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>;
using P2 = pair<int,P>;
const vector<P> moves = { {-1,0},{0,1},{1,0},{0,-1} };

int main() {
  int h,w; cin >> h >> w;
  vector<string> a(h);
  REP(i,h) cin >> a[i];
  int n; cin >> n;
  vector item(h,vector<int>(w));
  REP(i,n) {
    int r,c,e; cin >> r >> c >> e;
    r--; c--;
    item[r][c] = e;
  }

  auto bfs = [&]() {
    vector dist(h,vector<int>(w,-1));
    // エネルギー値の降順に取り出すキュー
    // P2 := { エネルギー, 位置(i,j) }
    priority_queue<P2, vector<P2>, less<P2>> q;
    // スタート地点をキューへ
    REP(i,h) REP(j,w) if (a[i][j] == 'S') q.emplace(0,P(i,j));

    while(q.size()) {
      auto [e,pa] = q.top(); q.pop();
      auto [i,j] = pa;
      if (a[i][j] == 'T') return true; // goal

      // アイテムは貪欲に使って良い
      e = max(e,item[i][j]);
      if (e <= 0 || dist[i][j] >= e) continue;
      dist[i][j] = e;
      for(auto [di,dj]: moves) {
        int ni = i+di, nj = j+dj;
        if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
        if (a[ni][nj] == '#') continue;
        q.emplace(e-1,P(ni,nj));
      }
    }
    return false;
  };

  cout << (bfs() ? "Yes" : "No") << endl;
  return 0;
}

雑感

D問題で DFS で薬の分岐まで考慮して何度も WA を出してしまった。計算量をぱっと見積もれないのは良くない。

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

AtCoder abc343 参加メモ

AtCoder Beginner Contest 343 - AtCoder

B - Adjacency Matrix

隣接行列を隣接リストにする

#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 g(n,vector<int>());
  REP(i,n) REP(j,n) {
    int a; cin >> a;
    if (a == 1) g[i].push_back(j+1);
  }
  REP(i,n) {
    for(auto v: g[i]) cout << v << " ";
    cout << endl;
  }
  return 0;
}

C - 343

全探索する。数字を文字列に変換して回文判定。

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

bool is_palindrome(string s) {
  string t = s;
  reverse(t.begin(),t.end());
  return t == s;
}

int main() {
  ll n, ans = 0; cin >> n;
  REP(i,1e6+1) {
    ll x = (ll)i*i*i;
    if (x > n) break;
    if (is_palindrome(to_string(x))) { ans = x; }
  }
  cout << ans << endl;
  return 0;
}

D - Diversity of Scores

map で現在の点数の種類数を管理する

#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,t; cin >> n >> t;
  vector<ll> m(n);
  map<ll,int> mp;
  mp[0] = n;

  REP(_,t) {
    int a,b; cin >> a >> b; a--;
    ll before = m[a], after = m[a]+b;
    mp[before]--; mp[after]++;
    if (mp[before] == 0) mp.erase(before);
    m[a] = after;
    cout << mp.size() << endl;
  }
  return 0;
}

E - 7x7x7

一つの直方体は原点に固定して、残り２つの座標を -7 〜 +7 の範囲で全探索する。 直方体の重なっている部分の面積はがんばって計算する。

#include <bits/stdc++.h>
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 L = 7;
// 3つの直方体が重なっている部分の面積を返す
int calcArea(T sq1, T sq2, T sq3) {
  auto [x1,y1,z1] = sq1;
  auto [x2,y2,z2] = sq2;
  auto [x3,y3,z3] = sq3;
  int minX = max({x1, x2, x3});
  int maxX = min({x1, x2, x3}) + L;
  int minY = max({y1, y2, y3});
  int maxY = min({y1, y2, y3}) + L;
  int minZ = max({z1, z2, z3});
  int maxZ = min({z1, z2, z3}) + L;
  if (maxX - minX < 0 || maxY - minY < 0 || maxZ - minZ < 0) return 0;
  return (maxX - minX) * (maxY - minY) * (maxZ - minZ);
}

int main() {
  vector<int> v(3);
  REP(i,3) cin >> v[i];

  auto f = [&](int x1, int y1, int z1, int x2, int y2, int z2) {
    T sq1 = {0,0,0};
    T sq2 = {x1,y1,z1};
    T sq3 = {x2,y2,z2};

    int v3 = calcArea(sq1,sq2,sq3);
    // 1-2, 1-3, 2-3 それぞれの組み合わせで重なっている部分の面積の合計 - 3つ重なっている部分の面積
    int v2 = calcArea(sq1,sq1,sq2) + calcArea(sq1,sq1,sq3) + calcArea(sq2,sq2,sq3) - v3*3;
    int v1 = (7*7*7*3) - (v3*3 + v2*2); // 3つの合計面積 - 重なっている部分の面積
    return (v[0] == v1 && v[1] == v2 && v[2] == v3);
  };

  for(int i1 = -7; i1 <= 7; i1++) {
    for(int j1 = -7; j1 <= 7; j1++) {
      for(int k1 = -7; k1 <= 7; k1++) {
        for(int i2 = -7; i2 <= 7; i2++) {
          for(int j2 = -7; j2 <= 7; j2++) {
            for(int k2 = -7; k2 <= 7; k2++) {
              if (f(i1,j1,k1,i2,j2,k2)) {
                printf("Yes\n0 0 0 %d %d %d %d %d %d\n",i1,j1,k1,i2,j2,k2);
                return 0;
              }
            }
          }
        }
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

tic40さんのAtCoder Beginner Contest 343での成績：1741位
パフォーマンス：1296相当
レーティング：1050→1077 (+27) :)
#AtCoder #ABC343 https://atcoder.jp/users/tic40/history/share/abc343?lang=ja 

AtCoder abc342 参加メモ

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342） - AtCoder

B - Which is ahead?

#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> p(n);
  REP(i,n) cin >> p[i];
  vector<int> m(n+1);
  REP(i,n) m[p[i]] = i;
  int q; cin >> q;
  REP(_,q) {
    int a,b; cin >> a >> b;
    int v1 = m[a], v2 = m[b];
    if (v1 > v2) swap(a,b);
    cout << a << endl;
  }
  return 0;
}

C - Many Replacement

#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; string s;
  cin >> n >> s >> q;
  vector<char> c(26);
  REP(i,26) c[i] = char('a' + i);
  REP(_,q) {
    char a,b; cin >> a >> b;
    REP(i,26) if (c[i] == a) c[i] = b;
  }
  for(auto v: s) cout << c[v-'a'];
  return 0;
}

D - Square Pair

A について素因数分解して平方数で割った残りの数を計算する。 map でその数をカウントしておいて、各値xに対して (map[x] * (map[x]-1)) / 2 の数だけ組み合わせが作れる。 0 のケースの扱いに気をつける。

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

vector<ll> prime_factorize(ll n) {
  vector<ll> res;
  for(ll a = 2; a*a <= n; a++) {
    if (n%a != 0) continue;
    ll ex = 0;
    while(n%a == 0) { ex++; n /= a; }
    if (ex % 2) res.emplace_back(a);
  }
  if (n != 1) res.emplace_back(n);
  return res;
}

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

  map<ll,ll> mp;
  REP(i,n) {
    auto pf = prime_factorize(a[i]);
    ll now = 1;
    for(auto v: pf) now *= v;
    mp[now]++;
  }

  ll ans = 0;
  for(auto [k,v]: mp) {
    if (k == 0) ans += (n-1)*v;
    else ans += (mp[0] + (v-1))*v;
  }
  cout << ans/2 << endl;
  return 0;
}

abc340 E - Mancala 2

E - Mancala 2

ac library の lazy segtree を使った解法

#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 S = ll;
using F = ll;
S op(S a, S b){ return 0; }
S e(){ return 0; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

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

  lazy_segtree<S,op,e,F,mapping,composition,id> seg(a);
  REP(i,m) {
    ll now = seg.get(b[i]); // 箱 b[i] に現在入っているボールの数を取得
    ll r = now / n; // 何周するか
    ll rem = now % n; // r 周した余り
    seg.set(b[i],0); // 箱 b[i] を空にする
    seg.apply(0,n,r); // r 周分を全体に加算

    // 余り分を加算
    if (b[i]+rem < n) {
      seg.apply(b[i]+1, b[i]+rem+1,1);
    } else {
      seg.apply(b[i]+1,n,1);
      seg.apply(0, (b[i]+rem)%n+1,1);
    }
  }

  REP(i,n) cout << seg.get(i) << " ";
  return 0;
}

コンテストでは fenwick tree で累積和をして解いたが、lazy segtree の方が簡単だった。

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

今回はここまで