https://beta.atcoder.jp/contests/code-festival-2018-quala
通過です…
A
sortしたけど、要素が3つでなんかオーバーキルな気がしてしまう
B
愚直にやった。sortもしてません
C
まあdpだよね。0にならないとKを減らせないので注意。
D
まあdpだよね。BIT使ったけどよく考えると累積和で十分。
E
最小値固定して、最大値を決めるんだけど、不等式の条件を整理したら二次元座標である領域から点を見つける問題になって、O(ZlogZ)(Z=X+Y)になったが?あんまり同じ解き方している人いませんね…みんな答えを二分探索してるんだけど、結局最大値最小値どっちも移動してあんまいい方針に見えなかった…
オマケ
ABC110C
これ難しくないですか…。S[i]->T[i]にグラフ張って考察したらこんがらがってしまいました…。普通に元の操作で考えればよかったですね。
解法ですがYesの時、グラフで枝分かれができちゃだめなので、単ループor直線になります。
https://agc003.contest.atcoder.jp/tasks/agc003_f
非連結だと勘違いしてハマってた…
まず縦に並べても横に並べても繋がる場合は答えが1です。
どっちもつながらない場合は#の個数をPとしてP^(K-1)です。
問題は片方だけ繋がる場合です。今回は横に繋がるとします。
#が横に２つ連続で繋がるものの個数をen、連結成分の数をfnとします。
また、盤面を横に並べた時#が繋がる個数をDとします。
するとen+1とfn+1はPとDの線形和で表されます。後は行列累乗をO(logK)でやれば答えが求まります。
ただH=1とW=1の時は場合分けが発生するので注意しましょう。
void solve() { cin >> H >> W >> K; ll p = 0; rep(i, 0, H) { string str; cin >> str; rep(j, 0, W) { if(str[j] == '#') B[i][j] = 1; p += B[i][j]; } } int bh = 0, bw = 0; rep(j, 0, W) { if(B[0][j] == 1 && B[H - 1][j] == 1) bh++; } rep(i, 0, H) { if(B[i][0] == 1 && B[i][W - 1] == 1) bw++; } if(H == 1) { if(bw) cout << 1 << "\n"; else cout << mod_pow(p, K - 1) << "\n"; } else if(W == 1) { if(bh) cout << 1 << "\n"; else cout << mod_pow(p, K - 1) << "\n"; } else { if(bw && bh) { cout << 1 << "\n"; } else if(!bw && !bh) { cout << mod_pow(p, K - 1) << "\n"; } else { int e = 0; int f; if(bh) { rep(i, 0, H - 1) { rep(j, 0, W) { if(B[i][j] == 1 && B[i + 1][j] == 1) e++; } } f = bh; } else { rep(j, 0, W - 1) { rep(i, 0, H) { if(B[i][j] == 1 && B[i][j + 1] == 1) e++; } } f = bw; } // debug(bh, bw, p, e); mat A(2, vl(2, 0)); A[0][0] = p; A[0][1] = mod - 1; A[1][0] = 0; A[1][1] = f; mat B = mat_pow(A, K - 1); cout << (B[0][0] + B[0][1] * e % mod) % mod << "\n"; } } }
なんか割と非連結でもいけそうな雰囲気が漂っていたから誤読に全然気づかなかった…。
多分問題数もっと解けばできるできないの判断が鋭くなるんだろうな…
https://agc001.contest.atcoder.jp/tasks/agc001_f
わりと自然な考察で解けるからそんな難しくはないけど…でもおもしろいのは確か。
解説にあるとおりトポロジカル順を求めれば良いんですが以下はその具体的な方法です。
(i,A[i])のようにplotします。
[i,i+k)でy
[i,v)でy<=A[i]を満たす点の個数をB[i]として、C[i]:=(B[i]+ΣD[child of i])として、CをG上で求めます。
あとは簡単です。bool値の配列Dを用意します。
i番目について、
Dを0から順番に見ていって、C[i]番目のfalseが入っているidxを出力する。
D[idx]をtrueにする。
を繰り返せば答えが得られます。配列DはBITで代用できて、C[i]番目を見つけるのもBIT特有の二分探索で合計O(NlogN)でできます。
コード中のBITは普通のBIT(0-origin)
BITBは二分探索機能付きBIT(1-origin)です。ややこしい。
int N, K; int G[MAX_N]; int A[MAX_N]; int D[MAX_N], F[MAX_N]; pi Q[MAX_N]; int loop(int v) { if(F[v] != -1) return F[v]; int res = D[v]; if(G[v] != v) { res += loop(G[v]); } return F[v] = res; } void solve() { cin >> N >> K; rep(i, 0, N) { cin >> A[i]; A[i]--; } set<pi> S; rep(i, 0, K) S.insert(pi(-A[i], i)); rep(i, 0, N) { auto it = S.upper_bound(pi(-A[i], i)); if(it == S.end()) { G[i] = i; Q[A[i]] = pi(i, i + 1); } else { G[i] = (*it).sec; Q[A[i]] = pi(i, G[i]); } S.erase(pi(-A[i], i)); if(i + K < N) S.insert(pi(-A[i + K], i + K)); } BIT bit(N); rep(i, 0, N) { bit.update(Q[i].fst, Q[i].fst + 1, 1); D[Q[i].fst] = bit.get(Q[i].fst, Q[i].sec); } memset(F, -1, sizeof(F)); rep(i, 0, N) loop(i); BITB bb(N); rep(i, 0, N) bb.update(i + 1, 1); rep(i, 0, N) { int a = bb.get_index(F[i]); cout << a << "\n"; bb.update(a, -1); } }
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2382
証明がむずい。地雷。絶対450じゃない。数オリメダリストの力を借りました。
まず隣接してる頂点同士を結んで木を作ります。この木の辺の数をfとしましょう。
f=N-1の時、全ての頂点が直接的or間接的につながっていることになります。
その時、適当な点を根として葉からスライムを合成していけば操作はN-1回となります。
1回の操作でスライムの数はたかだか1個しか減らないのでこれが最小です。
f≠N-1としましょう。
最小回数は壁に頂点がある時2N-f-2、ない時2N-f-1であることを示しましょう。
まずN=2です。
壁にスライムがあったら、スライムがある壁にもうひとつのスライムを移動させてから合成すればいいので2回、
壁にスライムがなかったら、2つのスライムを同じ壁に追いやってから合成させればいいので3回です。
主張は成立してます。
今度はあるN(>=2)の時、上の主張が成立するとして、N+1について考えましょう。
あるスライムを動かして頂点の数がN+1からNに減少したとします。
このときf->f-1、N+1->Nとなり、Nの場合に帰着できます。よって、操作の回数は
1+2*N-(f-1)-(1or2)=2*(N+1)-f-(1or2)となり成立です。
今度は頂点の数がN+1からN+1となった時、つまり合成が起こらなかった時を考えます。
ちょっとややこしいですが、考えるとfはせいぜい1しか増えないことがわかります。
1回操作したのに、(-f)での減少効果も1しか得られないので、N+1→N+1にする操作をしても操作の回数が2(N+1)-f-(1or2)よりも
小さくならないことが言えます。
アー結局ここまで書いたのに雑になってしまいました…fが1しか増えないことを示すのも意外にややこしい。図を書けばなんとなく
わかるんですが。
あとN+1->Nに合成する時スライムが壁から離れないようにしないといけませんが、これもf=0で場合分けがあってめんどくさい。
だれか証明完成させてください…おねがいします…
int N, H, W; vector<int> G[300010]; bool used[300010]; void loop(int v) { used[v] = true; rep(i, G[v].size()) { int n = G[v][i]; if(!used[n]) loop(n); } } int main() { cin >> N >> H >> W; bool wall = false; rep(i, N) { int a, b; cin >> a >> b; a--; b--; if(a == 0 || a == H - 1 || b == 0 || b == W - 1) wall = true; G[i].pb(a + N); G[a + N].pb(i); G[i].pb(b + N + 100000); G[b + N + 100000].pb(i); } int K = 0; rep(i, N) { if(!used[i]) { loop(i); K++; } } if(K == 1) cout << N - 1 << "\n"; else cout << N + K - (wall ? 2 : 1) << "\n"; }
オマケでshortest code達成しておきました。
https://beta.atcoder.jp/contests/arc102/tasks
C
K/2が肝とわかれば。
D
2^nの辺を張って、適当に付け加えれば良さそうと思って実際そうでした。添字がめんどい。
int L; vector<pi> G[20]; void solve() { cin >> L; int N = 1; while(L >= (1 << N)) N++; rep(i, 0, N - 1) { G[i].pb(pi(i + 1, (1 << (N - 2 - i)))); G[i].pb(pi(i + 1, 0)); } L -= (1 << (N - 1)); int now = (1 << (N - 1)); rer(i, N - 1, 0) { if(L & (1 << i)) { G[0].pb(pi(N - 1 - i, now)); now += (1 << i); } } int M = 0; rep(i, 0, N) { M += sz(G[i]); } cout << N << " " << M << "\n"; rep(i, 0, N) { rep(j, 0, sz(G[i])) { cout << i + 1 << " " << G[i][j].fst + 1 << " " << G[i][j].sec << "\n"; } } }
E
奇偶に分けてじっと見たら対称性があることに気づいたのでDPしました。でもよく考えると二項係数だけで行ける。
最初包除かなと思ったんですが、こんがらがってしまいました。
包除なんですが、f(集合)というよりは、f(条件)とすれば、
f(S1∨S2∨S3)=(f(S1)+f(S2)+f(S3))-(f(S1∧S2)+f(S2∧S3)+f(S3∧S1))+f(S1∧S2∧S3)
となってわかりやすくないですか?僕はわかりやすいです。
int K, N; ll ans[4040]; ll dp[4040][4040]; void solve() { cin >> K >> N; C_init(4040); dp[0][0] = 1; for(int i = 0; i <= K / 2; i++) { rep(j, 0, K + 1) { if(!dp[i][j]) continue; ADD(dp[i + 1][j + 1], dp[i][j] * 2 % mod); ADD(dp[i + 1][j], dp[i][j]); } } for(int i = 1; i <= K / 2 + 1; i++) { for(int j = 0; j <= N; j++) { if(!dp[i][j]) continue; int a = N - j; int b = K - (i * 2) + j; // debug(i * 2 + 1, j, a, b, dp[i][j] * C(a + b - 1, a)); ADD(ans[i * 2 + 1], dp[i][j] * C(a + b - 1, a) % mod); } } for(int i = 1; i <= K / 2 + 1; i++) { for(int j = 0; j <= N; j++) { if(!dp[i][j]) continue; int a = N - j; int b = K - ((i - 1) * 2 + 1) + j; // debug(i * 2, j, a, b); ADD(ans[i * 2], dp[i - 1][j] * C(a + b - 1, a) % mod); a = N - j - 1; b = K - ((i - 1) * 2 + 1) + j; // debug(i * 2, j, a, b); ADD(ans[i * 2], dp[i - 1][j] * C(a + b - 1, a) % mod); } } // rep(i, 0, 2 * K + 1) { // debug(i, ans[i]); // } for(int i = K + 1; i <= 2 * K; i++) { ans[i] = ans[2 * K + 2 - i]; } for(int i = 2; i <= K * 2; i++) { cout << ans[i] << "\n"; } }
F
pi-1 < pi < pi+1となればpiはこれ以降動けないのでpi=iが成立しないといけないことを中心に考察を進めました。
こういうのは適当にiterationを決めて実験をダラダラしてたら解けることはわかっていたので、時間かけたら解法が降ってきました。
でも速く解こうと思ったらやっぱり性質が他にないか確かめるべきですね。もし数が動き始めたら左右どちらかにしか移動しないことに気づいてなかったのは良くなかったです。問題たくさん解けばこういう性質にもう少し敏感になれるかなぁ。
int N; int A[MAX_N]; bool used[MAX_N]; void solve() { cin >> N; memset(A, -1, sizeof(A)); rep(i, 0, N) { cin >> A[i]; A[i]--; } int lv = -1, uv = -1; for(int i = 0; i < N; i++) { if(uv == -1) { if(A[i] != i) { uv = A[i]; lv = i; if((uv - lv) % 2) { cout << "No\n"; return; } } } else if((uv - i) % 2) { if(A[i] != i) { cout << "No\n"; return; } } else { if(A[i] > uv) { used[uv] = true; uv = A[i]; } else if(lv == A[i]) { used[lv] = true; while(used[lv]) lv += 2; } else { cout << "No\n"; return; } if(lv == uv) { lv = -1, uv = -1; } } } if(lv != -1) cout << "No\n"; else cout << "Yes\n"; }
re_shaさんすごい。めちゃくちゃかしこいですね…。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1314
構文解析といえばこの問題みたいなところあるよね。
まず左再帰を取り除きます。
assignment ::= var "=" expr "."
var ::= "A" | "B" | "C"
expr ::= term expr'
expr' ::= "+" term expr' | "-" term expr' | "e"
term ::= factor term'
term' ::= "*" factor term' | "e"
factor ::= primary | "-" factor
primary ::= inum primary' | var primary' | matrix primary' | "(" expr ")" primary'
primary' ::= "(" expr "," expr ")" primary' | "'" primary' | "e"
matrix ::= "[" row-seq "]"
row-seq ::= row row-seq'
row-seq' ::= ";" row row-seq' | "e"
row ::= expr row'
row' ::= " " expr row' | "e"
inum ::= digit inum'
inum' ::= digit inum' | "e"
digit ::= "0" | "1" | "2"
みたいになります。このBNFがLL1であることを証明します。つまり1文字読むだけで条件分岐が判別できることを示します。
First集合Follow集合は以下になります。First集合は下から、Follow集合は上から求める感じで計算すると楽です。
first(program) = {"A", "B", "C"}
first(program') = {"A", "B", "C"}
first(assignment) = {"A", "B", "C"}
first(var) = {"A", "B", "C"}
first(expr) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(expr') = {"+", "-", "e"}
first(term) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(term') = {"*", "e"}
first(factor) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(primary) = {"0", "1", "2", "A", "B", "C", "[", "("}
first(primary') = {"(", "'", "e"}
first(matrix) = {"["}
first(row-seq) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(row-seq') = {";", "e"}
first(row) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(row') = {" ", "e"}
first(inum) = {"0", "1", "2"}
first(inum') = {"0", "1", "2", "e"}
first(digit) = {"0", "1", "2"}
follow(program) = {"$"}
follow(program') = {"$"}
follow(assignment) = {"A", "B", "C"}
follow(var) = {"=", "(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(expr) = {".", ")", ",", " ", ";", "]"}
follow(expr') = {".", ")", ",", " ", ";", "]"}
follow(term) = {"+", "-", ".", ")", ",", " ", ";", "]"}
follow(term') = {"+", "-", ".", ")", ",", " ", ";", "]"}
follow(factor) = {"*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(primary) = {"*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(primary') = {"*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(matrix) = {"(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(row-seq) = {"]"}
follow(row-seq') = {"]"}
follow(row) = {";", "]"}
follow(row') = {";", "]"}
follow(inum) = {"(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(inum') = {"(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(digit) = {"0", "1", "2", "(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
ここからDirector集合を求めるんですが、'が付いている項にはFirst集合に"e"が含まれてないことがわかります。
なので'がついているもののみについて考えればよくて、
director(program') = {"A", "B", "C"} and {"$"} = empty
director(expr') = {"+", "-"} and {"{", ".", ")", ",", " ", ";", "]"} = empty
directort(term') = {"*"} and {"+", "-", ".", ")", ",", " ", ";", "]"} = empty
director(primary') = {"(", "'"} and {"*", "+", "-", ".", ")", ",", " ", ";", "]"} = empty
director(row-seq') = {";"} and {"]"} = empty
director(row') = {" "} and {";", "]"} = empty
director(inum') = {"0", "1", "2"} and {"(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"} = empty
あとは実装します。返り値をstate(mat, int)みたいにして、行列の値とどこまで解析したかのindexを持つようにしました。indexを持たせずに実装することもできるんですが、それだとデバッグがつらくなります。
あと'の付いている項は全て末尾再帰になっているので実装の際は単なる繰り返しに言い換えました。
string str; string show(int a, int b) { return string(str.begin() + a, str.begin() + b); } map<char, mat> dict; void program(int at); state assignment(int at); state expr(int at); state term(int at); state factor(int at); state primary(int at); state matrix(int at); state rowseq(int at); state row(int at); state inum(int at); void program(int at) { state s = assignment(at); rep(i, 0, sz(s.fst)) { rep(j, 0, sz(s.fst[0])) { cout << s.fst[i][j] << (j != sz(s.fst[0]) - 1 ? " " : "\n"); } } while(s.sec < sz(str)) { s = assignment(s.sec); rep(i, 0, sz(s.fst)) { rep(j, 0, sz(s.fst[0])) { cout << s.fst[i][j] << (j != sz(s.fst[0]) - 1 ? " " : "\n"); } } } // debug("program", show(at, s.sec)); } state assignment(int at) { char c = str[at]; state s = expr(at + 2); s.sec++; dict[c] = s.fst; // debug("assignment", show(at, s.sec)); return s; } state expr(int at) { state s = term(at); mat res = s.fst; while(s.sec < sz(str) && (str[s.sec] == '+' || str[s.sec] == '-')) { if(str[s.sec] == '+') { s.sec++; s = term(s.sec); rep(i, 0, sz(res)) { rep(j, 0, sz(res[0])) { ADD(res[i][j], s.fst[i][j]); } } } else { s.sec++; s = term(s.sec); rep(i, 0, sz(res)) { rep(j, 0, sz(res[0])) { ADD(res[i][j], mod - s.fst[i][j]); } } } } // debug("expr", show(at, s.sec)); return state(res, s.sec); } state term(int at) { state s = factor(at); mat res = s.fst; while(s.sec < sz(str) && str[s.sec] == '*') { s.sec++; s = factor(s.sec); if(sz(res) == 1 && sz(res[0]) == 1) { swap(res, s.fst); } if(sz(s.fst) == 1 && sz(s.fst[0]) == 1) { rep(i, 0, sz(res)) { rep(j, 0, sz(res[0])) { MUL(res[i][j], s.fst[0][0]); } } } else { mat tmp(sz(res), vi(sz(s.fst[0]), 0)); rep(i, 0, sz(res)) { rep(j, 0, sz(s.fst[0])) { rep(k, 0, sz(s.fst)) { ADD(tmp[i][j], res[i][k] * s.fst[k][j] % mod); } } } res = tmp; } } // debug("term", show(at, s.sec)); return state(res, s.sec); } state factor(int at) { state s; if(str[at] == '-') { s = factor(at + 1); rep(i, 0, sz(s.fst)) { rep(j, 0, sz(s.fst[0])) { s.fst[i][j] = (mod - s.fst[i][j]) % mod; } } } else s = primary(at); // debug("factor", show(at, s.sec)); return s; } state primary(int at) { state s; if('0' <= str[at] && str[at] <= '9') { s = inum(at); } else if('A' <= str[at] && str[at] <= 'Z') { s.fst = dict[str[at]]; s.sec = at + 1; } else if(str[at] == '[') { s = matrix(at); } else { s = expr(at + 1); s.sec++; } mat res = s.fst; while(s.sec < sz(str) && (str[s.sec] == '(' || str[s.sec] == '\'')) { if(str[s.sec] == '(') { s.sec++; s = expr(s.sec); mat a = s.fst; s.sec++; s = expr(s.sec); mat b = s.fst; s.sec++; mat tmp(sz(a[0]), vi(sz(b[0]), 0)); rep(i, 0, sz(a[0])) { rep(j, 0, sz(b[0])) { tmp[i][j] = res[a[0][i] - 1][b[0][j] - 1]; } } res = tmp; } else { s.sec++; mat tmp(sz(res[0]), vi(sz(res), 0)); rep(i, 0, sz(res)) { rep(j, 0, sz(res[0])) { tmp[j][i] = res[i][j]; } } res = tmp; } } // debug("primary", show(at, s.sec)); return state(res, s.sec); } state matrix(int at) { state s = rowseq(at + 1); s.sec++; // debug("matrix", show(at, s.sec)); return s; } state rowseq(int at) { state s = row(at); mat res = s.fst; while(str[s.sec] == ';') { s.sec++; s = row(s.sec); mat tmp(sz(s.fst) + sz(res), vi(sz(res[0]), 0)); rep(i, 0, sz(res)) { rep(j, 0, sz(res[0])) { tmp[i][j] = res[i][j]; } } rep(i, 0, sz(s.fst)) { rep(j, 0, sz(s.fst[0])) { tmp[i + sz(res)][j] = s.fst[i][j]; } } res = tmp; } //debug("rowseq", show(at, nat)); return state(res, s.sec); } state row(int at) { state s = expr(at); mat res = s.fst; while(str[s.sec] == ' ') { s.sec++; s = expr(s.sec); mat tmp(sz(res), vi(sz(res[0]) + sz(s.fst[0]), 0)); rep(i, 0, sz(res)) { rep(j, 0, sz(res[0])) { tmp[i][j] = res[i][j]; } } rep(i, 0, sz(s.fst)) { rep(j, 0, sz(s.fst[0])) { tmp[i][j + sz(res[0])] = s.fst[i][j]; } } res = tmp; } // debug("row", show(at, s.sec)); return state(res, s.sec); } state inum(int at) { int res = 0; int nat = at; while(nat < sz(str) && '0' <= str[nat] && str[nat] <= '9') { res *= 10; ADD(res, (str[nat] - '0')); nat++; } // debug("inum", show(at, nat)); return state(mat(1, vi(1, res)), nat); } void solve() { while(true) { int Q; cin >> Q; if(Q == 0) break; str.clear(); dict.clear(); string s; getline(cin, s); while(Q--) { getline(cin, s); str += s; } program(0); cout << "-----\n"; } }
https://beta.atcoder.jp/contests/arc101
本番解けないと意味ないってそれ一番。
コンテスト中は1完です…
C
K個の連続した区間になるので適切に計算すればO(N)。
D
本番誤読してかなしぃ。中央値はやっぱりにぶたんなんだよなぁ。
https://agc006.contest.atcoder.jp/tasks/agc006_d
これっぽいですね。
ll N; ll A[MAX_N]; int S[MAX_N]; pi P[MAX_N]; bool ok(ll m) { rep(i, 0, N) { if(A[i] <= m) S[i + 1] = 1; else S[i + 1] = -1; } // debug(m, vi(S + 1, S + N + 1)); rep(i, 0, N) { S[i + 1] += S[i]; } rep(i, 0, N + 1) { P[i] = pi(S[i], -i); } sort(P, P + N + 1); ll res = 0; BIT bit(N + 1); rep(i, 0, N + 1) { int at = P[i].sec * -1; bit.update(at, at + 1, 1); res += bit.get(0, at); } return res > N * (N + 1) / 4; } void solve() { cin >> N; rep(i, 0, N) cin >> A[i]; ll lv = 0, rv = inf; while(rv - lv > 1) { ll m = (lv + rv) / 2; if(ok(m)) rv = m; else lv = m; } cout << rv << "\n"; }
E
dp[v][a]:=根がvの木で余ってる辺がk本の時とすると、
dp[v][a+b-2k]:=dp[c1][a]*dp[c2][b]*C(a,k)*C(b,k)とかになって、なんとかまとめればできそうな形になりますが全然できません。本番もこれでめちゃくちゃハマりました。
なのでこの考えから離れましょう。包除を思いつけるとあとはそんな難しくないです。
木dpの書き方も忘れてたのでよい練習になりました。
int N; vector<int> G[MAX_N]; ll dp[5010][5010][2]; ll ep[5010][5010][2]; ll pow2inv[5010]; int loop(int v, int p) { int sz = 1; dp[v][1][0] = 1; rep(q, 0, sz(G[v])) { int n = G[v][q]; if(p == n) continue; int ts = loop(n, v); rep(i, 0, sz + ts + 1) { rep(j, 0, 2) { ep[v][i][j] = 0; } } rep(i, 0, sz + 1) { rep(j, 0, ts + 1) { rep(k, 0, 2) { rep(l, 0, 2) { ADD(ep[v][i + j][(k + l) % 2], dp[v][i][k] * dp[n][j][l] % mod); } } } } rep(i, 0, sz + ts + 1) { rep(j, 0, 2) { dp[v][i][j] = ep[v][i][j]; } } sz += ts; } for(int i = 0; i <= sz; i += 2) { rep(j, 0, 2) { ADD(dp[v][0][(j + 1) % 2], dp[v][i][j] * fac[i] % mod * pow2inv[i / 2] % mod * fiv[i / 2] % mod); } } return sz; } void solve() { cin >> N; C_init(N); rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } pow2inv[0] = 1; rep(i, 0, N) { pow2inv[i + 1] = pow2inv[i] * inv[2] % mod; } loop(0, -1); cout << (dp[0][0][1] - dp[0][0][0] + mod) % mod << "\n"; }
F
解説とだいぶ違った。
ロボットの出口との距離を(a,b)とします。座標の点をグラフにして、0から正の方向負の方向に辺を張ります。
それから(a->b)または(b->a)の辺を張ってグラフ全体がトポロジカルソートができることが条件になります。
トポロジカルソートができる<=>ループが存在しない<=>(a,b)(c,d)の組であってa<=c,b<=dを満たし、a->b,d->cに辺を張るものが存在しない
と言い換えられます。ここまでくればあとはBITで数え上げられます。
でも解説の2次元座標の言い換えができたほうが絶対良かったよなぁ。
int N, M; ll X[MAX_N], Y[MAX_N]; ll L[MAX_N], R[MAX_N]; vl vec; vl Q[MAX_N]; int fd(ll v) { return lower_bound(all(vec), v) - vec.begin(); } void solve() { cin >> N >> M; rep(i, 0, N) cin >> X[i + 1]; rep(i, 0, M) cin >> Y[i + 1]; X[0] = -linf; Y[M + 1] = linf; int at = 1; rep(i, 0, N) { while(X[i + 1] > Y[at]) at++; if(at != M + 1) R[i] = Y[at] - X[i + 1]; else R[i] = linf; vec.pb(R[i]); } at = M; rer(i, N, 0) { while(X[i + 1] < Y[at]) at--; if(at != 0) L[i] = X[i + 1] - Y[at]; else L[i] = linf; vec.pb(L[i]); } vec.pb(linf); sort(all(vec)); // debug(vl(L, L + N)); // debug(vl(R, R + N)); vec.erase(unique(all(vec)), vec.end()); rep(i, 0, N) { int lat = fd(L[i]), rat = fd(R[i]); Q[lat].pb(rat); } rep(i, 0, sz(vec)) { sort(all(Q[i])); Q[i].erase(unique(all(Q[i])), Q[i].end()); } BIT bit(sz(vec)); bit.update(sz(vec) - 1, sz(vec), 1); rer(i, sz(vec) - 1, 0) { rep(j, 0, sz(Q[i])) { int b = Q[i][j]; ll v = bit.get(b + 1, sz(vec)); // debug(vec[i], vec[b], v); bit.update(b, b + 1, v); } } cout << bit.get(0, sz(vec)) << "\n"; }
