AOJ 1314

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

となります。全て空集合なのでこのBNFはLL1です。

あとは実装します。返り値を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";
    }
}

ARC101

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";
}

AOJ 2255

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255

優先順位が低い演算子から再帰していく感じでやればいいです。例えば演算子の優先順位が(),/,*,-,+だったら、

expr0::=expr0 + expr0 | expr1
expr1::=expr1 - expr1 | expr2
expr2::=expr2 * expr2 | expr3
expr3::=expr3 / expr3 | expr4
expr4::=(expr0) | num
のようにすればいいです。左再帰を解消すると、
expr0::=expr1 + expr0'
expr0'::=+ expr0 expr0' | empty
のようになって、LL(1)になるので簡単に実装できます。

int K;
string str;
string strs;
int signat[20];
char csign[4] = {'+', '-', '*', '/'};

pi expr(int type, int at);
pi num(int at);

pi expr(int type, int at) {
	if(type == K) {
		if(str[at] == '(') {
			pi p = expr(0, at + 1);
			p.sec++;
			return p;
		}
		else {
			pi p = num(at);
			return p;
		}
	}
	else {
		pi p1 = expr(type + 1, at);
		if(p1.sec < sz(str) && str[p1.sec] == char(type + 'a')) {
			pi p2 = expr(type + 1, p1.sec + 1);
			if(p1.fst == inf || p2.fst == inf) return pi(inf, p2.sec);
			if(strs[p1.sec] == '+') {
				return pi(p1.fst + p2.fst, p2.sec);
			}
			else if(strs[p1.sec] == '-') {
				return pi(p1.fst - p2.fst, p2.sec);
			}
			else if(strs[p1.sec] == '*') {
				return pi(p1.fst * p2.fst, p2.sec);
			}
			else {
				if(p2.fst == 0) return pi(inf, p2.sec);
				else return pi(p1.fst / p2.fst, p2.sec);
			}
		}
		else return p1;
	}
}

pi num(int at) {
	int res = 0;
	while('0' <= str[at] && str[at] <= '9') {
		res *= 10;
		res += (str[at] - '0');
		at++;
	}
	return pi(res, at);
}

void solve() {
	while(true) {
		cin >> str;
		strs = str;
		if(str == "#") break;
		K = 0;
		rep(i, 0, sz(str)) {
			rep(j, 0, 4) {
				if(str[i] == csign[j]) {
					signat[K++] = i;
				}
			}
		}
		vector<int> vec(K, 0);
		rep(i, 0, K) vec[i] = i;
		set<int> S;
		do {
			rep(i, 0, K) {
				str[signat[i]] = char('a' + vec[i]);
			}
			S.insert(expr(0, 0).fst);
		} while(next_permutation(all(vec)));
		if(S.count(inf)) cout << sz(S) - 1 << "\n";
		else cout << sz(S) << "\n";
	}
}

AOJ 1155

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155&lang=jp

構文解析おもしろいじゃーん。

関数の返し値をpair ( (値),(どこまで解析したか) )にして、引数を(どこから解析するか)にすれば簡単に実装できます。
今回は
formula:=-formula|(formula*formula)|(formula+formula)|0|1|2|P|Q|R
となっていて、左再帰がないので本当にそのまま実装すればいいです。

string str;
int neg[3] = {2, 1, 0};
int mul[3][3] = {
	{0, 0, 0},
	{0, 1, 1},
	{0, 1, 2}
};
int add[3][3] = {
	{0, 1, 2},
	{1, 1, 2},
	{2, 2, 2}
};

int A[3];

pi formula(int at);
pi two(int at);

pi formula(int at) {
	if(str[at] == '-') {
		pi p = formula(at + 1);
		p.fst = neg[p.fst];
		return p;
	}
	else if(str[at] == '(') {
		pi p1 = formula(at + 1);
		pi p2 = formula(p1.sec + 1);
		if(str[p1.sec] == '*') {
			return pi(mul[p1.fst][p2.fst], p2.sec + 1);
		}
		else {
			return pi(add[p1.fst][p2.fst], p2.sec + 1);
		}
	}
	else if('0' <= str[at] && str[at] <= '2'){
		return pi(str[at] - '0', at + 1);
	}
	else {
		return pi(A[str[at] - 'P'], at + 1);
	}
}

