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…

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…

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

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

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

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

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 解法 一…

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

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

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

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

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

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

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

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

http://codeforces.com/problemset/problem/835/D 問題概要 ある文字列に対して以下のようにk-palindromesが定義される。 文字列が回文ならば、その文字列は 1-palindrome である k > 1 のとき、文字列の左半分と右半分が等しく、かつ左半分が (k-1)-palindr…