問題概要 AチームとBチームにわかれて対戦するゲームがある。このゲームでは試合終了後に各プレイヤーのリザルトとしてkill数とdeath数が表示される。リザルトは各チームごとにkill数の多いプレイヤーから順に表示される。kill数が同数の場合はdeath数の少な…

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

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

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

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

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

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

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

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

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

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

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が、そう…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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