mayoko’s diary

プロコンとかいろいろ。

CodeForces

Codeforces Round #345 (Div. 1) A. Watchmen

問題 codeforces.com 解法 マンハッタン距離とユークリッド距離が一致するのは, 「x 座標または y 座標が一致する時」です。X[x] = (x 座標が x の点の数), Y[y] = (y 座標が y の点の数) を数えておけば, 基本的には C[X[x]][2], C[Y[y]][2] の和が答えにな…

Codeforces Round #344 (Div. 2) D. Messenger

問題 codeforces.com 解法 T の i ブロック目を T[i] と書きます(例えば T[i] = 4-a だったら実際には T[i] = "aaaa")。で, T の l ブロック目から r ブロック目をつなげたものを T[l..r] と書きます。文字列 T の区間 [l..r] に文字列 S があるための条件は…

Codeforces Round #344 (Div. 2) C. Report

問題 codeforces.com 解法 まず考察です。最初に r1 個のソートをやったとしても, その後に r2 (> r1) 個のソートを行えば, r1 個のソートはなかったことにしても同じです。つまり, ソートは r1 > r2 > r3 > ... というようにソートを行ったと考えても良いで…

Educational Codeforces Round 9 D. Longest Subsequence

問題 codeforces.com 解法 m の値がそこそこ小さいので, m 以下の数 x について, 「x が最小公倍数になるような配列 a の組みあわせはあるのか」というように考えてみます。これは x の約数がなるべく多いものを選べば解決します(これだと例えば 6, 12, 18, …

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 とします。 他に, 今まで並んでいる整…

Manthan, Codefest 16 C. Spy Syndrome 2

問題 codeforces.com 解法 準備として, 各文字列 wi を反転させて, 小文字化します。やりたいことは, dp[now] = (now 文字目以降を wi を使って表現できるか?) というものです。ただ, あとで dp 復元するために, dp[now] = (now 文字目から復元が不可能なら…

Manthan, Codefest 16 D. Fibonacci-ish

問題 codeforces.com 解法 直前の 2 要素が 0 の時, またその時のみ数列のすべての値が 0 になります。それ以外の場合は, 普通のフィボナッチ数列と同じように, 指数オーダーで発散します。調べてみると, 大体 100 個程度あれば絶対値が 10^9 を超えてきそう…

Educational Codeforces Round 8 E. Zbazi in Zeydabad

D は問題文が理解できないので桁 DP だよねということだけ言っといて退散します。 というかこの問題, 趣旨的に tourist を助けて欲しいという問題になっていますが絶対 tourist のほうが早く解けるんだよなぁ。 問題 codeforces.com 解法 まず, toR[i][j] = …

Codeforces Round #343 (Div. 2) E. Famil Door and Roads

問題 www.codeforces.com 解法 kmjp さんの解法を参考にしました。kmjp.hatenablog.jpまず, この問題では 「グラフに辺を 1 本加えた時出来る閉路について, 特に u, v を含む閉路の平均長」を求める問題であることに注意します。depth[u] u, v の lca が u …

Codeforces Round #222 (Div. 1) C. Captains Mode

このこどふぉ, なんとなく DDPC 本戦が想起される(B が priority_queue を使ったほげで, C が高速化出来る dp) 問題 codeforces.com 解法 pick するなら, 残っているもののうち一番でかいのを取ってくるのが最適です。これを考えると, pick されるものとして…

Codeforces Round #222 (Div. 1) B. Preparing for the Contest

問題 codeforces.com 解法 二分探索します。check(x) = (担当する人が最大で x 日働いて良い場合の, 各問題の人の割り振りを表す配列。割り振れない時は ひとつ目の要素を -1 にする) とすると, 以下のようにすれば最小コストで担当者を割り振れます(前準備…

Codeforces Round #222 (Div. 1) A. Maze

問題 codeforces.com 解法 まず空いてるマスのすべてを 'X' にし, 'X' となっている好きな点から幅優先探索して '.' を広げていけば良いです。 string field[505]; bool done[505][505]; int n, m, k; int main() { cin.tie(0); ios::sync_with_stdio(false)…

Codeforces Round #343 (Div. 2) D. Babaei and Birthday Cake

問題設定ちょっと不自然な気がして最初誤読しました。普通上におけるのは体積の小さいものではなかろうか…? 問題 codeforces.com 解法 素直に dp 解法を取ろうとすると, dp[i] = max(dp[j], j > i, vj > vi) + vi (vi は i の体積) となりますが, これを普…

Codeforces Round #343 (Div. 2) C. Famil Door and Brackets

問題 codeforces.com 解法 dp[now][d] = (now 個の括弧を使った文字列の内, '(' の数が ')' の数を下回ることが一度もなく, '(' の数が now までで ')' の数を d 個上回っているようなものの数) とします。これは簡単な dp で計算できますね。で, 入力文字列…

Educational Codeforces Round 7 F. The Sum of the k-th Powers

問題 codeforces.com 解法 k 乗の和は, k+1 乗の多項式になります。なんで, って人は下の記事を読みましょう。 yama-taku.scienceということで, ラグランジュ補間しましょう。 mayokoex.hatenablog.com ラグランジュ補間は次数 k に対して O(k^2) かかるのが…

Educational Codeforces Round 7 E. Ants in Leaves

問題 codeforces.com 解法 0 の子 v の部分木それぞれの葉から, すべてのアリが頂点 v に到達するまで, 何秒かかるかを調べます。各頂点の v からの距離 d が等しい頂点同士は, 同時に v に向かって行くといつかどこかの頂点でおなじ頂点で重なるので, どち…

Educational Codeforces Round 6 E. New Year Tree

問題 codeforces.com 解法 見た目が明らかに Euler Tour + 遅延評価セグ木 です。今回, 色の種類が 60 種類しかないので, セグメント木には, 2^c[i] (色 c[i] が含まれるかどうかのフラグ) というのの OR を取る形のものを保持しておけば良いです。 struct S…

Educational Codeforces Round 6 D. Professor GukiZ and Two Arrays

問題 codeforces.com 解法 まず 0 回交換の場合, 1 回交換の場合はそのまま O(nm) で調べることが出来ます。で, 2 回交換の場合は, a から b に渡すことの出来る 2 つの数の和のリストおよび b から a に渡すことの出来る 2 つの数の和のリストを O(n^2log n…

Educational Codeforces Round 5 E. Sum of Remainders

問題 codeforces.com 解法 前似たような問題解いてましたね… mayokoex.hatenablog.com 上の記事のは問題設定がわかりにくいですが, 今回のは問題設定が率直でわかりやすいです。10^7 程度までは正直に余りを計算します。それ以上の数での余りは, n/div の商…

Educational Codeforces Round 5 D. Longest k-Good Segment

問題 codeforces.com 解法 しゃくとり法やるだけ, なんですがバグらせまくりました…区間系書くときは, 「閉区間か半開区間か」とか「区間がどのような性質を持っているか」とかは意識すべきですね。そういえば珠玉のプログラミングにもそんなことが書いてあ…

Educational Codeforces Round 4 E. Square Root of Permutation

問題 codeforces.com 解法 順列では「順列 p の i 番目の値が p[i] だったら i -> p[i] に有向辺を貼ってグラフを作る」というのがよくあります。この考えで問題文の順列 q のグラフを作り, そこから p = q^2 を作ることを考えると, p[i] は, 「q のグラフで…

Educational Codeforces Round 4 D. The Union of k-Segments

問題 codeforces.com 解法 未だに問題の意味が正確にはわからないのでアレなんですが, 現れる数ごとに区間が重なっている数を +1, -1 していって, 重なる数が k 以上のところを取り出していけば良いです。 int main() { int n, k; cin >> n >> k; vector<pii> mem</pii>…

Codeforces Round #221 (Div. 1) D. Tree and Queries

問題 codeforces.com 解法 前使ったばかりの, データ構造をマージする一般的なテクを使います。M[v][color] = (頂点 v 以下の subtree において, 色が color の頂点がいくつあるか) N[v][num] = (頂点 v 以下の subtree において, 頂点数が num 以上ある col…

Codeforces Round #221 (Div. 1) B. Maximum Submatrix 2

問題 codeforces.com 解法 maxi[row][l] = (row 行目の l 番目の要素から始めると, 1 が最大どこまで連続しているか) というのを, 各行 row について, しゃくとりっぽく O(m) で求めます。そしたら, l 列目からスタートする長方形について, 面積が最大にする…

Codeforces Round #221 (Div. 1) A. Divisible by Seven

問題 codeforces.com 解法 1, 6, 8, 9 を適当に並び替えると, 7 で割った余りが 0, 1, ..., 6 のいずれにもなりえます。ということで, 0, 1, 6, 8, 9 以外をとりあえず並べて, 1, 6, 8, 9 を全体の数が 7 の倍数になるように並べます。最後に, 0 を並べて終…

Educational Codeforces Round 3 E. Minimum spanning tree for each edge

問題 codeforces.com 解法 まず普通に MST を作ります。で, その木に辺 (u, v) を追加したと考えると, 閉路が出来ます。閉路のいずれかの辺を取り除くと再び木になるので, 閉路の中からコストが最大の辺を取り除けば良いです。最大の辺はどうやって取り除け…

Educational Codeforces Round 3 D. Gadgets for dollars and pounds

問題 codeforces.com 解法 冷静に考えるとちょっと前準備をしてから答えに対して二分探索すれば良かったと思うんですが, 答えを 1 つずつ足していって, それが条件を満たすかを 3 分探索で調べる, という方法で AC しました。ある日程 ans について, i あと…

Educational Codeforces Round 2 E. Lomsat gelral

問題 codeforces.com 解法 "データ構造をマージする一般的なテク" を使います。なにそれ, という人は以下のページをご覧ください。 topcoder.g.hatena.ne.jp今回の問題の場合, M[v][color] = (頂点 v 以下の部分木で, 色が color の頂点がいくつあるか) とい…