読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

JAG 夏合宿 Day2 A - Parades

AtCoder
問題

jag2016summer-day2.contest.atcoder.jp

N 頂点からなる木がある。各頂点の次数はたかだか 10 である。

このグラフ上でいくつかのパレードを開きたい。パレードの候補は M 個あり, その各パレードは頂点 u から 頂点 v へのパスで構成される。
これらのパレードは同時開催するため, 開くパレードはすべてパスの辺を共有していてはならない。最高でいくつのパレードを開けるかを求めよ。

解法

藤原さんの解答を参考にしました。

基本的には木 DP で, dp[v][s] = (頂点 v から伸びている辺のうち, s で表される集合の辺は使ったときに開催できるパレードの数の最大値) とします。

パレードはパスで表されるので, u, v の lca で特徴づけることができます。u -> lca -> v と移動する場合, lca では u 側に降りるために使う辺と v 側に降りるために使う辺を消費します。この辺が lca にとって x 番目, y 番目の辺であった場合,
dp[lca][s|(1< lca -> v みたいなパスが候補になったとして, そのパス自体でパレードの数は +1 されますが, そのパス上で行われていたパレードの数がどうなるかを考慮する必要があります。これをいちいち計算していると O(nm) 以上の計算量がかかりそうなのでアウトです。

ということで工夫をする必要があるわけですが, この木 dp は明らかに葉のほうから先にやっていきます。「末端が u であるようなパス」というのは lca -> u というように書けるわけですが, この lca はこれから先どんどん上に伸びていくだけなので, 「今調べている段階で u を終着点とするようなパスでどれだけのパレードを開けているか」というようなものを考えれば良いことになります。下のコードでこれをやっているのは S[v] というやつです。今までのパスの上に一つ頂点がつくことによってパレードの回数が更新される, という感じです。

あと問題なのは 各頂点に対して, その頂点を lca とするものは最高で O(n) 個考えられ, bitDP やってるときにいちいちやっていると O(n^2 2^10) かかって死ぬ, という問題があります。しかしあらかじめ M[x][y] = (頂点 lca で x 本目, y 本目の辺を使う場合に最大で開けるパレードの数) を前計算しておくとこれは大丈夫になります。

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		vector<vi> G(N);
		for (int i = 0; i < N-1; i++) {
			int a, b;
			cin >> a >> b;
			a--; b--;
			G[a].push_back(b);
			G[b].push_back(a);
		}
		// 木についていろいろメモ
		// 頂点を調べる順番
		vector<int> T(N);
		// 子
		vector<vi> chs(N);
		// 親
		vector<int> par(N);
		// 深さ
		vector<int> d(N);
		{
			d[0] = 1;
			par[0] = -1;
			int k = 0;
			queue<int> que;
			que.push(0);
			while (!que.empty()) {
				int now = que.front(); que.pop();
				T[k++] = now;
				for (int ch : G[now]) {
					if (!d[ch]) {
						par[ch] = now;
						chs[now].push_back(ch);
						d[ch] = d[now] + 1;
						que.push(ch);
					}
				}
			}
		}
		// anc[v][u] = v, u の LCA
		vector<vi> anc(N, vi(N));
		for (int i = 0; i < N; i++) {
			int v = T[i];
			for (int j = 0; j < N; j++) {
				int u = T[j];
				if (v == u) {
					anc[v][u] = v;
				}
				else if (d[v] > d[u]) {
					anc[v][u] = anc[par[v]][u];
				}
				else if (d[v] < d[u]) {
					anc[v][u] = anc[v][par[u]];
				}
				else if (d[v] > 1) {
					anc[v][u] = anc[par[v]][u];
				}
				else {
					anc[v][u] = 0;
				}
			}
		}
		vector<vi> dir(N, vi(N));
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
			int v = T[i], u = T[j];
			if (v != u && anc[v][u] == v) {
				for (int x = 0; x < chs[v].size(); x++) {
					int w = chs[v][x];
					if (anc[w][u] == w) {
						dir[v][u] = x;
						break;
					}
				}
			}
		}
		vector<vector<pii> > V(N);
		int M;
		cin >> M;
		for (int i = 0; i < M; i++) {
			int a, b;
			cin >> a >> b;
			a--; b--;
			int lca = anc[a][b];
			V[lca].emplace_back(a, b);
		}
		// dp
		vector<vi> dp(N, vi(1<<10));
		vi S(N);
		for (int t = N-1; t >= 0; t--) {
			int v = T[t];
			vi M1(10);
			vector<vi> M(10, vi(10));
			for (pii des : V[v]) {
				int a = des.first, b = des.second;
				if (a == v) {
					int x = dir[v][b];
					M1[x] = max(M1[x], S[b]+1);
				}
				else if (b == v) {
					int x = dir[v][a];
					M1[x] = max(M1[x], S[a]+1);
				}
				else {
					int x = dir[v][a], y = dir[v][b];
					M[x][y] = max(M[x][y], S[a] + S[b] + 1);
				}
			}
			int G = 0;
			for (int ch : chs[v]) {
				G += dp[ch][(1<<chs[ch].size())-1];
			}
			dp[v][0] = G;
			int sz = chs[v].size();
			for (int s = 0; s < 1<<sz; s++) {
				for (int x = 0; x < sz; x++) {
					if ((s>>x)&1) continue;
					dp[v][s|(1<<x)] = max(dp[v][s|(1<<x)], dp[v][s]);
					int ch = chs[v][x];
					dp[v][s|(1<<x)] = max(dp[v][s|(1<<x)], dp[v][s] + M1[x] - dp[ch][(1<<chs[ch].size())-1]);
					for (int y = 0; y < sz; y++) if (x != y && ((s>>y)&1) == 0) {
						int ch2 = chs[v][y];
						dp[v][s|(1<<x)|(1<<y)] = max(dp[v][s|(1<<x)|(1<<y)], dp[v][s] + M[x][y] - dp[ch][(1<<chs[ch].size())-1] - dp[ch2][(1<<chs[ch2].size())-1]);
					}
				}
			}
			int All = (1<<sz)-1;
			for (int des = 0; des < N; des++) {
				if (des != v && anc[v][des] == v) {
					int x = dir[v][des];
					int ch = chs[v][x];
					S[des] += dp[v][All^(1<<x)] - dp[ch][(1<<chs[ch].size())-1];
				}
			}
			S[v] = dp[v][(1<<sz)-1];
		}
		cout << dp[0][(1<<chs[0].size())-1] << endl;
	}
	return 0;
}

