mayoko’s diary

プロコンとかいろいろ。

2016-03-02から1日間の記事一覧

Codeforces Round #223 (Div. 1) C. Sereja and Brackets

いやぁこれは頭良いっす… 問題 codeforces.com 解法 セグメント木を使って解くことが出来ます。2 つの区間を合併する時, 各区間の valid な括弧列の長さを ok, それ以外で '(' の数を open, ')' の数を close とすると, valid な括弧列は崩しても得をしない…

Codeforces Round #223 (Div. 1) B. Sereja and Tree

問題 codeforces.com 解法 この問題では N, M が比較的小さいので, 一つのクエリにつき O(N log N) 程度で処理できれば AC します。まず, 7000 行目で頂点がいくつぐらいあるのかを確認してみましょう。プログラムに計算させると 109315 個であるとわかりま…

Codeforces Round #223 (Div. 1) A. Sereja and Prefixes

問題 codeforces.com 解法 2 つのタイプの操作がありますが, どちらのタイプでも 10^5 番目以降の数が数の生成に関わることはないです。なのでとりあえず 10^5 個の数は配列で持っておくことにしましょう。この配列を v とします。 他に, 今まで並んでいる整…

SRM 683 div1 med: GCDLCM2

問題 TopCoder Statistics - Problem Statement 解法 まず x と y を使って操作をしたらどうなるのかを考えてみます。x と y の最大公約数を g として, x = g*x1, y = g*y1 であったとすると, 新しくつくられる 2 つの整数は g, g*x1*y1 となります。これが …