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

mayoko’s diary

プロコンとかいろいろ。

CodeForces

Codeforces Round #365 (Div. 2) C. Chris and Road

問題 codeforces.comn 頂点の凸多角形が x 軸方向の負の方向に単位時間 v で移動する。この凸多角形の内部に入らないように, y 軸を y = w まで移動したい。 y 軸の移動速度が最大で u の時, 最短で何秒で y = w まで移動できるか。 解法 凸多角形の左側を歩…

Codeforces Round #367 (Div. 2) E. Working routine

問題 codeforces.comN*M のグリッドが与えられる。各クエリで 「(a, b), (c, d) を左上の頂点とする高さ h, 幅 w の領域を交換する」ということをする(ただし, 交換する長方形は辺やセルを共有しない)。 全てのクエリを処理した後の最終的なグリッドの状態を…

Codeforces Round #368 (Div. 2) D. Persistent Bookcase

これ普通に頭良いと思うんだけどみんな解いてるんだよなぁ… 問題 codeforces.com最初すべてのセルが塗られていないグリッドが与えられる。以下の Q 個クエリを処理し, グリッドで黒色のセルの数を出力せよ。 i 行 j 列目のセルが白なら黒くする。 i 行 j 列…

2015-2016 XVI Open Cup, Grand Prix of Bashkortostan, SKB Kontur Cup Stage 2 A. Abstract Picture

JAG 夏合宿最終日に yurahuna さんに投げたら勝手に AC してくれた問題です。 問題 codeforces.comN*N のグリッド上に色を塗りたい。 1 回の操作では行に同じ色をバーっと塗るか列に同じ色をバーッと塗るかしかない。最終的に塗りたい配色が与えられるので, …

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

問題 codeforces.com頂点数 n の木 T 上の点 v が T の centorid であるとは, T から v を取り除いて得られる任意の連結成分が, 全て頂点数 n/2 以下であることを言う。各頂点について, その頂点が以下の操作を一回以下許したとき centroid になるかどうかを…

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

問題 codeforces.com0, 1 のみから構成される文字列で, 以下を満たすものを作れ。 00 の部分文字列が a00 個ある 01 の部分文字列が a01 個ある 10 の部分文字列が a10 個ある 11 の部分文字列が a11 個ある 連続部分文字列ではないことに注意。 解法 0 が n…

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

問題 codeforces.comq 個のクエリが飛んでくる。それぞれのクエリは type, x の二つの整数から構成され, type = 1 の時, 種類 x のボールが飛んでくる type = 2 の時, 今までに飛んできた種類 x のボールをすべて捨てる type = 3 の時, 今まで飛んできたすべ…

Educational Codeforces Round 16 D. Two Arithmetic Progressions

問題 codeforces.comx = a1 * k + b1 = a2 * l + b2, L 解法 k, l の組を一つ求められれば, 後は x が lcm(a1, a2) の周期で解になるので簡単です(実装が楽とは言っていない)。a1 * k + b1 = a2 * l + b2 を変形すると a1 * k - a2 * l = b2 - b1 となります…

Codeforces Round #369 (Div. 2) E. ZS and The Birthday Paradox