院試(東京大学大学院情報理工工学研究科 システム情報学 2016)

院試の受験記です。なんかの参考になれば。

準備編

試験は

  • 英語(TOEFL ITP)
  • 数学
  • 専門
  • 面接

があります。日程的に英語 -> (しばらく間が空く) -> 数学 -> 専門 -> 面接 でした(数学と専門は同じ日にやってほしい感)。

噂によると筆記試験(面接以外)でほぼ結果は決まっていて, その 3 科目の配点は 1:1:2 とからしいです。1:2:2 という噂もあります(ホントかは知りません)。

自分のやったお勉強について書きたいと思います。ここからめっちゃ Amazon ラッシュ。
ただ内部生の立場で書いているので外部にはあまり参考にならないかもしれません。

英語

まず TOEFL iBT を事前に受けるか 決められた日程に TOEFL ITP を受けるかを選択できますが, iBT は受験料がクッソ高い(たしか 2 万円とか)し難しいので, ITP のほうが良いと思います。

とりあえず問題内容を知っているのと知らないのでは 50 点くらい違いがあると思うので, それは予習しておきましょう。

はじめて受けるTOEFL ITP TEST総合対策 (<CD+テキスト>)

はじめて受けるTOEFL ITP TEST総合対策 ()

  • 作者: 島崎美登里,ポール・ワーデン,ロバート・ヒルキ
  • 出版社/メーカー: 語研
  • 発売日: 2010/03/16
  • メディア: 単行本(ソフトカバー)
  • 購入: 1人 クリック: 3回
  • この商品を含むブログを見る

本番のリスニングはこれの 114514 倍速かったのでそこは別に対策した方が良いかもしれません。僕は全く聞き取れませんでした。

後文法は対策が非常に簡単で, 3 日くらい詰め込めば 8 割は余裕で取れるようになるのでそのために 1 冊買いました。

全問正解するTOEFL ITP TEST文法問題対策 ([テキスト])

