ABC145
結果
問題 | ACまでに要した時間 | AC | WA | TLE |
---|---|---|---|---|
A | 1:09 | 1 | 0 | 0 |
B | 5:18 | 1 | 0 | 0 |
C | 16:55 | 1 | 0 | 0 |
D | - | 0 | 0 | 0 |
Rating | 順位 |
---|---|
550 (+64) | 1850 |
コメント
- A, B, Cはたまたま簡単だったので速く解けただけのような気もするが,久々にレーティングをプラス更新することができた
- Dは解答の方針は分かったが,
{}_{m+n} C _n
の計算とmod 10000007の計算の実装がうまくできずに終了した- この手の「大きい整数で割って回答する」パターンは結構出るので解けるようになっておかないといけない.そのため完全な準備不足
- あとE問題はDPで解けそうだったけど前処理をどのようにするか分からなくて手が出なかった
- 今回のレーティングの上がり幅からして,次はABC超速解きに加えてDかEもACしないとレーティングがほとんど上がらないような状態に見える..厳しくなってきた.
解答
D
合同式における加減乗除演算の計算方法と逆元の求め方は調べた上で以下に別途まとめた.
serihiro-competitive-programming.hatenablog.jp
コンテスト時は以下の式変形をするところまではできたが肝心の除算しながらCombinationを計算する方法が分からずに断念した.
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef unsigned long long ll; using namespace std; const ll MOD = 1000000007; const ll MAX = 1000000; vector<ll> fac(MAX, 0ll); vector<ll> finv(MAX, 0ll); vector<ll> inv(MAX, 0ll); void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (ll i = 2; i <= MAX; i++) { fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } long long COM(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; // n! / (r!(n-r)!) return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int main() { cin.tie(0); ios::sync_with_stdio(false); ll X, Y, n, m; cin >> X >> Y; COMinit(); // 2n + m = X // n + 2m = Y // <=> m = (2Y - X)/3, n = Y - 2m; if ((X + Y) % 3 == 0) { m = ((2 * Y - X) / 3); n = (Y - 2 * m); cout << COM(n + m, m) << endl; } else { cout << 0 << endl; return 0; } return 0; }
解説放送出てきた t.co
Writerのコメント
フェネック「C問題は、制約が小さいから全ての順列を全探索すれば解けるけど、O(N^2)で解けるから考えてみてねー。D問題は、(+1,+2),(+2,+1)のどっちを何回したかはすぐ分かるから、あとは二項係数を求めるだけだよ。組み合わせ問題の入門、mod逆元の入門のつもりで作ってみたけどどうだったかなー?」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2019年11月16日
茶色雑魚勢には難しかったのだフェネック…
2019年に出たABCで唯一4完チャンスがあったABC145だが,逆元使って剰余取りながら除算する方法知らないとD問題だけはどうしようもなかった.