B - Two Contests 概要 Ｎ個の区間[Li, Ri]が与えられる。この区間を2つのグループに分け、それぞれのグループごとの区間の共通部分の長さの和の最大値を求めよ。 制約 2 ≦ N ≦ 10^5 1 ≦ Li ≦ Ri ≦ 10^9 方針 maspyさんのブログを参考に考察を進めたい…ので…

E - Balanced Path 概要 H × WのグリッドとH × Wの整数の配列A, Bが与えられる。 グリッドを右もしくは下に移動して(0,0)から(H-1,W-1)に移動する経路を考える。同時に経路に対応するA, Bの数値のいずれかを赤、もう片方を青色に塗り分ける。 各経路について…

概要 N頂点の木が与えられる。各辺に色を付けて塗り分けることを考える。同じ頂点から出ている辺に同じ色がつかないように塗り分けることとしたとき、必要な色の種類の最小値と塗り分けの方法を1つ出力せよ。 制約 2 ≦ N ≦ 10^5 方針 色の種類の最小値は、各…

B - Reversi 概要 長さNの正整数列Cが与えられる。この数列に以下の操作を好きなだけ行う。 C[i] = C[j] (i 上の操作の結果出来上がる整数列の種類数を答えよ。(mod 10^9 + 7 して出力) 制約 1 ≦ N ≦ 2 * 10^5 1 ≦ C[i] ≦ 2 * 10^5 方針 大まかにはDPを使う…

F - Must Be Rectangular! 概要 2次元平面上にN個の点がプロットしてある。i番目の点の座標は(x[i], y[i])と表される。以下の操作を可能な限り繰り返す。 次のような任意の4か所(a, c), (a, d), (b, c) , (b, d)のうち、ちょうど3か所に点がプロットしてある…

B - Sorting a Segment 概要 0からN-1のN個の整数の順列Pと整数Kが与えられる。この順列を用いて下記の操作を行った後にできる数列の種類数を答えよ。 順列Pの連続するK項を昇順に並べ替える 制約 2 ≦ N ≦ 2 * 10 ^ 5 方針 昇順にするK項の最初の各項につい…

E - Second Sum 概要 1からNまでの数字の順列Pが与えられる。1≦ L 制約 2 ≦ N ≦ 10^5 方針 各L, Rについて2番目に大きい項を逐一探しに行くと計算が間に合わない。あるP[i]が何回足されるかを考える。 P[i]が足されるときのL, i, Rの関係としては、P[L]からP…

概要 下記の制約があるNプレイヤーの総当たり対戦を考える。 各プレイヤーは1日1回しか試合できない プレイヤーiがj番目に対戦する相手はA[i][j] このとき、全ての試合が終わるまで必要な日数の最小値を求めよ。なお、制約下で総当たり対戦ができない場合は-…

C - 菱型カウント 概要 R行C列のマスがあり、各マスにはoかxのいずれかが記入されている。 整数Kが与えられる。次のような(x, y)の組(R ≦ x ≦ R + K - 1, C ≦ y ≦ C + K - 1)の個数がいくつあるか答えよ。 |i -x| + |j - y| ≦ K - 1を満たすi, j については…

概要 0, ..., N-1と番号付けられたN個のハスが横一列にならんでいる。現在ハス0にいる。 正の整数A, Bを選び、0, A, A - B, 2 * A - B, 2 * A - 2 * B, ...の順番で対応する番号のハスを行き来し、最終的にハスN-1に到達したい。ただし、同じハスに2度行くこ…

概要 整数Nが与えられる。高橋君、青木君の二人ゲームを考える。 ・最初の整数を1とする。 ・現在の整数をxとするとき、プレイヤーはxを2xもしくは2x+1に置き換える操作を交互に行う。 ・先手は高橋君 整数がNを超えたとき、最後に操作を行ったプレイヤーを…

F - Permutation Oddness 概要 数列{1, 2, ..., N}の順列{p1, p2, ..., pN}の奇妙さをΣ|pi - i| で定義する。 Σ|pi - i| = k なる順列の個数を求めよ。(mod 10^9 + 7 して出力) 制約 1 ≦ N ≦ 50 0 ≦ K ≦ N * N (もとの問題はN, Kともに小文字) 方針 DPが使え…

F - Absolute Minima 概要 関数f(x)が与えられる。関数f(x)は最初f(x) = 0の定数関数である。 クエリがQ個与えられるので、それに従い操作する。クエリは下記2つ。 更新クエリ："1 a b"の形で与えられ、f(x) 求値クエリ："2" の形で与えられ、f(x)の最小値を…

F - Colorful Tree 概要 N頂点の木が与えられる。辺iは頂点ai, biを結び、色ciがついている。また辺の長さはdiである。 Q個のクエリが与えられる。クエリiではxi, yi, ui, viが与えられ、下記の問いに答えよ。 色xiの辺の長さがyiになったとき、uiからviまで…

E - Virus Tree 2 概要 N頂点の木を下記の要領で塗り分ける。塗り分けにK色まで使えるとき、塗り分けの通り数を求めよ。(mod 10^9 + 7 して出力) 2つの異なる頂点x, yについて、xとyの間の距離が2以下ならxとyは異なる色で塗られる。 制約 1 ≦ N, K ≦ 10^5 …

E - Hopscotch Addict 概要 有向グラフが与えられる。始点Sから終点Tまでの経路で長さ3がの倍数のもののうち最小のものについて、その長さを3で割ったものを出力せよ。（けんけんぱで移動できるか） 制約 2 ≦ N ≦ 10^5 0 ≦ M ≦ min(10^5, N * (N - 1)) 方針 …

概要 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}のケースを考える。このとき該当する部分列…