全問正解するTOEFL ITP TEST文法問題対策 ([テキスト])

数学

線形代数と解析と確率が出るそうです。

数学に関しては公式ページに過去問があるのでそれをやっていれば良い点取れそうです。

線形代数は何も言わなくてもできそう。

解析は内部生なら数力演習のノート見直せば良さそうです(これで完璧に対策出来るとは言っていない)。

確率に関しては確率分布っぽい話と大学入試か?みたいのが混ざっています。内部生なら確率数理工学のノートを見返せば確率分布っぽいのが出たときの対策ができます。

専門

信号処理, 回路, 制御, コンピュータ, 力学 から 1 問ずつでて, その中から 3 問を解答します。これも公式ページに過去問があるのでそれで練習できます。ただ 2013 くらいからフォントがひどい(読めない)のがあるので文句言った方が良いと思います(僕は内部生なのでちゃんとした問題文を共有できたので問題なかったですが)。

信号処理は毎回狭く, 深く問うてくるイメージなので過去問解いても意味なさそうだし, 普通に難しいので僕は選択する気 0 でした。大学では信号処理論第一, 第二というのがあって, 第一の範囲はおおよそやる夫で勉強することができます。
www.ic.is.tohoku.ac.jp

今年の範囲は第二っぽかったです。第二の内容についてはよく知りません。

回路は毎年オペアンプが出ています。今年も毛色が若干変わったけど出ました。オペアンプを使った回路, 発振回路あたり勉強すれば良いのではないでしょうか。

制御は信号処理と違って毎年だいたい安定した問題が出ています。最近は古典制御の中にこっそり現代制御を仕込むみたいな形式が多かったですが, 今年は堂々と現代制御を出していました。下の 2 冊勉強すれば十分な気がします。

演習で学ぶ基礎制御工学

演習で学ぶ基礎制御工学

演習で学ぶ現代制御理論

演習で学ぶ現代制御理論

コンピュータは…よくわからないので過去問だけやってました。今年はシミュレータでやれ💢💢というようなアセンブリを読まされる問題(再帰関数っぽかった)が出てよくわかりませんでしたが普段は結構簡単だと思います。暇だったらコンピュータの構成と設計でも読んでればよいのではないでしょうか。

コンピュータの構成と設計 第5版 上

コンピュータの構成と設計 第5版 上

力学はクッソ簡単な時があるのでそうだったら解こう, という感じで選択するつもりでした。1 年生の時に使ってた演習書が出てきたのでそれを使って一部勉強しました。

演習力学 (セミナーライブラリ物理学 (2))

演習力学 (セミナーライブラリ物理学 (2))

当日編

英語

リスニングで MP を使い果たす懸念をしていましたが全く聞き取れず MP を消費しなかったので他は計画通り解けました。
多分 リスニング 4 割, 文法 9 割, 長文 7 割くらいだと思います。

数学

「簡単すぎて差がつかない」と言っている人とそれを見て「ハーキレソー」と言ってる人がいました。
満点の自信は多少アリ。

専門

全然できなかったんですが周りも阿鼻叫喚だったので今年はそんな感じだったんだろうという感じでした。
5 割くらい?

追記

点数開示しました。300 円かかるのであんまりやりたくなかったんですが, 結局数学満点で自慢できたので良かったです(小並感)。

f:id:mayokoex:20161229102024j:plain

面接

ほとんどの人がスーツでした。

を聞かれました。

テクニカルタームで聞かれたというので覚えてるのを(他の人のも含めて)あげていくと,

  • ヤコビ行列
  • サンプリング定理
  • ゼロ位法
  • ナイキストの安定判別
  • 主成分分析
  • 投資投影
  • SN 比

とかでした。

まとめ

JAG 夏合宿に参加しました

楽しかったです。

前日

  • 家で高速回転したり奇声を発したりしながら楽しみにしてました。

1 日目

  • と言ってもシャイなのでビクビクしながら会場入りしました。
  • 自己紹介でクソなぞなぞに言及したところ結構知られてるイメージでした。うれしい。
  • ゆらふなさんと初めて会いました。これもうれしい。
  • 懇親会。いろいろな人と話せて楽しかった。寿司はほとんど食べれなかった。egg fire。

