TL;DR set<int> st; lower_bound( st.begin(), st.end(), 0); // これは O(NlogN) lower_bound( 0 ); // これはO(logN) 解説 この前のABCでハマってしまった. 上のコード 下のコード 異様に遅いしlower_boundあたりがもしかして O(N) になってないか?と思って書き</int>…

とりあえず考えること 要素/総和のmod/パリティに注目する 操作回数を求めることができるか(特に総和を用いて) 逆操作が可能か 操作が単純な操作に分解できるか 階差数列を考える 数列2つを一致させるなら差を取る 操作の縮約ができないか/周期を持たないか …

問題 解法 典型的な文字列AとBの編集距離を求める問題において, B = "yahoo" と固定したバージョンになる. (は正規表現における閉包) i=1,2,.. として 部分文字列S[0,i) を最終的な状態 "yahoo"* の前半と一致させることにしよう. それまでの最小の編集距離…

問題 解法 a_i は K と共通の因数しか注目しなくて良いことがわかるので, a_i = gcd(a_i, K) とみなして良い. Kの約数は高々 2sqrt(K) しかないので(エラトステネスの篩をやっていくとわかる), a_i として現れる数は O(sqrt(K)) しかない. 定跡としてこの分…

問題 解法 制約から半分全列挙をエスパーする 2Nとあるので半分と後半に分けてみる 前半の赤色がa文字とすると,前半の青色はN-a,後半の青色はaになる 前半の赤色=reverse(後半の青色) かつ 前半の青色=reverse(後半の赤色)である必要がある どちらも全列挙し…

問題 解法 明らかに,解説で除いている3ケースはわかる. そうでないとき, 個数をy個とすると無限に買い続けられるときは y = C の周りを振動する 無限ループするので,yが周期をもつ-> C+1 <= y <= C+B の値を全て取りうる? .. そうであればC+1-B>=0を判定すれ…

問題 解法 考察 XOR swapによりswapが可能( a ^= b, b ^= a ) これによってa_i, a_j (i!=j) で操作ができる あるbitだけ立っている要素があればそれを使ってそのbitを自由に立たせることが可能 そのような要素は {1101, 1001} のような1bitだけ異なる数があ…

問題 解法 良解説を聞くのが良い とりあえずsortして分布(c[x] := #( a_i=x なる i ) )をまとめておく 1人ずつグループに入れていこうとすると,分布(k人グループが何個できているか)を持たないといけないので状態が指数時間になって無理 視点を変えて,人数が…

問題 解法 sample2をじっと見ると,必要条件として X_i, Y_i の和のパリティが全て一致する というのがあることがわかる パリティに注目するのはよくやるのでこれは気づかないとどうにもならない. 実際に,そのときdとして1を20個/21個用意すれば300点は取れる…

問題 解法 まず十分条件を列挙していく. 0-indexedとして, s[0] = 1 s[N-1] = 1 s[i] = s[N-1-i] D問題でもそうだったが,自明な必要条件が必要十分条件になっているというパターン. s = "100..01.." として,k番目に初めて1が現れるとする. このとき,1つの辺…

問題 解法 関連した以下のような簡単な問題について考える. n個の0があり,K回だけ 0<=i < n なるa_i を+1 する操作を行う. 数列は何通りできるか. これは以下のようなO(NK) の DPで解くことができる.(普通にコンビネーションでも解ける) def : dp[i][j] := (…

ミス o rep(k,N) rep(i,N) rep(j,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]); x rep(i,N) rep(j,N) rep(k,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]); なぜか Warshall-Floydの証明を考えれば明らか. 証明 Warshall-Floydが何をしてい…

