Typical DP Contest H - ナップザック

http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack 問題概要 N個のものがあって、それぞれに重さw・価値v・色cが設定されている。重さ合計の最大値Wと使える色の種類の最大値Cが与えられるので、その範囲内で価値の合計が最も高くなるような組合せを選ん…

Typical DP Contest J - ボール

http://tdpc.contest.atcoder.jp/tasks/tdpc_ball 問題概要 一次元の座標xiにN個の目標物が設置されている。座標xを狙ってボールを投げると等確率でx-1, x, x+1のいずれかにボールが飛んでいき、そこに目標物があればそれを倒せる。狙う座標を最適に選んだと…

Codeforces Round #433 Div.2 D / Div.1 B - Jury Meeting

http://codeforces.com/contest/854/problem/D 問題概要 (N+1)個の町があり、1~Nの町に一人ずつ人が住んでいる。また 町0 → 町(1~Nのどれか) に飛ぶ飛行機と、町(1~Nのどれか) → 町0 に飛ぶ飛行機の2種類がある。飛行機を使って1~Nの町の人を全員町0に呼…

CS Academy #46 (Div. 1.5) E - Ultimate Orbs

https://csacademy.com/contest/round-46/task/ultimateorbs/ 問題概要 N個のオーブが座標1~Nに順番に並んでいる。各オーブには強さGiが設定されており、左隣あるいは右隣のオーブに対して 自分の強さ+D >= 相手の強さ であればそのオーブを吸収できる。吸…

Codeforces Round #432 Div.2 E / Div.1 C - Arpa and a game with Mojtaba

http://codeforces.com/contest/850/problem/C 問題概要 先手と後手に分かれて以下のような2人ゲームを行う。まずN要素の数列Aが与えられる。プレイヤーは手番ごとに素数pと正整数kを選び、数列のうちpkで割り切れる要素をpkで割る。ただしどの要素も割り切…

AtCoder Regular Contest 082 F - Sandglass

http://arc082.contest.atcoder.jp/tasks/arc082_d 問題概要 砂時計に合計X[g]の砂が入っている。砂は1秒に1[g]のペースで上から下に落ちる。砂時計はr1, r2, …, rK秒後にひっくり返される。ここでQ個のクエリ(ti, ai)が与えられるので、初めに砂時計の上の…

AtCoder Regular Contest 082 E - ConvexScore

http://arc082.contest.atcoder.jp/tasks/arc082_c 問題概要 二次元平面上のN個の点が与えられる。これらの点の部分集合Sであって凸多角形をなすものについて考える。このようなSの凸包に対し、凸包の周上の点と内部の点の数の合計をnとし、2n-|S|をSのスコ…

Codeforces Round #432 Div.2 D / Div.1 B - Arpa and a list of numbers

http://codeforces.com/contest/850/problem/B 問題概要 N要素の数列Aが与えられる。以下の操作を好きなだけ繰り返して、数列の全要素のGCDが1でなくなるようにしたい。目的を達成する最小のコストを求めよ。 操作1. コストxで数列から任意の1要素を取り除く…

Codeforces Round #432 Div.2 C / Div.1 A - Five Dimensional Points

http://codeforces.com/contest/850/problem/A 問題概要 5次元空間上のN個点が与えられる。この中のある点aについて、異なる点b, cを取ってきたときにab, acのなす角が90度未満となるb, cが存在するとき、aを悪い点と呼び、そうでない場合良い点と呼ぶ。良い…

AtCoder Grand Contest 019 D - Shift and Flip

http://agc019.contest.atcoder.jp/tasks/agc019_d 問題概要 0と1のみからなる同じ長さの文字列A, Bが与えられる。以下の操作を何度か行ってAを変化させていったとき、AをBに一致させることができるか判定せよ。また可能な場合は最小の操作回数を求めよ。 操…

AtCoder Grand Contest 019 C - Fountain Walk

http://agc019.contest.atcoder.jp/tasks/agc019_c 問題概要 東西方向に伸びる108本の道と、南北方向に伸びる108本の道がある。それぞれの道はすべて100メートルごとに等間隔で並んでおり、0から108 -1の番号がついている。南北方向のx番目の道と東西方向のy…

CS Academy #43 D - Bad Triplet

https://csacademy.com/contest/round-43/task/bad-triplet/ 問題概要 N頂点M辺の単純無向連結グラフが与えられる。各辺の長さはいずれも1である。このグラフからある3つの頂点A, B, Cを選んだとき、A-B間, A-C間, B-C間の最短距離が等しくなるようなA, B, C…

AtCoder Grand Contest 009 C - Division into Two

http://agc009.contest.atcoder.jp/tasks/agc009_c 問題概要 昇順ソート済みのN要素の数列Sが与えられる。この数列を2つの集合X, Yに分割する。ただしX, Yは以下の条件を満たしていなければならない。 Xに含まれるどの相異なる2要素も差の絶対値がA以上 Yに…

AtCoder Grand Contest 006 D - Median Pyramid Hard

http://agc006.contest.atcoder.jp/tasks/agc006_d 問題概要 N段のピラミッドがあり、i段目は(2i-1)個のブロックからなる。最下段の(2N-1)個のブロックには(1, 2, …, 2N-1)を並べ替えた数字がそれぞれ書き込まれている。最下段以外のi段目のブロックのj番目…

AtCoder Grand Contest 006 C - Rabbit Exercise

http://agc006.contest.atcoder.jp/tasks/agc006_c 問題概要 1~Nの番号が振られたN匹のうさぎが一次元の数直線上に存在し、各うさぎの初期座標を示す数列Xが与えられる。うさぎi(2<=i<=N-1)がジャンプを行うと、うさぎ(i-1)かうさぎ(i+1)のどちらかが等確率…

