問題 解法 前提知識: 凸包 (ググればいっぱい出てくる) Rが十分に大きいので数学的にINFだとして考察していく. 各点に落ちるような領域は与えられた二点の全ての組を取った垂直二等分線で区切られる(ボロノイ図と言うらしい) R=INFなので,この領域が有限領域…

問題 問題概要 N個の区間[l_i,r_i],自然数Mが与えられる. 1 <= d <= Mについて,dの倍数を含む区間はいくつあるかそれぞれ答えよ. 1 <= N <= 3*105, 1 <= M <=105 解法 各dについて dの倍数を含むような区間を数え上げていく. 愚直にやろうとすると [1,M] の …

問題 問題概要 要素数Nの数列{a_i}とコストPが与えられる. 任意の場所へのワープにはコストP,隣接するiからjへのの移動にはmax(0,a[i]-a[j])かかる時,全ての点を訪れる最小コストを求めよ. 2 <= N <= 2*105, 0 <= P,a[i] <= 109 解法 1 普通のDP 解説が詳し…

問題 問題概要 自然数K,Qが与えられる.以下のクエリQ個を処理せよ. 1. 配列に値Xを挿入する 2. 配列のK番目に大きい値を出力し,削除する 1 <= Q,K <= 2*105, 1 <= X <= 1018 解法 想定解で解いた. minキューとmaxキューを用意し,maxキューにはK番目に小さい…

問題 問題概要 N頂点の0を根とする木が与えられる. 木を白黒に塗る. ある頂点が黒の時,その子が全て黒であるという制約を満たしながら塗る時,黒の数がKであるのは何通りか. 解法 dp[i][j] := (i頂点以下で黒がj個の場合の数)とする. 初期値は dp[i][0] = 1, …

