AtCoder abc253 参加メモ

NOMURA Programming Contest 2022（AtCoder Beginner Contest 253） - AtCoder の参加メモ

B - Distance Between Tokens

2つのoの位置を見つけてそのマンハッタン距離を計算する

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

int main() {
  int h,w; cin >> h >> w;
  vector<string> s(h);
  REP(i,h) cin >> s[i];

  vector<pair<int,int>> p;
  REP(i,h) REP(j,w) if(s[i][j] == 'o') p.emplace_back(i,j);
  int ans = abs(p[0].first - p[1].first) + abs(p[0].second - p[1].second);
  cout << ans << endl;

  return 0;
}

C - Max - Min Query

mapで集合Sを管理する。iteratorの最初と最後を参照すればSの最小/最大値が取得できる

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

int main() {
  int q; cin >> q;

  map<int,int> mp;
  REP(_,q) {
    int t; cin >> t;

    if(t == 1) {
      int x; cin >> x;
      mp[x]++;
    } else if (t == 2) {
      int x,c; cin >> x >> c;
      mp[x] = max(0, mp[x]-c);
      if (mp[x] == 0) mp.erase(x);
    } else {
      cout << ((--mp.end())->first - mp.begin()->first) << endl;
    }
  }
  return 0;
}

D - FizzBuzz Sum Hard

• 初項がa、末項がl、公差がd、項数がn の等差数列の総和は $ 1/2n(a+l) $ で求められる。
• A の倍数でも B の倍数でもないものの総和 = (1〜Nの総和) - Aの倍数の数列の総和 - Bの倍数の数列の総和 + A,Bの最小公倍数の数列の総和

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

int main() {
  ll n,a,b; cin >> n >> a >> b;

  ll ans = (1+n)*n/2;
  ans -= (a+n/a*a)*(n/a)/2;
  ans -= (b+n/b*b)*(n/b)/2;
  ll l = lcm(a,b);
  ans += (l+n/l*l)*(n/l)/2;

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

E - Distance Sequence

• 動的計画法 + fenwick_tree。fenwick_treeを利用することで区間の要素の総和を O(logN) で求められる。
• a[i] - a[i+1] >= k のケースと a[i+1] - a[i] >= k のケース二通りの範囲を計算しているが、k == 0 の場合には範囲が被るため注意

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

int main() {
  int n,m,k; cin >> n >> m >> k;

  fenwick_tree<mint> dp(m+1);
  for(int i = 1; i <= m; i++) dp.add(i,1);

  REP(_,n-1) {
    fenwick_tree<mint> p(m+1);
    swap(dp,p);
    for(int j = 1; j <= m; j++) {
      if (k == 0) {
        dp.add(j, p.sum(1,m+1));
        continue;
      }

      int x1 = j + k;
      if (x1 <= m) dp.add(j, p.sum(x1, m+1));
      int x2 = j - k;
      if (1 <= x2) dp.add(j, p.sum(1, x2+1));
    }
  }

  cout << dp.sum(1,m+1).val() << endl;
  return 0;
}