問題 問題概要 {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| …

問題 問題概要 N頂点M辺の距離のある無向グラフが与えられる. 頂点S,TからA,Bが各々頂点T,Sに最短路で向かうとき,AとBがすれ違わないような組み合わせをmod 1e9+7で求めよ. 1 <= N <= 105, 1 <= M <= 2*105, 1 <= d <= 109 解法 問題の流れ : Dijkstra -> DP…

問題 問題概要 N個の整数 {a_i} (i=1,2,..,N) が与えられる. 各 i = 1,2,..,N について min_(1<=j<=N) (a_j + (j-i)2) を求めよ. 1 <= N <= 2*105, 1 <= a_i <= 1012 解法 a_j + (j-i)2 = i2 + (-2ji + j2 + a_j) より, 各iについて, (-2ji + j2 + a_j)を最…

問題 問題概要 N頂点M辺のグラフが与えられる.各辺には種類c_iがある. 頂点1からNに行くには最低何種類のパスをまたぐ必要があるか. * 種類1 -> 2 -> 1 は3種類と数える. 2<=N<=105, 0<=M<=2*106, 1 <= c_i <= 106 解法 a b cのような辺に対して, (a,c) <=> …

問題 問題概要 N個のノードのグラフの全点間最短距離A_ijが与えられる. これを満たすような辺の張り方は存在するか.あるなら辺のコストの総和を求めよ. 1 <= N <= 300, 1 <= A_ij <= 109 解法 各頂点間について,A_ijの辺があるか,辺が存在しないかのいずれか…

問題 問題概要 2つの山にX,Y個の石が置かれている. プレイヤーは一つの山から2i個(2<=2i<=XorY)とってもう片方の山にi個置くことができる. 石が取れなくなったら負け. どちらのプレイヤーが勝つか. 1 <= X,Y <= 1018 解法 とりあえず実験してみる. X<=1 & Y …

問題 問題概要 A(x1,y1), B(x2,y2), C(x3,y3)が与えられる. ABC内部に半径の同じ円を2つ描く時,最大の半径を求めよ. 解法 BC,CA,ABをそれぞれa,b,cとする. またcが最大の辺とする. 内接円の中心O,半径r, 内部に描く二つの円の半径をxとすると,以下のようにな…

問題 問題概要 N個の数列{a_i} (1<=i<=N)に対して, 数字iを選び,全ての1<=j<=Nに対し, a_(i+j)%N を -jする という操作を行う. 全てのaiを0にすることができるか. 1 <= N <= 105, 1 <= a_i <= 109 解法 1回の操作を行うと,合計は+N(N+1)/2されるので,合計を…

問題 問題概要 N個の点(xi,yi)と色(B|W),自然数Kが与えられる. 幅Kの市松模様で,(xi,yi)を与えらえれた色にするという希望を最大何個満たすことができるか. 1 <= N <= 105, 1 <= K <= 103, 0 <= xi,yi <= 109 解法 全てのマスに対して,(x,y)の色C(x,y)は,C(x…

問題 問題概要 a[i] (1<=i<=N) の長さのロープN本がある.これらは順に繋がっている. 長さがLより小さくならないように一つずつ結び目を解くことができるか,できる時解き方を出力せよ. 2 <= N <= 105, 1 <= a_i,L <= 109 解法 解くことができる <-> a[i] + a[…

問題 解法 前提知識 分割数 蟻本にも載ってる. この問題は,X=sum(death)=sum(相手チームのkill)とすると, kill数が全員同じ -> sum(death_i) = X, death_i は昇順の通り数 -> すなわち分割数,DPで出せる kill数が全員違う -> sum(death_i) = X, death_i の順…

問題 問題概要 長さNの正三角形ABCがある. AB上にあり,AP=Xであるような点からBCと平行に光を放つ. この光は,辺とそれまで通った点に反射する. 光はどれだけの長さを通るか. 2 <= N <= 1012 解法 a * b の平行四辺形に光を放った時の光の長さをf(a,b)とする…

問題 問題概要 N頂点M辺の連結な無向グラフが与えられる. 2個以上の頂点を通り,1頂点を1回以内しか通らず, 両端の少なくとも一つと繋がっている頂点を全て通るようなパスを求めよ. 解法 適当なパスを決めて,両端を条件を満たすか確認し,greedyに伸ばしていけ…

問題 問題概要 N x Mのグリッドが与えられ,各々に0,1のいずれかが書いてある. 1のマスで閉路はできないようになっている. Q個のクエリx1_i, y1_i, x2_i, y2_i (1<=i<=Q)が与えられる. x1_i <= x <= x2_i, y1_i <= y <= y2_i に含まれる,1の連結成分はいくつ…

問題 問題概要 N匹の猫がいて,それぞれが色のついた帽子をかぶっている. N匹の猫に,自分以外の猫の帽子の色は何種類あるかという質問をした時の答えa[i] (1<=i<=N) が与えられる. 条件を満たすような帽子のかぶり方は存在するか. 1 <= a[i] <= N-1, 1 <= N <…

問題 問題概要 文字列Sが与えられる. 1回だけ,Sの i〜j文字目(1<=i

問題 問題概要 N個の整数からなる数列が与えられる. x,yについて,a[y]にa[x]を足す,という操作を繰り返して, a[0] <= a[1] <= ... <= a[N] を満たすようにしたい. 条件を満たす2N回以内の操作を出力せよ. そのような操作が存在することは保証されている. 2 <…