void solve() {
	while(true) {
		cin >> str;
		if(str == ".") break;
		int cnt = 0;
		rep(i, 0, 3) {
			rep(j, 0, 3) {
				rep(k, 0, 3) {
					A[0] = i;
					A[1] = j;
					A[2] = k;
					if(formula(0).fst == 2) cnt++;
				}
			}
		}
		cout << cnt << "\n";
	}
}

AOJ 2021

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021&lang=jp

は?これも難しくないか?
普通にO(MN)頂点O(MN^2)辺のグラフでダイクストラすればいいんですが、これだと若干重くないか?ということで、O(N^3)解法にしました。

Aから中継点を数カ所挟んでHに行くわけですが、その間、距離M以上は移動できません。
逆にこの条件さえ満たしていれば、AからHへの最短距離をdとして、答えはmax(d, 2d-M)です。
なぜかというと、d<=Mの時は答えがdになることは言うまでもなく、d>Mのとき、d-Mだけ補給しなければなりません。よって答えの下界はd+(d-M)=2d-Mになるわけですが、これは達成できます。max(d,2d-M)はd<=Mのとき、d>Mのときで答えと一致します。
あとはワーシャルフロイドを2回やればいいです。1回目は、全頂点間で、2回目はAとHと中継点で長さがMより大きい辺を除いたグラフで行います。

しかしダイクストラより遅くてかなしぃ。

int N, M, L, K, A, H;
bool blood[110];
ll d[110][110];
ll e[110][110];

void solve() {
	while(true) {
		cin >> N >> M >> L >> K >> A >> H;
		debug(K);
		if(N == 0) break;
		memset(blood, 0, sizeof(blood));
		rep(i, 0, L) {
			int a; cin >> a;
			blood[a] = true;
		}
		blood[A] = true; blood[H] = true;
		rep(i, 0, N) {
			rep(j, 0, N) {
				d[i][j] = inf;
				e[i][j] = inf;
			}
		}
		while(K--) {
			int a, b; ll c;
			cin >> a >> b >> c;
			MIN(d[a][b], c);
			MIN(d[b][a], c);
		}
		rep(k, 0, N) {
			rep(i, 0, N) {
				rep(j, 0, N) {
					MIN(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
		rep(i, 0, N) {
			rep(j, 0, N) {
				if(blood[i] && blood[j] && d[i][j] <= M) {
					e[i][j] = d[i][j];
				}
			}
		}
		rep(k, 0, N) {
			rep(i, 0, N) {
				rep(j, 0, N) {
					MIN(e[i][j], e[i][k] + e[k][j]);
				}
			}
		}
		if(e[A][H] == inf) {
			cout << "Help!\n";
		}
		else {
			cout << max(2 * e[A][H] - M, e[A][H]) << "\n";
		}
	}
}

AOJ 2011

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011&lang=jp

は?むずくないか?
DPできないと思ったので、貪欲でやりました。
うしろから見ます。k日間でできるとします。k日目スケジュールが入っている人の集合をSとします。k-1日目でSに全部の地図が集まれば良いです。k-1日目にスケジュールが入っている人の集合をUとします。もし、Sの要素vの中でUに含まれるものがあったら、Uに含まれる人はvに地図を全て渡せばよいです。なのでS=S∪Uとupdateしてk-2...1日目まで再帰的に計算します。Sに全ての人が含まれていれば成功です。

Codeforces Round #503 (by SIS, Div. 1)

https://codeforces.com/contest/1019

Aで無限に時間を使ってしまい、絶望的だったので撤退…いやでも今後のためにも提出したほうがよかったかなぁ…

A
普通に勝たせる人に何票入れるかで全探索すれば良いんですが、いろいろこんがらがってしまいだめでした…
B
真面目に読んでないんですけど、どうせ二分探索です。
C
1点について見てから、適当に頂点を削除して、再帰的に構成するっていうのを本番も思いついたんですが、形にはできず…
結局2-SATに流れてしまいました…でも2-SATでもO(M)個の値のorが必要だったのでできなさそうです。
あとn=10^6の時は本当に単純じゃないとTLEするので注意です。今回も対して複雑ではないけど1824ms/2000msとかだったので。

できることを素早くできるようになって、できないことを判断できるようになったらだいぶ良くなりそう。