問題概要 頂点数1000以下の単純無向グラフがあり、辺には番号がついている。辺の番号のある区間の辺のみ使って二部グラフをつくるとき、使えない辺のコストの最大値の最小値を1000回くらい求めよ。 解法 10^9を実装しても通るらしい。許さない。区間を平方分…

問題概要 文字列がたくさんある。次のクエリを処理せよ。クエリ: k個目文字列の中に出てくるr番目からl番目までの文字列のoccurrenceの合計を求めよ。 解法 安心安全の筋肉系文字列 & 平方分割。長い文字列に関してはSAで答えを前計算(Aho-Corasickをつかっ…

見た目に反してかなり面白い。わからなかったので解説を見たが、行間が異常に広かったので埋めるのに苦労した。この記事ではちゃんと行間を削った解説を書きます。 問題概要 1~Nまでの番号がついた頂点からなる木がある。各辺の両端の頂点番号の桁数のみわか…

問題概要: 区間をソートした後重複を取り除き、さらにそのi項目にフィボナッチ数列のi項目をかけたものの和を求めるクエリを30000個くらい処理せよ。解法: 最初に思いついたのが、区間を平方分割して、クエリを終点でソートし、sqrt(N)個のsegtreeを始点をず…

http://codeforces.com/contest/668/problem/F問題概要: サイズkのクリークから始め、サイズkのクリークの全点と新たに結ぶことで頂点を増やしていって作ったグラフの全域木の個数を求めよ。解法: 解説は木分解とかしてるしantaさんも意味不明なライブラリを…

VK Cup Round 3のボス問。 問題概要 区間を埋めるクエリと、区間のうちp%以上を占める数をすべて出力せよというクエリに答えよ。クエリ数, 数の範囲は150000, 20 解法 区間のうち1/5以上を占めるものしか出力しなくていいので、区間からランダムに何回か選べ…

問題概要 n人の人がいる。箱がたくさんあり、そのうち1個があたり。 毎日、各人は箱のうちいくつかを見て、その中に当たりが入っていた場合消える。p人まで消してよい。 i: 1~qについて、日数がi日のときに当たりの箱を特定できるような箱の個数の最大値を求…

問題概要: 文字列Sと、文字列X_1,...,X_Nが与えられる。次のクエリをQ個処理せよ。クエリ: l,r,p,qが与えられるので、X_lからX_rのなかで文字列[s_p...s_q]が部分文字列として一番多く現れるものとその回数を求めよ。 解法: suffix array+LCP+sparse tableで…