http://tdpc.contest.atcoder.jp/
K
O(NlogN)ということは問題が簡単な構造をしていますね?区間dpなど複雑なものを考えないでください。
segtreeを使ってできます。
std::findはO(logN)と思っていたのでTLE出た時びっくりした。
あと区間を使う順番に気を付けず、WAも出した。
ちなみにstd::countもO(N)で
set.count、set.findはともにO(logN)です。混同しがち。
int N, M;
ll A[MAX_N], B[MAX_N];
ll vx[MAX_N];
vector<int> G[MAX_N];
segtree seg;
int fd(ll a) {
return lower_bound(vx, vx + M, a) - vx;
}
void solve() {
cin >> N;
rep(i, 0, N) {
ll x, r;
cin >> x >> r;
A[i] = x - r; B[i] = x + r;
vx[M++] = A[i];
vx[M++] = B[i];
}
sort(vx, vx + M);
M = unique(vx, vx + M) - vx;
seg.init(M);
rep(i, 0, N) {
int a = fd(A[i]), b = fd(B[i]);
G[a].push_back(b);
}
rep(i, 0, M) sort(all(G[i]));
rep(i, 0, M) {
rep(j, 0, (int)G[i].size()) {
int a = G[i][j];
int b = seg.get(a + 1, M).v;
int c = seg.get(a, a + 1).v;
if(c < b + 1) {
seg.update(a, b + 1);
}
}
}
cout << seg.get(0, M).v << "\n";
}
L
最初猫の順番は自由だと思っていてこんなのNP-Completeだろ!って思っていた。
i番目の猫から左に距離1以内に含まれる猫の最大indexをL[i]とするとLは単調増加。これを生かしてdpできる。
猫の順番が自由の場合NP-Completeであることを示すなら、ほかのNP-Completeの問題(3-SATなど)に帰着させる必要があるができず。
int N;
int A[MAX_N][MAX_N], S[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
void solve() {
cin >> N;
rep(i, 0, N)
rep(j, 0, N) {
cin >> A[i][j];
dp[i][j] = -inf;
}
rep(i, 0, N) {
rep(j, i + 1, N) {
S[i][j] = S[i][j - 1] + A[i][j];
}
}
dp[0][0] = 0;
rep(i, 0, N) {
rep(j, i, N) {
if(i != N - 1) MAX(dp[i + 1][j], dp[i][j] + S[i + 1][j]);
if(j != N - 1) MAX(dp[i][j + 1], dp[i][j] + A[i][j + 1]);
if(i == j) MAX(dp[i + 1][j + 1], dp[i][j]);
}
}
cout << dp[N - 1][N - 1] * 2 << "\n";
}
M
巡回セールスマンしてから行列累乗。O(R^3*2^R+R^3*log(H))みたいになってヤバそうだがTLEが8秒なので余裕。
bitdpはbitのループを一番外に書きましょう。当たり前ですが。WA取りかけた。
int R, N;
ll dp[16][(1 << 16)];
int G[16][16];
void solve() {
cin >> R >> N;
rep(i, 0, N)
rep(j, 0, N) cin >> G[i][j];
mat A(N, vl(N, 0));
rep(n, 0, N) {
memset(dp, 0, sizeof(dp));
dp[n][(1 << n)] = 1;
rep(bit, 0, (1 << N)) {
rep(i, 0, N) {
rep(j, 0, N) {
if(i == j || !G[i][j]) continue;
if(bit & (1 << j)) continue;
if(!dp[i][bit]) continue;
ADD(dp[j][bit | (1 << j)], dp[i][bit]);
}
ADD(A[i][n], dp[i][bit]);
}
}
}
cout << mat_pow(A, R)[0][0] << "\n";
}
N
最初に使う辺を決めてしまえばあとはそこから順番に使っていくだけ。dpテーブルすらいらない。
木dpなどでありがちのmergeする感じで更新していくと実装軽くて良い。
int N;
int A[MAX_N], B[MAX_N];
ll C[MAX_N][MAX_N];
vector<int> G[MAX_N];
void C_init(int n) {
n++;
rep(i, 0, n) C[i][0] = 1;
rep(i, 1, n) {
rep(j, 1, i + 1) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
C[i][j] %= mod;
}
}
}
pl merge(pl a, pl b) {
return make_pair(a.fst * b.fst % mod
* C[a.sec + b.sec][a.sec] % mod, a.sec + b.sec);
}
pl dfs(int v, int p) {
pl res(1, 0);
rep(i, 0, (int)G[v].size()) {
int n = G[v][i];
if(n == p) continue;
pl d = dfs(n, v); d.sec++;
res = merge(res, d);
}
return res;
}
void solve() {
cin >> N;
C_init(N + 10);
rep(i, 0, N - 1) {
cin >> A[i] >> B[i];
A[i]--; B[i]--;
G[A[i]].pb(B[i]);
G[B[i]].pb(A[i]);
}
ll res = 0;
rep(i, 0, N - 1) {
pl a = dfs(A[i], B[i]);
pl b = dfs(B[i], A[i]);
res += merge(a, b).fst;
res %= mod;
}
cout << res << "\n";
}
なおC(Combination)だが、次のようにしてもさほど実行時間が変わらず、N=10^6などでも対応できるので脳死でこっちを常に使えばいいと思う。
invをmod-2の累乗で求めるやつはかなり遅いのでやめましょう。
ll fac[MAX_N], inv[MAX_N], fiv[MAX_N];
void C_init(int n) {
fac[0] = fac[1] = 1;
inv[1] = 1;
fiv[0] = fiv[1] = 1;
rep(i, 2, n + 1) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
fiv[i] = fiv[i - 1] * inv[i] % mod;
}
}
ll C(int a, int b) {
if(a < b || a < 0 || b < 0) return 0;
return fac[a] * fiv[b] % mod * fiv[a - b] % mod;
}
O
同じ文字が連続している隙間の数を持ってdpを行う。
隙間に高々10個の同じ文字を入れることを考えれば良いので、前処理として1~10の足し算による分解(例えば10=1+4+5など)を全通り求めておく。
後は適当に場合の数の計算をすればできる。
10の足し算による分解方法は42通りなので、計算量は26*26*10*42*42*10<=1.2*10^8とかで抑えられて通ります。
なぜかWAしてどうしてだろうと思ってたら、普段使っているテンプレートが間違っていて戦慄。
vector<vi> F[11];
int D[11][50][11];
void loop(int a, vi vec) {
F[a].pb(vec);
int n = (int)vec.size();
int t = vec[n - 1];
vec.resize(n + 1); n++;
int s = accumulate(all(vec), 0);
for(int i = t; i + s <= 10; i++) {
vec[n - 1] = i;
loop(i + s, vec);
}
}
int A[27];
ll dp[27][300];
void solve() {
C_init(300);
vi vec(1, 0);
rep(i, 1, 11) {
vec[0] = i;
loop(i, vec);
}
rep(i, 1, 11) {
rep(j, 0, (int)F[i].size()) {
rep(k, 0, 11) {
D[i][j][k] = count(all(F[i][j]), k);
}
}
}
F[0].pb(vi(1, 0));
D[0][0][0] = 1;
dp[0][0] = 1;
int s = 1;
rep(i, 0, 26) cin >> A[i];
rep(n, 0, 26) {
rep(m, 0, s + 1) {
rep(i, 0, A[n] + 1) {
int a = i, b = A[n] - i;
int as = s - m, bs = m;
rep(j, 0, (int)F[a].size()) {
rep(k, 0, (int)F[b].size()) {
int an = (int)F[a][j].size(), bn = (int)F[b][k].size();
if(F[a][j][0] == 0) an = 0;
if(F[b][k][0] == 0) bn = 0;
if(as < an || bs < bn) continue;
ll tmp = 1;
MUL(tmp, fac[as] * fiv[as - an] % mod);
MUL(tmp, fac[bs] * fiv[bs - bn] % mod);
rep(l, 0, 11) {
MUL(tmp, fiv[D[a][j][l]]);
MUL(tmp, fiv[D[b][k][l]]);
}
int to = m;
rep(l, 0, an) {
to += F[a][j][l] - 1;
}
rep(l, 0, bn) {
to += F[b][k][l] - 2;
}
assert(to >= 0);
ADD(dp[n + 1][to], dp[n][m] * tmp % mod);
}
}
}
}
s += A[n];
}
cout << dp[26][0] << "\n";
}
単調性大事なのはわかるけど、dpとの関連性がよくわからない…
あとOは重複組合せすればめんどくさいことしなくて済みますね…
