RUPC2019参加記 Day3

Posted on 3 mins read

2日目の続きです。
※この記事は問題のネタバレを含みます

コンテスト

@yamerarenakuさん、@kouki111x1さんと組みました。
問題は、北海道大学の3時間のセットでした。

@yamerarenakuくんがEのmanacher解放を一瞬で伝えてくれたのが最強でした。
Fは実装も考察もコンテスト中に手前まで行っていて、落ち着いて考察したら解けていたと思うので通せなかったのが残念でした。

内容

C: 約数ゲーム / Divisor Game

最大値: 約数の個数-1 (小さい順に言えば全部言える)
最小値: 素因数の種類数 (1つの素因数について1つだけ減らしたものを全部言う必要がある)

signed main() {
  int n; cin >> n;
  map<int, int> mp;
  for (int x = 2; x * x <= n; x++) {
    while (n % x == 0) {
      mp[x]++;
      n /= x;
    }
  }
  if (n > 1) mp[n]++;
  int ans = 1;
  for (auto& p: mp) {
    ans *= (p.se + 1);
  }
  cout << mp.size() << ' ' << ans - 1 << endl;
}

E: 往復文字列 / Round-trip String

manacherを計算しておいて、あとは周期がkになっているかをkについて全探索すれば調和級数で$\mathcal{O}(n \log{n})$。
manacherはsnukeさんの記事を参考にさせていただきました(パクりました)。

vector<int> manacher(string& S) {
  vector<int> R(S.size());
  int i = 0, j = 0;
  while (i < S.size()) {
    while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
    R[i] = j;
    int k = 1;
    while (i-k >= 0 && i+k < S.size() && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
    i += k; j -= k;
  }
  return R;
}
signed main() {
  int n; cin >> n;
  string s; cin >> s;
  vector<int> a = manacher(s);
  REPI (k, 2, n + 1) {
    bool ok = true;
    for (int cen = k - 1; cen < n; cen += k - 1) {
      if (a[cen] < min(k, n - cen)) ok = false;
    }
    if (ok) {
      cout << k << endl; return 0;
    }
  }
}

F: 赤黒そーるじぇむ / Red-Black Soul Gem

とりあえず赤と黒の色の数を決めて、辺の貼り方を独立なものどうしに分割します。
赤と黒の間の辺の貼り方は基本的な包除原理で求まります。

(以下はコンテスト後に通したものです)

int n, MOD;
int mod_pow(int x, int n) {
  if (n == 0) return 1;
  int tmp = mod_pow(x, n / 2);
  return tmp * tmp % MOD * (n % 2 ? x : 1) % MOD;
}

int inv(int x) {
  return mod_pow(x, MOD - 2);
}

vector<int> fact, fact_inv, pows;
void init() {
  fact = vector<int>(n + 1, 1);
  fact_inv = vector<int>(n + 1);
  REP (i, n) {
    fact[i + 1] = fact[i] * (i + 1) % MOD;
  }
  fact_inv[n] = inv(fact[n]);
  for (int i = n; i >= 1; i--) {
    fact_inv[i - 1] = fact_inv[i] * i % MOD;
  }
  REP (i, n + 1) {
    assert(fact[i] * fact_inv[i] % MOD == 1);
  }

  pows = vector<int>(n + 1, 1);
  REP (i, n) {
    pows[i + 1] = pows[i] * 2 % MOD;
  }
}
int comb(int n, int r) {
  return fact[n] * fact_inv[r] % MOD * fact_inv[n - r] % MOD;
}

signed main() {
  cin >> n >> MOD;
  int ans = 0;
  init();
  REPI (a, 1, n) {
    int b = n - a;
    int acc = 0;
    REPI (i, 1, b + 1) {
      int sign = (b - i) % 2 ? -1 : +1;
      acc += sign * comb(b, i) % MOD * mod_pow(pows[i] - 1, a) % MOD;
      (acc += MOD) %= MOD;
    }
    int tmp = (a * (a - 1) + b * (b - 1)) / 2 % MOD;
    ans += acc * comb(n, a) % MOD * mod_pow(2, tmp) % MOD;
    ans %= MOD;
  }
  cout << ans << endl;
}

その他

  • やむなく君と昼ごはんを食べてから帰りました。
  • 考察のスピードをもっとつけたい、、
  • RUPC楽しかった！！