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, ... のことです)を見に行って, また右に…」とやるのは…