2 日目

  • 朝ごはんのブルーベリーゼリーが異様に濃い紫色でビビった(名物らしい)。
  • コンテストは btk さん, たわしさんと組んだ。
  • チーム全体で解いたのは C, D, H, I。
    • C は btk さんが謎 TLE(入力がクソだった)を連発していて, 代わりに書いてみたら通った。
    • D は問題読んで行けると思ったけど x/y の x, y が巨大になると勘違いした(実際には最初の歯車との比のみで決まるのでそんなことはない)のでたわしさんに実装を投げた。
    • H, I はいつの間にか AC してた。
    • 最後に F を通そうと思ったけど for 文のミスで死んだ。for 文は 1 行 に 1 個書くようにすれば防げるバグだったのですみませんという感じ。
    • 解説聞いて L はなるほどという感じだった。
    • 後で A は通したいぞい

3 日目

  • コンテストは btk さん, 紺青さんと組んだ。in LINE
  • ABCDE を解いた。
    • A 読んで自明と思いながら通す。B も自明だったっぽい?
    • C がつらくてつらいつらい言ってる間にプロたちが D, E を通す
    • C 通った後いつの間にか F の考察が進んでいたらしいく取り残されながら F のデバッグを眺めて終了。
    • F はもうちょっとでした。
  • このころからすごい勢いでクソなぞなぞが量産されていました。個人的には snuke さんのクソなぞなぞが全体的に面白いと思います。
  • AGC で激冷えした。逆に writer さんに申し訳ない感ある。

4 日目

  • snuke さんのクソなぞなぞ日記が面白かった。そのあと悔しくて何個か駅を見て考えたけどあんまりおもしろいのは思いつかなかった。
  • コンテストは btk さん, yurahuna さんと組んだ。in 六本木ヒルズ
    • ACDFHJL を解きました。
    • C は自明っぽい?(見てない) D は二分探索が嘘であることに気付いて O(N log^2 N) すれば OK
    • L は知らんけど通してた
    • A は後ろから見てけば良いんだけど O(N^3) しか思いつかなかったから yurahuna さんに投げたらいけそうな雰囲気にしてもらえたので投げた(そのあと大変そうだったけどなんとか通してた)
    • F は各頂点で最短経路木を作ってほげる
    • H は読めれば簡単
    • J は dp[A] = (a の配列で合計を A にしたときの, b の配列側の最小値, およびそのとき選んだ集合) みたいのを更新していけば良い(btk さんと相談して出来た)
    • I はほとんど 1/2 の確率で勝つとすると絶対に勝てる方法を btk さんが思いついたけど普通にアンチケースがあったっぽく死。後から聞いたら UMEKOMI すれば行けそうだった。
  • コンテスト終わった後集まった人で築地に行って海鮮丼を食べた。いろいろ話せたし良かった。



まとめ

AIM Tech Round 3 (Div. 1) C. Centroids

CodeForces
問題

codeforces.com

頂点数 n の木 T 上の点 v が T の centorid であるとは, T から v を取り除いて得られる任意の連結成分が, 全て頂点数 n/2 以下であることを言う。

各頂点について, その頂点が以下の操作を一回以下許したとき centroid になるかどうかを判定せよ。
操作:木のある辺を消して, 好きな辺を加える(ただし新しいグラフも連結でなければならない)。

解法

操作を許さない場合にどうなるかを考えます。この場合はかなり単純です。頂点 v から伸びる辺の頂点から構成される部分木が, 全て n/2 以下の連結成分で構成されているか判定すれば良いです。いちいち頂点 v を根にして木dp しているとまにあわないですが, 0 を頂点にした木のみを考えて, 親方向側の連結成分の個数は n - (v の部分木のサイズ) というようにすれば良いです。

次に操作を許す場合を考えます。頂点 v の部分木でサイズが n/2 より大きいものがあった場合, その部分木の一部を切り取って v に直接つなぎかえるのが最適です。ここで部分木の頂点 ch で 2 通りの場合分けをします。

0 を根とした木でも ch が v の子である場合
この場合は, ch 以下の部分木を単純に調べるだけで良いので, euler_tour とか用意しておいてその中で部分木のサイズが n/2 である最大のものを求めます。ch の部分木のサイズ - この部分木のサイズ が n/2 以下なら操作をして centroid になることになります。