問題 解法 本番中の考察 何回原点に戻ってくるかでXの係数が変わるのでこの回数を決めうちして1回O(N)でやったら部分点取れそう 部分最適構造( [l,r) 間のごみの最適なとり方が x=l,..,r として [l,x),[x,r) の最適なとり方を各々やってきたうちコスト最小の…

問題 問題概要 '(' と ')' のみからなる文字列Sがある. 1 <=i < j <=|S| で, S[i :j] が対応が取れているのは何組あるか. 1 <= |S| <= 105 思考と反省 考えたこと 構文木作れば k 個の子を持つ親を見つける度に kC2 足していけば出来る -> 再帰で実装しよう …

問題 問題概要 自然数N,M と 数列 {a_i} (0 <= i < N) が与えられる. 各 j = 1, ... ,M について, jと互いに素なa_iの要素の数を求めよ. 1 <= N,M,a_i <= 105 解法 各jについて, 互いに素でない <-> 共通因数を持つ a_i の数を考えることにしよう. j = 5 の…

問題 問題概要 サイズNの数列からサイズKのsubarrayを選び,subarrayのminを取り除く試行をQ回行う. 取り除いたminのうちの max - min をminimizeするように試行を行った時のminを求めよ. 1 <= N <= 2000, 1 <= a_i <= 109 解法 思考箇条書き 単純に小さい順…

問題 問題概要 NM のハンコをハンコがマスに収まるような範囲の全ての場所でHW のマスに押す. ハンコで黒く塗られるのは何箇所か求めよ. 1 <= N,M <= 103 ,1 <= H,W <= 109 解法 まず for(ハンコを押した回数) for(ハンコの全てのマス)のループの順序を入れ…

問題 問題概要 昇順に並んでいる数列{x_i} (1<=i<=N) が与えられる. (i, j, k) , (i < j < k) の組で, x_j - x_i <= D x_k - x_j <= D x_k - x_i > D を満たす組の総数を求めよ. 3 <= N <= 105 解法 補集合を考える. x_j - x_i <= D, x_k - x_j <= D を満た…

問題 問題概要 ブロックに0,A,B,A+Bのいずれかの得点をつけることができる 合計Kの得点をつける塗り方をmod 998244353で求めよ. 1 <= N,A,B <= 3105, 0 <= K <= 181010 解法 単純にDPを立てると,状態がO(NK)とかになってしまうので間に合わない. ここで問題…

問題 問題概要 1~Nの数字が書かれた白のボールと黒のボールがN個ずつ,合計2N個ある. 白と黒それぞれに注目した時,どちらも順番通りに並んでいるようにするには最低何回のswapが必要か. 1 <= N <= 2*103 解法 考察段階から箇条書き 最終状態が決まるとそのswa…

ab = ab mod p-1 (mod p) が成り立つ. proof. フェルマーの小定理より ap-1 = 1 (mod p)なので,mod pにおいて ab = a^( (p-1)(floor(b/(p-1)) +(b mod (p-1))) = ( (ap-1)floor(b/(p-1))) * ab mod (p-1) = ab mod (p-1)

問題 問題概要 0,1が書かれているh*wの盤面がある. 行または列を全て反転する操作が何回でもできるとして, その中の要素が全て1であるような長方形の最大の面積を求めよ. 解法 ここの方法がわかりやすかったのでこれでやった. ex. 盤面 1 0 1 0 1 0 1 0 1 1 …

問題 問題概要 N要素の数列{a_i}, {b_i} が与えられる. Xor_(1<=i,j<=N) (a_i + b_i) を求めよ. 解法 a_i + b_j のkビット目の1の数の偶奇を考える. x + y = ( x & y ) << 1 + ( x xor y ) から, (a_i , b_j のkビット目の立っている数) * N + (k-1ビット以…

問題 問題概要 N要素の整数列{a_i}を以下の作業を繰り返して{b_i}に一致させる. - いくつかの要素を選び, a_i をa_i % k に変化させる. その際いくつ選んだかに関わらず コスト2kを払う 必要な最小コストはいくらか. 1 <= a_i, b_i, N <= 50 解法 a_i から a…

問題 問題概要 サイズN, 各要素が30000以下の次の条件を満たす数列を求めよ. - 全ての要素のgcdは1である(全ての要素が互いに素ということではない) - 全要素の和をSとして,全てのiに対して gcd(a_i, S-a_i) != 1 解法 gcd(a_i, S-a_i) != 1 <-> gcd(a_i, S)…

問題 問題概要 N組の計2N個の整数x_i,y_iを赤/青に分けていく. (Rmax - Rmin) * (Bmax - Bmin) を求めよ. 1 <= N <= 2*105, 1 <= x_i,y_i <= 109 解法 全体のmax,minであるma = max_i(max(x_i,y_i)), mi = min_i(min(x_i,y_i) は必ずR/Bに塗られているため, …

問題 問題概要 N頂点M辺の重み付き無向グラフと整数Xが与えられる. この辺を2色に塗っていく. 次の条件を満たす辺の塗り方の数をmod 1e9+7で求めよ. - 2色どちらの色も含む全域木が存在して,そのような全域木の最小コストがXである. 1 <= N <= 103, 1 <= M <…

問題 問題概要 1が根であるN頂点の根付き木が与えられる. また数列{x_i} (i=1..N) が与えられる. 木に白/黒と非負整数を割り振り,自身を含めた子に含まれる自身と同じ色の頂点の数の総和がx[i]であるようにしたい. そのように割り振ることはできるか. 解法 …

問題 問題概要 N人から何人か選んで複数回レースをする. N人はKクラスに分かれている. また,N人の実力は決まっており,レースをするとその実力通りの順位になる. レースをした時,自分より順位が上の人全員が自分より上のクラスであるならその人は勝利となる. …

問題 解法 M=1,2 の場合は容易に解ける. 以降ではM=3とする. まず下準備として押す場所で同じ場所が連続して来る場合は結合して一つの区間にしておこう. とりあえず一番近い指を使う貪欲を考えてみると, p1 <--> 指1 <-> p2 <--> 指2 <-> 指3 , s1=2, t1 = s…