問題 codeforces.com整数 n, k が与えられる。p = 2^n として, 1 - (p! / p^k * (p-k)!) の分母と分子を求めよ。ただし分母と分子は非常に大きな値になることがあるので, 10^6+3 で割ったあまりを求める。 (本当は p 解法 上では p! / p^k * (p-k)! と書きま…

Codeforces Round #354 (Div. 2) E. The Last Fight Between Human and AI

問題 codeforces.comA さんと B さんが N 次の多項式の係数を埋めるゲームをする(係数は実数ならなんでも良い)。A さんの目的はこの多項式が x-k で割り切れるようにすることで, B さんはそれを阻止することが目的である。B さんが先行ですでにいくつかの係…

Codeforces Round #354 (Div. 2) D. Theseus and labyrinth

Div2 だけど久しぶりにこどふぉやった気がする・・・ 問題 codeforces.com迷路が与えられる。迷路はセルが H*W 個あるような形をしており, 各セルにはいくつかの方向にドアがついている(上, 右, 下, 左 からいくつか)。 あるセルからは, 隣接するセルに移動…

Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor

問題 codeforces.com例によって正しいかっこ列 CBS を定める。 このかっこ列に対して, あるポインタ p から次のように操作をしていく。 L: p を 1 つ左に移動させる。 R: p を 1 つ右に移動させる。 D: p に対応するかっこが必ずある。p 番目のかっことそれ…

Codeforces Round #349 (Div. 1) A. Reberland Linguistics

問題 codeforces.com文字列 s が与えられる。この文字列を以下のルールにしたがって区切る。 まず s の最初の 5 文字以上の文字を作る。 その後は, 長さを 2 か 3 にしながら区切る。区切る時, 直前に区切ってできた文字列と同じになってはならない。 この時…

VK Cup 2016 - Qualification Round 1 D. Running with Obstacles

問題 codeforces.com 解法 戦略としては, JUMP するときは a[i]+1 から a[i+1]-1 のようにめっちゃ走ってから, a[i+1]+1 のように障害物の直後の場所に着地する, というようにするのが良さそうです。dp[i] = (a[i]+1 から走って JUMP することで a[par]+1 ->…

CROC 2016 - Qualification B. Processing Queries

問題 codeforces.com 解法 しゃくとりっぽくやります。 区間 [lp, rp) の区間を見ている時, t[rp] より前の始まる仕事は全部片付けておきます。で, この時 queue に詰まれた仕事の数が b 未満なら, rp を仕事として追加します。一方, 仕事の数が b 以上なら,…

CROC 2016 - Qualification C. Hostname Aliases

問題 codeforces.com 解法 各ホストについて, 出てくるパスを sort -> erase することによってまとめます。パスについては, 両端に "$" を挟むような形にして各パスが独立になるようにしておきましょう(そうしないと "ab", "cd" っていうのと "abc", "d" っ…

Codeforces Round #346 (Div. 2) E. New Reform

問題 codeforces.com 解法 連結成分に一つでも閉路があると, すべての頂点の入次数を 1 以上にすることが出来ます。そうでない場合は木になりますが, 一つの頂点を root として, それ以外のすべての頂点の入次数を 1 以上に出来ます。よって, 各連結成分につ…

VK Cup 2016 - Round 1 D. Bear and Contribution

問題 codeforces.com 解法 まず単純な解法を考えてみます。目標になる値を決めると, 各値(vals という配列にまとめておくことにします)を目標の値にするために必要なコストが決定します(t だけ contribution を増やしたいとすると, t/5 * c1 + (t%5)*c がか…

Educational Codeforces Round 10 D. Nested Segments

気づかなかった…ガックシ。Codeforces の data structure の問題解いてきます… 問題 codeforces.com 解法 条件は, 「a_i まず a_i の大きい順番にソートし, 順番に a_i を見ていくと, 後から見る a_i は, それ以前に考慮されたすべての a_j について, a_i 落…

Educational Codeforces Round 10 C. Foe Pairs

問題 codeforces.com 解法 しゃくとり法を使って解きます。まず前準備として, pos[i] = (数 i がある位置), memo[i].first = (数 i より左側にある数で, Foe Pair になってしまううち最も右側にあるもののの位置), memo[i].second = (数 i より右側にある数…

IndiaHacks 2016 - Online Edition E. Bear and Forgotten Tree 2

問題 codeforces.com 解法 さっきの問題とよく似ています。 mayokoex.hatenablog.comまず, 頂点 0 からつながる頂点を列挙します。これが k 個以下だったら impossible です。で, それらの点からスタートして, 0 以外の頂点となるべく連結させていきます。こ…

IndiaHacks 2016 - Online Edition D. Delivery Bears

問題 codeforces.com 解法 もう問題から「最大流使って下さい」というにおいがプンプンします。答えを二分探索して, 各辺について「くまが何匹通れるか」というのを cap にします。この時, 頂点 0 から頂点 n-1 へのフローが x 以上であるならば, すべてのく…

IndiaHacks 2016 - Online Edition C. Bear and Up-Down

問題 codeforces.com 解法 条件が合わない場所がたくさんありすぎると, どうスワップしても条件が合わない場所すべてに対応することが出来ないので, NG です。ということで, 条件が合わない場所が 10 箇所より多い場合は問答無用で 0 を出力しましょう(多分 …

8VC Venture Cup 2016 - Final Round C. Package Delivery

これはいろいろ難しい問題でした… 良い問題だと思います。 問題 codeforces.com 解法 まず方針です。なんとなく貪欲な気がしますが, 気づくのが難しいです。 next[i] = (x[i] から n 以内で進める場所にあって, p[i] よりもコストが小さい, 最もx[i] に近い…

Codeforces Round #225 (Div. 1) D. Antimatter

こんな簡単に解けると思ってなかったので目からウロコでした。 問題 codeforces.com 解法 dp[n][sum] = ([1, n], [2, n], ..., [n-1, n] という区間で, 和が sum になる場合の数) というのを考えます(antimatter の分はマイナスで数えるので, 要するに dp[n]…

Codeforces Round #225 (Div. 2) C. Milking cows

解いてる時はなんとなく提出したら正解だった, という感じでした。 問題 codeforces.com 解法 右に向いてるやつを左から順番に取っていき, その後に左に向いてるやつを右から順番に取っていく, というのが最適な milking の一つです(左に向いてるやつを右か…

8VC Venture Cup 2016 - Final Round B. Factory Repairs

問題 codeforces.com 解法 問題文の解釈をするのが一番難しいです。問題文の意味を書きます。指ぬき(?)を作る機械が 1 つある。修理する前は 1 日 b 個, 修理した後は 1 日に a 個の指ぬきを作れる。修理をするのには k 日かかり, 修理開始日が p だとすると…

8VC Venture Cup 2016 - Final Round A. XOR Equation

問題 codeforces.com 解法 dp で解きます。a の 2^0 の位が決まれば, b の 2^0 の位も決まります。なぜなら, a^b = x より, x の 2^0 の位を見れば b のそれも決定するからです。このようにして a と b の 2^0 の位を決めた際, a+b は偶数になるか奇数になる…

Codeforces Round #345 (Div. 1) C. Table Compression

問題 codeforces.com 解法 大小関係系は, 「a b に有向辺を貼る」ということをやるのがよくあります。これもそのタイプです。すべての数が異なっていたとすると, a_ij (i, k) に辺を貼る a_ij (k, j) に辺を貼る というようにしてグラフを作ります。で, この…

Codeforces Round #345 (Div. 1) B. Image Preview

この回かなり簡単だったみたいですね…(普段だと僕は B から苦戦しているはず) 問題 codeforces.com 解法 まず考察です。 写真の見かたを考えると, 「0 より右側の写真を見に行って, 次に左側(n-1, n-2, ... のことです)を見に行って, また右に…」とやるのは…

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…