0 を根とした木で ch が v の親である場合
この場合がややこしいです。さらに二通りに分けます。

・つなげる木が v の祖先である場合
この場合, v からつなぎなおす頂点を a とすると, v - ch の木は,

  • (a の部分木サイズ) - (v の部分木サイズ) の木
  • n - (a の部分木サイズ) の木

に別れることがわかります。 n - (a の部分木サイズ) が n/2 以下で最大のものを覚えておけばこの中で (a の部分木サイズ) - (v の部分木サイズ) が n/2 以下になるものがあるかは, O(1) でわかります。

・つなげる木が v の祖先でない場合(要するに v の祖先の子孫のうち v の部分木以外のやつ)
木dp するとき dfs から抜け出すタイミングで部分木のサイズのメモしていくと, 頂点 v にたどり着いたときにメモされているのは, v 祖先の子孫の部分木のサイズのみになっています(直接の先祖はまだ v が子にあるので dfs から抜けておらず, サイズがメモされていない)。

よって, 部分木のサイズが n/2 以下なら 部分木のサイズをメモする, というようにやれば同じようにできます。

この手法でやるときは一回 dfs した後もう一回グラフを逆順にして再び dfs しなければいけないことに注意です。

// セグメント木(RMQ 対応)
// update: k 番目の値を a に変更
// query: [l, r) の区間の最大値を求める
template<typename T>
struct ST {
    vector<T> seg;
    int size;
    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(2*size-1, 0);
    }
    inline T merge(T x, T y) {
        return max(x, y);
    }
    void update(int k, T a) {
        k += size-1;
        seg[k] = a;
        while (k > 0) {
            k = (k-1)/2;
            seg[k] = merge(seg[k*2+1], seg[k*2+2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        T vl = query(a, b, k*2+1, l, (l+r)/2);
        T vr = query(a, b, k*2+2, (l+r)/2, r);
        return merge(vl, vr);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

const int MAXN = 400400;
vi G[MAXN];

// Euler-Tour
const int MAXSIZE = MAXN;
int BEGIN[MAXSIZE], END[MAXSIZE];
vector<int> euler_tour;
int K;

void createEulerTour(int v, int p) {
    BEGIN[v] = K++;
    euler_tour.push_back(v);
    for (int el : G[v]) {
        if (el == p) continue;
        createEulerTour(el, v);
        euler_tour.push_back(v);
        K++;
    }
    END[v] = K;
}

int subSize[MAXN];
pii maxi[MAXN];
int n;

int getSize(int v, int p) {
    int& ret = subSize[v];
    pii& ma = maxi[v];
    ma.first = 0, ma.second = -1;
    for (int ch : G[v]) if (ch != p) {
        int tmp = getSize(ch, v);
        if (ma.first < tmp) {
            ma.first = tmp;
            ma.second = ch;
        }
        ret += tmp;
    }
    ret++;
    int tmp = n - ret;
    if (ma.first < tmp) {
        ma.first = tmp;
        ma.second = p;
    }
    return ret;
}

int ans[MAXN];
int tsize;

void dfs(int v, int p, ST<int>& seg, int top) {
    //cout << v << " " << top << " " << tsize << endl;
    if (maxi[v].second == p) {
        if (subSize[top]-subSize[v] <= n/2) ans[v] = 1;
        else if (n-subSize[v]-tsize <= n/2) ans[v] = 1;
    } else {
        int ch = maxi[v].second;
        int tmp = seg.query(BEGIN[ch]+1, END[ch]);
        if (maxi[v].first - tmp <= n/2) ans[v] = 1;
    }
    if (n - subSize[v] <= n/2) top = v;
    for (int ch : G[v]) if (ch != p) {
        dfs(ch, v, seg, top);
    }
    if (subSize[v] <= n/2) tsize = max(tsize, subSize[v]);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    // 部分木のサイズを求める
    getSize(0, -1);
    // euler tour して部分木のサイズをメモ
    createEulerTour(0, -1);
    ST<int> seg(euler_tour.size());
    for (int i = 0; i < n; i++) {
        if (subSize[i] > n/2) {
            seg.update(BEGIN[i], 0);
        } else {
            seg.update(BEGIN[i], subSize[i]);
        }
    }
    dfs(0, -1, seg, 0);
    tsize = 0;
    for (int i = 0; i < n; i++)
        reverse(G[i].begin(), G[i].end());
    dfs(0, -1, seg, 0);
    for (int i = 0; i < n; i++) {
        cout << ans[i] ;
        if (i < n-1) cout << " ";
    }
    cout << endl;
    return 0;
}

AIM Tech Round 3 (Div. 1) B. Recover the String

CodeForces
問題

codeforces.com

0, 1 のみから構成される文字列で, 以下を満たすものを作れ。

  • 00 の部分文字列が a00 個ある
  • 01 の部分文字列が a01 個ある
  • 10 の部分文字列が a10 個ある
  • 11 の部分文字列が a11 個ある

連続部分文字列ではないことに注意。

解法

0 が n 個あるとすると, 00 の部分文字列は n*(n-1)/2 個あります。これから n がほとんど一意に決められます(n = 0 と n = 1 は区別できない)。
同様に a11 の情報から 1 の個数 m をほとんど一意に決められます。

0, 1 の区別はめんどくさいので, for 文で n+i, m+j を調べることにしましょう。以下では n, m は一意に確定したとします。

01, 10 の部分文字列は合計で n*m 個あります。a01 の個数から考えていくとすると, 0 の後に 1 が m 個続くようなものがいくつあるか, 1 が m-1 個続くようなものがいくつあるか, というように順番に調べていけば必ず所望の文字列が見つかることが分かります。

const string no = "Impossible";

string calc(vi a, int n, int m) {
    if (n*(n-1)/2 != a[0]) return no;
    if (m*(m-1)/2 != a[3]) return no;
    if (a[1] + a[2] != n*m) {
        return no;
    }
    if (n == 0 && m == 0) return "0";
    string ret;
    for (int i = m; i > 0 && a[1] > 0; i--) {
        int x = a[1] / i;
        a[1] %= i;
        for (int j = 0; j < x; j++) {
            ret += '0';
            n--;
        }
        ret += '1';
        m--;
    }
    for (int i = 0; i < m; i++)
        ret += '1';
    for (int i = 0; i < n; i++)
        ret += '0';
    return ret;
}

string solve() {
    vi a(4);
    for (int i = 0; i < 4; i++)
        cin >> a[i];
    int n = 0;
    while (n*(n-1)/2 < a[0])
        n++;
    int m = 0;
    while (m*(m-1)/2 < a[3])
        m++;
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
        string t = calc(a, n+i, m+j);
        if (t != no) return t;
    }
    return no;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}

AOJ 2439 Hakone

AOJ
解法

まず, '-' があるところは順位が一意的に決まるので, 無視して良いです。与えられる文字列は 'U' と 'D' しか含まれないものとしましょう。

そしたら dp します。問題では今の中継地点での i 位の人が, 前の中継地点では何位なのかの場合の数を求めれば良いわけですが, 雰囲気としては以下のような戦略を取ります。

  • C[i] = 'D' なら, [0, i) に所望のチーム(順位が落ちてきたチーム)がないとおかしいので, ここで C[i] に対応するチームを確定させる
  • C[i] = 'U' なら, まだ所望のチームはどこかよくわからないので, 放っておく

具体的には以下のようにやります。

dp[i][j][k] = (i 番目まで見て, j チームはまだどこに割り当てられるか確定しておらず, k チーム割当先が残っているような場合の数) とします。割当先が残っている k チームというのは, C[l] = 'U' だったようなもので, まだどうしようか決めてないやつですね。

dp[0][0][0] = 1 であり, dp[n][0][0] が求めるべき値です。

このとき, dp[i][j][k] からは以下のように遷移します。

  • C[i] == 'D' の時,
    • 割当先が決まっていない j チームの中から C[i] に割り当てるものを決めるが, i 番目のチームはどこに割り当てるか決めない。
      • 割り当て方は, j 通りあるので, dp[i+1][j][k] += dp[i][j][k] * j
    • 割当先が決まっていない j チームの中から C[i] に割り当てるものを決め, かつ i 番目のチームを k チームのどれかにする。
      • 割り当て方は j * k 通りなので, dp[i+1][j-1][k-1] += dp[i][j][k] * j * k
  • C[i] == 'U' の時,
    • その i 番目はどこにも割り当てない場合 これは dp[i+1][j+1][k+1] += dp[i][j][k]
    • i 番目を今までに割り当てられていない k 個のどれかに割り当てる場合, dp[i+1][j][k] += dp[i][j][k] * k

これで解けます。

ただ上の遷移をよく見ると j = k のところ以外は dp[i][j][k] = 0 となることに気付くので, O(N^2) で解けます。

O(N^2)

const int MAXN = 222;
const int MOD = 1e9+7;
ll dp[MAXN][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    string s;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        if (c != '-') s += c;
    }
    N = s.size();
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            if (s[i] == 'D') {
                dp[i+1][j] += dp[i][j] * j % MOD;
                if (j) dp[i+1][j-1] += dp[i][j] * j * j % MOD;
            } else {
                dp[i+1][j+1] += dp[i][j];
                dp[i+1][j] += dp[i][j] * j;
            }
        }
        for (int j = 0; j <= i+1; j++)
            dp[i+1][j] %= MOD;
    }
    cout << dp[N][0] << endl;
    return 0;
}

