https://beta.atcoder.jp/contests/arc093/tasks/arc093_a 3点を見比べる。
https://beta.atcoder.jp/contests/arc093/tasks/arc093_b 一面黒に塗って白をその中にちまちま塗る。逆も同じ。
https://beta.atcoder.jp/contests/arc064/tasks/arc064_b えー結構難しい。端の文字が異なるなら文字数偶数で終わり、同じなら奇数。
https://beta.atcoder.jp/contests/arc071/tasks/arc071_b xy独立なやつ。
https://beta.atcoder.jp/contests/arc059/tasks/arc059_c 独立利用してちょっとめんどくさい前処理すればおわり。
https://beta.atcoder.jp/contests/arc059/tasks/arc059_d うーんこういうの苦手。情報を同一視するのが得意じゃないのかなぁ。結局文字数がMになる場合を数え上げればいいだけ。
3/24精進
https://beta.atcoder.jp/contests/arc060/tasks/arc060_c doublingするだけ。
https://beta.atcoder.jp/contests/agc005/tasks/agc005_c 一番長いパスを考えれば一瞬。 cout << "Impossible\n"; return;はアホらしいので別の関数を用意しましょう。
https://beta.atcoder.jp/contests/agc010/tasks/agc010_c 下からmergeする辺の本数が決まっていく。その時
http://omochan.hatenablog.com/entry/2018/02/24/113010と同じような話が出てくる。めっちゃWAした。
3/23精進
https://beta.atcoder.jp/contests/agc002/tasks/agc002_b DPっぽいことすればできます。でもあまり自分にはない発想なので解いてよかった。
https://beta.atcoder.jp/contests/agc003/tasks/agc003_b 小さいものからペアにしていけばいいです。0に注意。
https://beta.atcoder.jp/contests/agc004/tasks/agc004_b 400にしては難しくない…?魔法唱える回数固定すれば捕まえるスライムがわかる
https://beta.atcoder.jp/contests/agc005/tasks/agc005_b よくある一番大きいのとって区間分けるやつ
https://beta.atcoder.jp/contests/agc006/tasks/agc006_b 自明な必要条件が実は十分でもあってたまげる。
https://beta.atcoder.jp/contests/agc007/tasks/agc007_b a+b=1,2,3...となるように調節する。Editorialの小さい差を無視する方法も覚えておく。
https://beta.atcoder.jp/contests/agc008/tasks/agc008_b 塗り方はKマス同じの塗っちゃえば後は自由です。
https://beta.atcoder.jp/contests/agc011/tasks/agc011_b 大きさ順に並べればどっかでその色にできるできないの境目があるのでにぶたん。
https://beta.atcoder.jp/contests/agc015/tasks/agc015_b 特になし。
400のConstructive要素が入った問題は普通に手こずりますね。必要条件に注目大事。
精進3/22
https://beta.atcoder.jp/contests/arc058/tasks/arc058_b コンビネーションやるだけだけど、素早く通せてよかった。
https://beta.atcoder.jp/contests/abc088/tasks/abc088_d 幅優先久しぶりに書いた…
https://beta.atcoder.jp/contests/arc065/tasks/arc065_b これ難しくないですか?グループ同じ<=>数が同じに言い換える。本当に思いつかなかった。
https://beta.atcoder.jp/contests/arc074/tasks/arc074_a 切り方4通り試す。
https://beta.atcoder.jp/contests/arc080/tasks/arc080_a 14141422222...みたいな。
https://beta.atcoder.jp/contests/arc080/tasks/arc080_b ウネウネさせる
https://beta.atcoder.jp/contests/arc081/tasks/arc081_b すんごいしょぼいDP
https://beta.atcoder.jp/contests/arc082/tasks/arc082_b やばそうと思うけど、入れ替えないといけない数字が連続した区間を見るだけ
https://beta.atcoder.jp/contests/arc090/tasks/arc090_b グラフにすぐ見えたので勝ち
https://beta.atcoder.jp/contests/arc059/tasks/arc059_b 累積和。この系統400にめっちゃ多い。
https://beta.atcoder.jp/contests/arc061/tasks/arc061_b 面白い。黒いマスの周り9通りのエリアを見る。
https://beta.atcoder.jp/contests/abc061/tasks/abc061_d ループ検出するだけ…ではなく頂点Nがループに含まれているのも見ないといけない。
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d modでまとめればできる。
3/21精進
適当に簡単めの問題をたくさん解いたのでメモっときます。
https://beta.atcoder.jp/contests/abc051/tasks/abc051_d ワーシャルフロイドして辺を通るルートは最適か見る。
https://beta.atcoder.jp/contests/abc054/tasks/abc054_d 混合液の量が小さいのでdp
https://beta.atcoder.jp/contests/abc057/tasks/abc057_d 上から取れば良い。しかしベストな個数がAであることに気づかず。
https://beta.atcoder.jp/contests/abc073/tasks/abc073_d next_permutation
https://beta.atcoder.jp/contests/abc075/tasks/abc075_d 座圧+累積和
https://beta.atcoder.jp/contests/abc076/tasks/abc076_d 良問。時間が整数しかとりえないことを利用してDPしたが、解説の条件を列挙するほうが筋が良い。
https://beta.atcoder.jp/contests/abc079/tasks/abc079_d ワーシャルフロイド
https://beta.atcoder.jp/contests/abc080/tasks/abc080_d 0.5の罠に引っかからないこと。座標二倍して整数にしても良かった。
https://beta.atcoder.jp/contests/abc085/tasks/abc085_d 殴る剣と投げる剣の２つに分解して考えるとわかりやすい。貪欲。
https://beta.atcoder.jp/contests/arc060/tasks/arc060_b わけわかんないと思ったら途中まで愚直にやる形だと疑ったほうが良さそう。
https://beta.atcoder.jp/contests/arc073/tasks/arc073_b ちょっとだけナップサックいじるだけ
https://beta.atcoder.jp/contests/arc063/tasks/arc063_b おもしろい。Tは関係なくて、一番差が大きい区間が問題。そのような区間は重なり合わないので、個数を数えれば良い。
imosと累積和を混同しないように。
imosで[s, t]まで1足すときS[s]++, S[t + 1]--
累積和で[s, t]の和を求めるときS[t + 1]- S[s]
ARC091
https://beta.atcoder.jp/contests/arc091/tasks/arc091_a
速さが足りない。
C
はい。
ll N, M; void solve() { cin >> N >> M; if(N > M) swap(N, M); if(N == 1) { if(M == 1) cout << "1\n"; else if(M == 2) cout << "0\n"; else cout << M - 2 << "\n"; } else if(N == 2) { cout << "0\n"; } else cout << (N - 2) * (M - 2) << "\n"; }
D
こういうの速くかけないとなぁ。
ll N, K; void solve() { cin >> N >> K; if(K == 0) { cout << N * N << "\n"; return; } ll res = 0; rep(b, K + 1, N + 1) { ll to = N / b; int a = 0; res += to * (b - K); a += to * (b - K); res += max(0LL, N - (to * b + K - 1)); a += max(0LL, N - (to * b + K - 1)); // debug(b, a, to); } cout << res << "\n"; }
E
いい感じの必要条件が思いつかなかったので発見的にときました。証明もしてないですけどまあ通るだろうということで。
なんでこれ爆速で解けるんだ…
int N, A, B; int ans[MAX_N]; void solve() { cin >> N >> A >> B; if(N == 1) { if(A == 1 && B == 1) { cout << 1 << "\n"; } else cout << "-1\n"; return; } bool swaped = false; if(A < B) { swap(A, B); swaped = true; } vector<int> cnt(B, 1); int n = N; if((N + A - 1) / A > B) { cout << "-1\n"; return; } rep(i, 0, (N + A - 1) / A) { cnt[i] = min(A, n); n -= A; } int r = B - (N + A - 1) / A; rep(i, 1, (N + A - 1) / A) { if(cnt[i] - 1 >= r) { cnt[i] -= r; r = 0; } else { cnt[i] = 1; r -= (cnt[i] - 1); } } if(r != 0) { cout << "-1\n"; return; } int at = 0; int from = N - 1; rep(i, 0, B) { rep(j, 0, cnt[i]) { ans[at] = from - cnt[i] + j + 1; at++; } from -= cnt[i]; } if(swaped) reverse(ans, ans + N); rep(i, 0, N) { cout << ans[i] + 1 << " "; } cout << "\n"; }
F
grundyの高速化って眺めることしかないし、適当にプログラム書いて眺めたんですけどよくわかんなかったです。でも手で書いたらわかったので、計算量大丈夫か勘定してACしました。
int grundy1(ll A, ll K) { if(A < K) return 0; if(A % K == 0) return A / K; else return grundy1(A - A / K - 1, K); } int grundy2(ll A, ll K) { if(A < K) return 0; if(A % K == 0) return A / K; else { ll m = A / K; ll to = m * K; return grundy2(A - ((A - to + m) / (m + 1)) * (m + 1), K); } } void solve() { ll N; cin >> N; ll res = 0; rep(i, 0, N) { ll A, K; cin >> A >> K; if(K <= 10000) res ^= grundy1(A, K); else res ^= grundy2(A, K); } if(res != 0) cout << "Takahashi\n"; else cout << "Aoki\n"; }
AGC005F: Many Easy Problems
https://beta.atcoder.jp/contests/agc005/tasks/agc005_f
FMT初実装です。
まず求めるものを式にすると
ans[K]=1/(K!)Σ(i=K...N)cnt[i]*(i!)/(i-K)!
となります。ただしcnt[i]はサイズがiである部分木の数です。
これを式変形すると、
ans[N-u]=1/((N-u)!)Σ(i=0...u)d[u-i]*e[i]となります。
ただしd[i]=cnt[N-i]*(N-i)!、e[i]=1/(i!)です。このようにdi,eiがK(またはu)に依存しない式が立てれれば、FMTが使えます。iとK-iの式で表わせる形があったらFFTを疑ったほうが良さそうですね。
FMTですが、FFTとほとんど同じです。代わりにω^n=1(mod p)を満たすようなωを探せばいいだけです。その際にpの原始根が必要になるんですが、与えられるpは因数分解すると綺麗な形になっているので、見つけるのもそんなに苦労はしないです。
今回はp=924844033ですが原子根の１つに5があります。
struct FMT { const int num_factor = 3; ll factor[3] = {2, 3, 7}; ll gen = 5; ll mod_pow(ll a, ll n) { if(n == 0) return 1; ll res = mod_pow(a, n / 2); if(n % 2 == 0) return res * res % mod; else return a * res % mod * res % mod; } bool check() { rep(i, 0, num_factor) { if(mod_pow(gen, (mod - 1) / factor[i]) == 1) { return false; } } return true; } void fmt(vector<ll>& v, bool rev = false) { //v.size() == (1 << x) int n = sz(v), i, j; for(i = 0, j = 1; j < n - 1; j++) { for(int k = n >> 1; k > (i ^= k); k /= 2); if(i > j) swap(v[i], v[j]); } for(int m = 2; m <= n; m *= 2) { ll root = mod_pow(gen, (mod - 1) / m); for(int i = 0; i < n; i += m) { ll w = 1; rep(j, 0, m / 2) { ll f0 = v[i + j], f1 = w * v[i + j + m / 2] % mod; v[i + j] = (f0 + f1) % mod; v[i + j + m / 2] = (mod + f0 - f1) % mod; MUL(w, root); } } } if(rev) rep(i, 0, n) MUL(v[i], mod_pow(n, mod - 2)); } vector<ll> get(const vector<ll>& A, const vector<ll>& B) { int n = 1; int len = sz(A) + sz(B) - 1; while(n < len) n *= 2; vector<ll> a(n, 0), b(n, 0); rep(i, 0, sz(A)) a[i] = A[i]; rep(i, 0, sz(B)) b[i] = B[i]; fmt(a); fmt(b); rep(i, 0, n) MUL(a[i], b[i]); reverse(++a.begin(), a.end()); fmt(a, true); vector<ll> res(len); rep(i, 0, len) res[i] = a[i]; return res; } }; int N; vi G[MAX_N]; int cnt[MAX_N]; int dfs(int v, int p = -1) { int res = 1; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(n == p) continue; res += dfs(n, v); } if(p != -1) { cnt[res]++; cnt[N - res]++; } return res; } void solve() { cin >> N; C_init(N + 10); rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } dfs(0); vector<ll> D(N + 1), E(N + 1); rep(i, 0, N + 1) { D[i] = cnt[N - i] * fac[N - i] % mod; E[i] = fiv[i]; } FMT f; vector<ll> F = f.get(D, E); vector<ll> ans(N + 1); rep(i, 0, N) { ans[N - i] = (mod + N * C(N, i) % mod - fiv[N - i] * F[i] % mod) % mod; } rep(i, 1, N + 1) cout << ans[i] << "\n"; }