AtCoder Beginner Contest 020 D - LCM Rush

http://abc020.contest.atcoder.jp/tasks/abc020_d 問題概要 整数N, Kが与えられる。 を求めよ。 1 <= N, K <= 109 解法 (要点:「約数にxをもつ集合」から「約数に2xを持つ集合」, 「約数に3xを持つ集合」, …を引いていけば「GCDがxの集合」を出せる) LCM…

Codeforces Round #429 Div.2 D / Div.1 B - Leha and another game about graph

http://codeforces.com/contest/840/problem/B 問題概要 N頂点M辺の連結な無向グラフGと、N要素の数列Dが与えられる。数列Dの要素は-1, 0, 1のいずれかである。Gから任意の辺集合を選び、選ばれた辺以外を削除するとき、以下の条件を満たすことができるか判…

AtCoder Regular Contest 081 F - Flip and Rectangles

http://arc081.contest.atcoder.jp/tasks/arc081_d 問題概要 H×Wの2次元のマス目が与えられる。各マスは白か黒のどちらかで塗られている。任意の行または列を選びその行または列に含まれるすべてのマスの色を反転させる、という操作を好きなだけ行えるとき、…

AtCoder Regular Contest 081 E - Don't Be a Subsequence

http://arc081.contest.atcoder.jp/tasks/arc081_c 問題概要 文字列Sが与えられる。Sの部分列ではないような文字列のうち、最も短いものを求めよ。答えが複数ある場合には辞書順で最小のものを答えること。文字列はいずれも英小文字のみからなるものとする。…

CS Academy Round #42 (Div. 2 only) E - Xor Submatrix

https://csacademy.com/contest/round-42/task/xor-submatrix/ 問題概要 N要素の数列UとM要素の数列Vが与えられる。これらを用いて, となるようなN*Mの行列Aを構成する。Aから任意のサイズの部分行列を取り出し全要素のxorを取った時に得られる最大の値を求…

Codeforces Round #428 Div.2 D - Winter is here

http://codeforces.com/contest/839/problem/D 問題概要 N要素の数列Aが与えられる。Aの部分集合Sに対して、strength(S) = |S|・gcd(S) と定義する。gcd(S) > 1 なるすべての部分集合Sに対するstrengthの総和を求めよ。 N <= 2 * 105, max(A) <= 106 解法 一…

AtCoder Grand Contest 008 D - K-th K

http://agc008.contest.atcoder.jp/tasks/agc008_d 問題概要 与えられた長さNの数列Xに対して、次の条件すべてを満たす数列Aが構成できるか判定せよ。またできるならば実際にひとつ示せ。 条件1. Aの長さはN2 条件2. Aは要素として1, 2, …, NをN個ずつ含む …

AtCoder Grand Contest 004 D - Teleporter

http://agc004.contest.atcoder.jp/tasks/agc004_d 問題概要 N個の町があり、1~Nまでの番号が振られている。それぞれの町には1台ずつテレポーターがあり、町iのテレポーターの転送先は町aiに設定されている。また初期状態では必ず何回かテレポーターをたど…

CS Academy Round #41 E - Candles

https://csacademy.com/contest/round-41/task/candles/ 問題概要 N要素の数列HとM要素の数列Cが与えられる。以下のような操作をHに対して行っていく。 操作: i回目の操作においてHからC[i]個の正の要素を選び、すべてを1デクリメントする。 数列Hに正の要素…

AtCoder Regular Contest 080 F - Prime Flip

http://arc080.contest.atcoder.jp/tasks/arc080_d 問題概要 1, 2, …と順に番号の振られた無限枚のカードと、N要素の数列Xがある。数列Xに含まれる番号のカードは表向きで、それ以外は裏向きである。奇素数pと連続するp枚のカードを自由に選びそれらを裏返す…

Typical DP Contest G - 辞書順

http://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical 問題概要 英小文字からなる文字列Sの部分文字列のうち、辞書順でK番目のものを求めよ。ただしここでいう部分文字列は元の文字列で連続でないものも含む。また違うindexからなるものでも、結果と…

AtCoder Grand Contest 018 C - Coins

http://agc018.contest.atcoder.jp/tasks/agc018_c 問題概要 (X+Y+Z)人の人がいて、全員が金・銀・銅の3種類のコインを決められた枚数ずつ持っている。X人から金の、Y人から銀の、Z人から銅のコインをそれぞれその人が持っている分だけもらうとき、もらえる…

第3回 ドワンゴからの挑戦状 本選 A - 計算ドリル

http://dwacon2017-honsen.contest.atcoder.jp/tasks/dwango2017final_a 問題概要 0~9の数字と+, -の演算子のみからなる文字列Sが与えられる。この文字列を逆ポーランド記法とみなして計算を行ったときの最終的な計算結果をこの文字列の値とする。ただしこ…

AtCoder Regular Contest 080 E - Young Maids

http://arc080.contest.atcoder.jp/tasks/arc080_c 問題概要 偶数N、1~Nの順列P、空の数列Qがある。Pが空になるまで以下の操作を行う。 操作: Pの隣り合う2要素を選び、順序を保ったままQの先頭に追加する。 これによってできるQのうち、辞書順で最小のもの…

Codeforces Round #427 Div. 2 E - The penguin's game

http://codeforces.com/contest/835/problem/E 問題概要 N要素の数列があり、そのうち2要素はYで残りの要素はXである。質問クエリとして数列のインデックスの部分集合を指定すると、それらの値のXORを知ることができる。19回以内の質問クエリで値Yを持つ2要…