O(N^3)

const int MOD = 1e9+7;
ll dp[222][222][222];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
        int N;
    cin >> N;
    string s;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        if (c != '-') s += c;
    }
    N = s.size();
    dp[0][0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) for (int k = 0; k <= i; k++) {
            if (s[i] == 'D') {
                dp[i+1][j][k] += dp[i][j][k] * j % MOD;
                if (j > 0 && k > 0) dp[i+1][j-1][k-1] += dp[i][j][k] * j * k % MOD;
            } else {
                dp[i+1][j+1][k+1] += dp[i][j][k];
                dp[i+1][j][k] += dp[i][j][k] * k % MOD;
            }
        }
        for (int j = 0; j <= i+1; j++) for (int k = 0; k <= i+1; k++) {
            dp[i+1][j][k] %= MOD;
        }
    }
    cout << dp[N][0][0] << endl;
    return 0;
}

Codeforces Round #366 (Div. 2) C. Thor

CodeForces
問題

codeforces.com

q 個のクエリが飛んでくる。それぞれのクエリは type, x の二つの整数から構成され,

  • type = 1 の時, 種類 x のボールが飛んでくる
  • type = 2 の時, 今までに飛んできた種類 x のボールをすべて捨てる
  • type = 3 の時, 今まで飛んできたすべてのボールのうち, 最初の x 個のボールを捨てる

