概要 2以上の整数Nと整数Kが与えられる。このときN頂点M辺の無向グラフで下記のものが存在するかどうかを判定せよ。もし存在するならそのグラフを出力し、存在しないなら-1を出力せよ。 グラフは単純かつ連結 グラフには最短距離が2であるような頂点対(i, j)…

概要 長さNの整数列Sと長さTの整数列Mが与えられる。Sの部分列とTの部分列のなかで共通するものはいくつあるか。(mod 10^9+7 して出力) 制約 1 ≦ N, M ≦ 2 * 10^3 方針 DP。S = {1, 3, 2}, T = {1, 2, 3, 3, 2, 3}のケースを考える。このとき該当する部分列…

Problem - C - Codeforces 概要 N項の数列a, bがある。a, bに含まれる要素はあわせて2N個であるが、このうちN個は1からNまでの整数で、うちN個は全て0である。aを手札、bを山札とし、次の操作を繰り返す。 手札から1枚選び、山札の底に入れる。その後、山札…

Problem - D - Codeforces 概要 n項の数列aと整数kが与えられる。aをk個の連続する部分列に分解し、f(i)：i番目の項が属する部分列の番号とする。Σai * f(i)の最大値を答えよ。 制約 1 ≦ k ≦ n ≦ 3 * 10 ^ 5 |ai| ≦ 10^6 方針 数列の後ろからの累積和s(k) = …

概要 整数Lが与えられる。下記の条件を満たす非負整数の組(a, b)がいくつあるかを求めよ。(mod 10^9+7 して出力) a+b ≦ L a+b = a xor b 制約 1 ≦ L 方針 a + b = a xor b ⇔ a & b = 0 ⇔ a, bの2進表記でどちらも1となる桁がない（繰り上がりがない）下記の…

D - プレゼント 概要 N項の数列HとWが与えられ、N個の箱の縦の長さと横の長さを表す。箱iと箱jはHi 入れ子にすることができるか。 制約 1 ≦ N ≦ 10^5 1 ≦ H, W ≦ 10^5 方針 Hが全て異なる場合は、H・WのペアについてHを昇順に並べた後、WのLISの長さが答え。…

J - GCD β 概要 整数のペア(Ai, Bi)がN個ある。各ペアから1つずつ整数を選び、選んだN個の整数の最大公約数を計算することを考える。計算されうる最大公約数の最大値を求めよ。 制約 1 ≦ N ≦ 5 * 10^4 1 ≦ Ai, Bi ≦ 10^9 方針 最初のペア(A1, B1)のうちどち…

B - ABC 概要 A, B, Cからなる文字列がある。この文字列の部分文字列のうちABCの部分をBCAに変える操作を好きなだけ行う。操作が行える最大の回数を答えよ。 制約 1 ≦ |s| ≦ 200 000 方針 ①前から順に操作したいが、次の例のように後ろを走査した後に前が再…

A - Kenken Race 概要 横一列に並んだNマスがあり、マスAとマスBにはコマが置いてある。マスAのコマをマスCに、マスBのコマをマスDに移動できるかどうかを判定せよ。ただし、以下の条件がある。 コマは右に1マスもしくは2マス移動できる 移動先のマスが壁'#'…