概要 整数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の長さが答え。…

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

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

E - Roadwork 概要 数直線上の座標0にQ人の人がいる。人iは時刻Diから数直線上正の向きに毎秒1ずつ進む。 数直線上ではN回の工事が行われており、工事iでは時刻Si-0.5から時刻Ti-0.5の間、座標Xiが通行止めである。 人iは最初に通行止めにあった時点で停止す…

E - Cell Distance 概要 N行M列のマス目にK個コマを置く。すべてのコマの置き方について、下記の合計を求めよ。 コマ1が(x1, y1)、コマ2が(x2, y2)、… 、コマKが(xK, yK)に置かれたとき、1 ≦ i 制約 2 ≦ N * M ≦ 2 * 10^5 2 ≦ K ≦ N * M 方針 行、列独立に考…

令和ABC初回。残念ながらunratedでした。F - XOR Matching 概要 整数M, Kが与えられる。長さが2^(M+1)の数列aで下記を満たす数列が構築できる場合、その数列を1つ出力せよ。できない場合-1を出力せよ。 要素に0, 0, 1, 1, ... 2^M, 2^Mをもつ a[i] = a[j] と…

B - LRUD Game 概要 H行W列のマスにコマが1つおいてある。先手と後手はそれぞれ'L', 'R', 'U', 'D'からなる長さNの文字列をもっている。 先手と後手は交互に文字列の先頭から、文字が表す方向にコマを1マス動かすことができる。また動かさなくてもよい。 コ…

D - へんてこ辞書 概要 N頂点N辺の有効グラフとN項の数列bが与えられる。各頂点から出る辺は1本であり、b[i]は頂点iから出ている辺を表す。 頂点aからスタートし、k回移動した後にいる頂点番号を答えよ。 制約 2 ≦ N ≦ 10^5 1 ≦ k ≦ 10^100000 共通方針 この…

D - Flipping Signs 概要 N項の数列Aが与えられる。「1からN-1までの番号iを選び、A[i-1]とA[i]に-1を乗算する」という操作を好きなだけ行う。操作終了後の数列をBとするとき、Bの和の最大値を求めよ。 制約 2 ≦ N ≦ 10^5 -10^9 ≦ A[i] ≦ 10^9 方針① いろい…

C - GCD on Blackboard 概要 N項の数列Aが与えられる。この数列のうち1項を好きな数字に変えて数列全体のGCDを計算する（数字を変えなくてもよい。）。GCDの最大値を求めよ。 制約 1 ≦ N ≦ 2*10^5 1 ≦ A[i] ≦ 10^9 全体の方針 数字を変更する項を固定する。 …

D - Handstand 方針 反転する区間は0が続いている区間のみを考えてよい。 すると問題は、0が続いている区間をK区間ずつ1に反転していって、1が連続する区間が最大になるものを求めればよい。これは尺取り法でO(N+K)で求めることが出来る。 感想 下記ブログを…