AtCoder abc300 参加メモ

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300) - AtCoder

B - Same Map in the RPG World

H,W <= 30 のため縦方向 shift と横方向 shift を全探索できる

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

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

  // s: 縦方向shift数, t: 横方向shit数
  auto f = [&](int s, int t) {
    REP(i,h) REP(j,w) {
      int ni = (i+s) % h;
      int nj = (j+t) % w;
      if (a[ni][nj] != b[i][j]) return false;
    }
    return true;
  };

  int ok = 0;
  REP(i,h) REP(j,w) ok |= f(i,j);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

C - Cross

B と同じく H,W <= 100 のためすべての座標を全探索できる

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

const vector<P> m = { {1,1}, {1,-1}, {-1,1}, {-1,-1} };

int main() {
  int h,w; cin >> h >> w;
  vector<string> c(h);
  REP(i,h) cin >> c[i];
  int n = min(h,w);

  // 座標(i,j)を中心とする x印のサイズを返す
  auto f = [&](int i, int j) {
    if (c[i][j] == '.') return 0;
    int res = 0;
    for(int k = 1; k <= n; k++) {
      for(auto [vi,vj]: m) {
        int ni = i + vi * k;
        int nj = j + vj * k;
        if (ni < 0 || nj < 0 || ni >= h || nj >= w) return res;
        if (c[ni][nj] == '.') return res;
      }
      res = k;
    }
    return res;
  };

  vector<int> ans(n+1);
  REP(i,h) REP(j,w) ans[f(i,j)]++;
  REP(i,n) cout << ans[i+1] << " ";
  return 0;
}

D - AABCC

エラトステネスの篩で素数を列挙し、そこから a < b の組み合わせとなる値を全探索する。

#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<int> eratosthenes(int n) {
  vector<int> res;
  vector<bool> is_prime(n+1,true);
  for(int i = 2; i <= n; i++) {
    if (!is_prime[i]) continue;
    for(int j = 2*i; j <= n; j+=i) is_prime[j] = false;
    res.push_back(i);
  }
  return res;
}

int main() {
  ll n; cin >> n;
  auto p = eratosthenes(sqrt(n));
  sort(p.begin(),p.end());
  int sz = p.size();

  int ans = 0;
  REP(i,sz) for(int j = i+1; j < sz; j++) {
    ll a = p[i], b = p[j];
    ll c = sqrt( n / (a*a*b) );
    if (c <= b) break;
    int idx = upper_bound(p.begin(),p.end(),c) - p.begin();
    ans += max(0, idx-j-1);
  }

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

E - Dice Product 3

abc298 の E - Unfair Sugoroku と似ている。

n の数が 10¹⁸ と大きいので計算量が不安になるが、公式解説にあるように 2^a * 3^b * 5^c で表せる数の個数は大きくないため、メモ化再帰で十分間に合う

#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 mint = modint998244353;

int main() {
  ll n; cin >> n;
  mint p = mint(1)/5;

  map<ll,mint> mem;
  auto dfs = [&](auto self, ll now) -> mint {
    if (now >= n) return now == n ? 1 : 0;
    if (mem.count(now)) return mem[now];
    mint res;
    for(int i = 2; i <= 6; i++) res += self(self,now*i);
    res *= p;
    return mem[now] = res;
  };

  cout << dfs(dfs,1).val() << endl;
  return 0;
}