AtCoder

AtCoder Grand Contest 002 D - Stamp Rally

http://agc002.contest.atcoder.jp/tasks/agc002_d 問題概要 N頂点M辺の無向グラフがあり、頂点には1~N, 辺には1~Mの番号がついている。またQ個のクエリがあり、ひとつのクエリでは2つの頂点番号x, yと整数zが与えられる。各クエリごとに、x, yの2つを出発…

Typical DP Contest M - 家

http://tdpc.contest.atcoder.jp/tasks/tdpc_house 問題概要 H階建ての家があり、各階には部屋が1番~R番までのR個存在する。部屋間を以下のルールに従って移動するとき、H階の部屋1から1階の部屋1に移動する経路は何通りあるか。ルール1. h階の部屋rから(h-…

AtCoder Regular Contest 084 D - Small Multiple

http://arc084.contest.atcoder.jp/tasks/arc084_b 問題概要 正整数Kのすべての正の倍数において、10進法で表したときの各桁の和の最小値を求めよ。 2 <= K <= 105 解法 以下のようなグラフを考え、最短経路問題を解く。 頂点は0~(K-1)のK個 頂点x → 頂点(x…

天下一プログラマーコンテスト2016予選A C - 山田山本問題

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_c 問題概要 英小文字のみからなる2つの文字列のペア(Ai, Bi)がN個与えられる。ここで26個のアルファベットの順番を並べ替え、AiがBiより辞書順で小さくなるようにしたい。そのような並…

CODE FESTIVAL 2017 qual A D - Four Coloring

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d 問題概要 H行W列のグリッドを4色で塗り分ける。このときマンハッタン距離がちょうどdのグリッド同士は別の色で塗らなければならない。条件を満たす塗り方をひとつ示せ…

AtCoder Grand Contest 014 D - Black and White Tree

http://agc014.contest.atcoder.jp/tasks/agc014_d 問題概要 N頂点の木に対し以下のような2人ゲームを行う。各手番において未着色の頂点を必ずひとつ選び、先手ならば白、後手ならば黒で塗る。すべての頂点が塗られたあと、黒の頂点に隣接している白の頂点を…

AtCoder Grand Contest 011 D - Half Reflector

http://agc011.contest.atcoder.jp/tasks/agc011_d 問題概要 左右からボールを入れられるN個の装置が横一直線に並んでいる。装置は状態Aか状態Bのどちらかである。状態Aの装置にボールが入ってくると、入ってきた方向にボールを跳ね返し状態Bに変化する。状…

AtCoder Regular Contest 083 E - Bichrome Tree

http://arc083.contest.atcoder.jp/tasks/arc083_c 問題概要 N頂点の根付き木とN要素の数列Xが与えられる。木の各頂点に白or黒の色と非負整数を割り当てるとき、頂点nを根とする部分木に含まれる頂点のうちnと同じ色のものに割り当てられた数の合計がX_nとな…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

http://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d 問題概要 英小文字のみからなる文字列Sをいくつかの箇所で区切り、空でない部分文字列に分割することを考える。このとき必ずすべての部分文字列が「並べ替えれば回文…

AtCoder Grand Contest 011 C - Squared Graph

http://agc011.contest.atcoder.jp/tasks/agc011_c 問題概要 N頂点M辺の単純無向グラフGが与えられる。Gの各頂点は1~Nまでの番号が付いている。Gを元にして以下のようなグラフG'を作ったとき、G'の連結成分の数を求めよ。 頂点数はN2 各頂点は1以上N以下の2…

AtCoder Regular Contest 078 E - Awkward Response

http://arc078.contest.atcoder.jp/tasks/arc078_c 問題概要 ある正整数Nが設定されている。64回以内の質問クエリでNを特定せよ。質問クエリで正整数nを投げると、「n <= N かつ str(n) <= str(N)」または「n > N かつ str(n) > str(N)」 のときYESが、そう…

Typical DP Contest L - 猫

http://tdpc.contest.atcoder.jp/tasks/tdpc_cat 問題概要 1~Nまでの番号がついたN匹の猫がいる。任意の猫2匹の組合せには親密度が設定されており、各猫の幸福度は自分との距離が1以内のところにいるすべての猫との親密度の和で定義される。1次元の数直線上…

Typical DP Contest K - ターゲット

http://tdpc.contest.atcoder.jp/tasks/tdpc_target 問題 半径ri, 中心(xi, 0)のN個の円が与えられる。この中からどの2円をとっても片方がもう片方の内部に厳密に含まれるようにいくつかの円を選ぶとき、選べる円の最大数を求めよ。 解法 円cとx軸上の2交点…

Typical DP Contest I - イウィ

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi 問題概要 iとwの2種類の文字のみからなる文字列Sが与えられる。Sのある連続部分文字列が"iwi"となっているとき、その部分を取り除く操作を行うことができる。Sに対して最大何回この操作を行えるか求めよ。 |S…

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のいずれかにボールが飛んでいき、そこに目標物があればそれを倒せる。狙う座標を最適に選んだと…

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のスコ…

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…

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…

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の部分列ではないような文字列のうち、最も短いものを求めよ。答えが複数ある場合には辞書順で最小のものを答えること。文字列はいずれも英小文字のみからなるものとする。…

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に設定されている。また初期状態では必ず何回かテレポーターをたど…

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からなるものでも、結果と…