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

問題 問題概要 英小文字から成る文字列sが与えられる. 両端以外から,その両隣が同じ文字でないならば文字を1つ取り除け,文字が取り除けなくなったら負けというゲームをする. 先手と後手どちらが勝つか. 解法 ゲーム終了時の文字列は"abab..ab" または "abab.…

問題 問題概要 N個の自然数から成る数列a[i] (1<=i<=N) が与えられる. a[i] の部分列の和 S_1, S_2, ... , S((2N)-1) の中央値(すなわち{S}を昇順に並べた時のS(2N-1)を求めよ. 1 <= N, a_i <= 2*103 解法 S_0 = 0 として考える. ある S_j がいくつかの a_i …

問題 問題概要 N個のtask,そのメモリ使用x[i] (1<=i<=N), タスク依存関係a[i] (2<=i<=N) が与えられる. iのタスクはa[i]のタスク実行後にしか実行できず,その中でもタスク1は他の全てのタスク実行後にしか実行できない. メモリx[i]はタスクi実行後に消すこと…

問題 問題概要 羊(S)と狼(W)が円状に並んでいる. Sは両隣が同じ動物の時o,そうでない時xと答える. Wは両隣が同じ動物の時x,そうでない時oと答える. 動物の数Nと,各動物の答えS(|S|=N)が与えられる. 答えを満たす動物の並びが存在すればその内1つを,存在しな…

問題 問題概要 ABから成る文字列S,Tが与えられる。 次の操作をいくらでも行うことができる。 1. 'AA' -> 'B', 'BB' -> 'A' の変換 2. 'AAA' または 'BBB' の消去 以下のQ個のクエリを処理せよ。 ai,bi,ci,di(1<=i<=Q)が与えられる。 Sの部分文字列S[ai:bi+1]…

問題 問題概要 N個の自然数a[i] (1<=i<=N)と自然数Kが与えられる。 その組み合わせからなる2Nの集合を考え、そのうち部分和がKを超えるものを良い集合とする。 a[i]を含む任意の良い集合Aに対し、A\ {a[i]}(Aからa[i]を除いた集合)も良い集合であるならばa[i…

問題 問題概要 'F'と'T'からなる文字列Sと座標x,yが与えられる. Fは1つ前進,Tは左右いずれかに90°回転の命令を表す. (0,0),x軸正方向向きからSの命令列を実行した時,(x,y)にいくことができるか。 1<=|S|<=8*103 解法 x,y各方向について,Fの塊のたびに(正規表…