それぞれのクエリが投げられた直後, 手元にあるボールの数を求めよ。

解法

D[x]: 種類 x のボールが投げられたタイミングをすべて記録したもの
S[x], T[x]: 種類 x のボールのうち, 手元にあるものの区間([S[x], T[x]) の区間 i について, D[x][i] というボールがある)
memo[i]: i 番目に来たボールはまだ手元にあるか

というようにデータを持っておきます。すると,

  • type 1 については, D[x].push_back と T[x]++ でだいたい済む
  • type 2 については, [S[x], T[x]) の区間に含まれる i について, memo[D[x][i]] = false にする
  • type 3 については, memo[x] までをすべて false にする

ということをやれば良いです。すでに調べたところを二重に調べなければ, これらのクエリはすべて全体として O(Q) で対処可能です。

const int MAXN = 300300;
vi D[MAXN];
int S[MAXN], T[MAXN], R[MAXN];
bool memo[MAXN];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    int note = 0, ans = 0, last = 0;
    for (int i = 0; i < q; i++) {
        int type, x;
        scanf("%d %d", &type, &x);
        if (type == 1) {
            D[x].push_back(note);
            memo[note] = true;
            //R[note] = x;
            note++;
            ans++;
            T[x]++;
        } else if (type == 2) {
            for (int i = S[x]; i < T[x]; i++) {
                if (memo[D[x][i]]) {
                    ans--;
                    memo[D[x][i]] = false;
                }
            }
            S[x] = T[x];
        } else {
            for (int i = last; i < x; i++) {
                if (memo[i]) {
                    ans--;
                    memo[i] = false;
                    //S[R[i]]++;
                }
            }
            last = max(last, x);
        }
        printf("%d\n", ans);
    }
    return 0;
}

これ 2000 人も解けるのね…