問題 問題概要 直線上のN個の点x_iが与えられる. 1回に合計距離Lまでの点から点への移動が可能として, 以下のQ個のクエリを処理せよ. - a,b間の移動には何回移動が必要か 1 <= N <= 105, 1 <= Q <= 105 解法 r[i][k] := (iから2k回正方向に移動してたどり着…

問題 問題概要 N個の荷物の重さwi,価値vi,色ciが与えられる. 重さW以下,色C色以下で達成できる最大価値を求めよ. 1 <= N <= 100,1 <= W <= 105, 1 <= C <= 50 解法 dp(i,j) := (i色以下,重さj以下で持てる最大価値) としてdp(i,j)を更新していく. w,vは色ご…

問題 問題概要 N頂点M辺の無向グラフと各辺の距離が与えられる. また各頂点に対してコストc[i]が与えられる. 各i (1<=i<=N)に対し min_j(2dist(i, j)+c(j))を求めよ. 2 <= N <= 2105, 1 <= M <= 2*105 解法 Dijkstraで各頂点とそのコストを初期位置としてキ…

問題 問題概要 0,1からなる行列で,どのMxMの小行列をとってもいずれかの要素に0が含まれる行列をM-free Matrixという. 整数xが与えられ,1の要素数を最大化したNxNのM-free Matrixで,1の要素数がxであるようなN,Mを答えよ. というクエリがt個与えられるので各…

問題 問題概要 整数N,X,Y,Zが与えられる. 整数1〜10から成り,XYZを含む要素数Nの数列をmod1e9+7で求めよ. なお{a_i}がXYZを含むとは sum(x<=i

問題 問題概要 英小文字から成る文字列Sが与えられる. Sの部分列でないような最短の文字列を求めよ. ここでS'がSの部分列とは S'[i] = S[a_i] (1<=i<=|S'|) なる単調増加なa_iが存在するものとする. 解法 まず,S[i,N)で一番最初に出てくる文字j(j='a'〜'z')…

問題 問題概要 {X_i},{Y_i} (0<=i<N, X_i > Y_i) と自然数Mが与えられる. 各i についてX_i,Y_i を選んでいく. ただし,X_iを選べるのはM回までで,i<N-1でM回選んでしまうとそれ以降のY_iは得られない. 得られる合計を最大化せよ. 1 <= N,M <= 105 解法 まず, M>=Nのケースは全てX[i]を選べば良い. その他のケースについて,Z[i] := [0,i) で得られるM-1個以下の和の最大値 とする. </n-1でm回選んでしまうとそれ以降のy_iは得られない.></n,>…

問題 問題概要 Nターンのゲームをする. 値段x[i],価値v[i],費用c[i] が与えられる. 先手は前からx[i]を売るか,それまで得た値段を払ってmax_(i in {1..N})(v[i])を得てゲームを終了する. 後手は先手の価値を最小化するように価値を取り除く 先手の最大スコア…

問題 問題概要 N人で総当たり戦を行う. 勝ち数が同じ場合はindexで順位をつける. Pの確率で結果を間違う時,元どおりの順位となる確率を求めよ. 解法 solve(i,j) := [i,N)が正しい順位で,i人めがj勝の確率 としてメモ化再帰. 答えはsolve(0,N-1)になる. m勝n…

問題 問題概要 {a_i} (1 <= i <= N), {b_i} (1 <= i <= M)が与えられる. 各数列からK個選んで,昇順に並べた時のmax_(1 <= i <= K) (abs(a_i - b_i))を最小化せよ. 1 <= N,M,K <= 105, 1 <= a_i,b_i <= 109 解法 二分探索する. l = -1としないと X = 0とでき…

問題 問題概要 グリッドが与えられる. '.'には広告を置くことができる.また広告は隣り合わないようにしたい. 置ける最大数を求めよ. 1 <= H,W <= 40 解法 グリッドグラフは二部グラフとみなせる. すると二部グラフの最大独立集合を求める問題に帰着できる. …

問題 問題概要 HxWのグリッド,各グリッドに報酬p[i][j], コストc[i][j]が与えられる. 各グリッドに移動すると初回でp[i][j]が得られ, 毎回c[i][j]かかる. (i,j) -> (i+1,j), (i,j)+1, (i,j-1) への移動が可能であるとして(H,j) (1<=j<=W)に最終的にいる時の…

問題 問題概要 N辺の木が与えられる. aとbを繋いだ時にできる閉路の長さを出力せよ,というQ個のクエリに答えよ. 1 <= N,Q <= 105 解法 典型的なLCAの練習問題. a,b間に閉路を作った時, depth[a] + depth[b] - 2 * depth[lca(a,b)] + 1 の長さとなる. メモ ab…

問題 問題概要 N頂点のグラフが与えられる. M辺が与えられ,順番に張っていく. 2頂点がいつ何番目の辺で連結になったか,というQ個のクエリを出力せよ. 1 <= N,M,Q <= 105 解法 永続union-find treeを張って,クエリごとに二分探索. 完全永続でも部分永続でも良…

問題 問題概要 N辺M頂点のグラフが与えられる. 頂点集合S⊆VでSに含まれる二頂点を結ぶ辺が存在しないようなSのmax(|S|)を求めよ. 1 <= N <= 40 解法 解説がめっちゃ丁寧. 半分全列挙して4回ぐらいbitDPする. Vに含まれる二頂点に含まれる辺が存在しないとい…

問題 問題概要 数列{a_i} (1 <= i <= N)が与えられる. 1. 連続する2数を入れ替える 2. 連続する3数を反転させる の2つの操作を行い単調増加数列にする時,1.の最小回数を求めよ. 1 <= N <= 105 , i != j => a[i] != a[j] 解法 2.では奇数番目/偶数番目の数の…

問題 問題概要 N頂点M辺の森と,各頂点にコストが与えられる. 両端の頂点のコストを払うことで辺を作ることができる. なお各頂点は1回までしか使えない. 全て連結にするのに必要なコストを答えよ. 解法 連結成分はN-M個あるため,必要な辺はN-M-1,必要な頂点は…

問題 問題概要 N人をいくつかのグループに分ける. ただし以下の制約を満たす. グループに含まれる人数iは a <= i <= bである. i 人が含まれるグループの数を f_i とした時, c <= f_i <= d. 分け方の総数を求めよ. 1 <= N <= 103 解法 sum(a<=e<=b)f_e*e = N …

問題 問題概要 自然数Nが与えられる. 0 <= u,v <= N であってa+b <= u, ab <= v を満たす非負整数a,bが存在するようなu,vのペアはいくつあるか. 1 <= N <= 1018 解法 a+b = ( (a & b) << 1 ) + (a ^ b)であることから,a+b >= a ^ b. また, a&b = ( (a+b) - (…

問題 問題概要 文字列Sが与えられる. '()', '((()))', '()(())'などの'('と')'が対応している文字列を有効な文字列とする. ')('はダメ. また,'?'はどちらにも変換できる. l ,r (1<=l < r<=|S|)でS[l..r]が有効な文字列であるような組の数を求めよ. 1 <= |S| …