問題概要 4*n+1で表される数をH-numberという。1*hでしか表せないH-numberをH-prime numberという。二つのH-prime numberの積で表されるH-numberをH-semi-prime numberという。[1..k](k 解法 篩をかける。計算量が読みにくいけどやってみると余裕で間に合う。

問題概要 長さN( 解法 xorとってbitcountが1なら辺を張る。後は二部マッチングの分だけ減らすことができる。

問題概要 正整数n(区間[l,r]を全て列挙する問題。 解法 しゃくとり法。

問題概要 H*W(H,W 解法 各マスについて列の状態を保持しながらビットdpする。 時間 30分かかった。遅い。入力の0と1を間違えてしかも2回も間違えた。入力読み込んだ時点で自分に分かりやすいようフリップしとくべきだった。

問題概要 2次元格子上にn( 解法 とりあえず座標圧縮しておく。y座標の小さい点から順に処理をしていく。数え方としては、蓋をするときにまとめてカウントする感じ。区間に数字を足し込む操作があるのでBITを使って頑張る。

問題概要 分かりにくいけど、サイズ2以上の強連結成分の個数を求める問題。 解法 実際に強連結成分分解する。

問題概要 N*N(N 解法 各点の頂点に流量1,コスト-X[i][j]と流量INF,コスト0の制限を付けて自然に有向グラフをつくり、左上から右下へ流量Kの最小費用流を求めればよい。辺の使用量が一定なので負のコストも簡単に解消できる。

問題概要 長さN(=0, A[i] = (A[i-1]+A[i+1])/2 - 1 (i in (1,N))となる。A[N]のとりうる最小値を求める問題。 解法 最小値はA[N]について単調なので答について二分探索する。答を決めたらそれ以外の値は連立一次方程式を解くことで求めることができる。

問題概要 問題文がかなり不親切なので適当に補完してまとめるとこんな感じ。 N個の山があるNimがある。同時に1~M個まで山を選んで石を1~K個まで自由に取り除くことができる。最後に取った方が勝ち(=有効手が選べない方の負け)。どちらが勝つか判定する問題。…

問題概要 長さn( 解法 All nearest smaller valuesという有名問題。

問題概要 f(0)=1, f(n)=b^f(n-1)のとき、f(i)の下n桁を求める問題。n 解法 b^kをmod mで見るとρのように尻尾とループの部分ができる。ループの部分の長さはphi(m)の約数になるので、ループの部分の長さはphi(m)だと思ってよい。最終的にb^k mod mが知りたい…

問題概要 n個の重み付き区間[a[i],b[i]), w[i]が与えられる。[M,E]を全て被覆するのに必要な最小コストを求める問題。n 解法 これとほとんど同じ。座標圧縮すれば定数を多少軽くできる。

問題概要 4*N(N 解法 S=4とする。3^S*S(全てのビットに対し、部分集合を選んで、その部分集合に含まれるビットは横向きになっていると思う)で遷移行列を計算して後は行列累乗で加速する。

問題概要 N( 解法 2*T位までコインの枚数制限ありと制限なしで最適な支払い枚数を計算しておく。コインの支払い枚数最小化の問題はナップサック問題の重さをコインの価値で置き換えて、価値を1で置き換えて、maxをminに置き換えるだけでよい。

問題概要 T( 解法 新たにはさんで行くタイプのDP。ways[i][s] = {color [0,i)までで作れるサイズsの集合の個数}とするとways[i+1][s] = sum_{max(0,s-num[i])

問題概要 長さN(区間和で、絶対値がtに最も近いものを求める問題。 解法 しゃくとり法でやる。累積和をソートしておくと、http://d.hatena.ne.jp/komiyam/20120802/1343894601 でのfをf( [l,r) ) = accum[r] - accum[l] (ソート後)がt以上、とできるのでよい…

問題概要 N(区間が与えられる。これを交わらないいくつかの列に分解したい。最小いくつにできるか復元付きで求める問題。 解法 左端の小さい順に貪欲にやればよい。左端でソートしてから右端のmin-heapに突っ込んでいけばよい。

問題概要 N( 解法 1回の反復で係数行列がどう変化分かるので後は行列累乗するだけでよい…のだけどこれだとO(log M * N^3)でTLEする。この係数行列はかなり疎で、定数項以外の係数は1か0しか出てこないので置換で表すことにする。つまり、1回の操作でa[i]はa[…

問題概要 長さL[i]( 解法 蟻本p.129。見るからに二分探索。まったく本質的ではないけれど、小数点以下何桁出力、みたいなのはEPSを足さないとひどい目にあうことがある。 ソース略

問題概要 (A[i]*k, B[i])(k in [1,inf) i in [1..N( 解法 優先順位付きキューから取り出しては時間を進めて再び突っ込んでいく。

問題概要 循環小数が与えられる。ただし循環の単位は分からない。分母が最小になるように有理数で表す問題。 解法 反復単位がどうなってるか全探索する。制約がよく分からなかったので多倍長で。

蟻本を参考にして解いた。ところで蟻本はBITの部分だけ1-indexed、閉区間で扱っているけど、個人的には他と同じように0-indexed、半開区間で考えた方がいろいろ楽になる気がする。ソース略。

問題概要 N( 解法 半分全列挙だけど、0を適当に取り除いたりユニークしたりする。

問題概要 重み付き無向グラフが与えられる。0からN-1までの経路のうちK+1番目に大きい値を最小化したい。最小値を求める問題。 解法 解について二分探索する。判定関数は、コストx以上なら1、それ以外なら0を重みとして0からN-1までの最短路がK以下になるか…

問題概要 長さN( 解法 Aを反転させれば良いので、広義単調増加に限定してよい。dp[i][j] = {B[i] = j番目に小さいA[k]の値でのときの最小値}とすると絶対値を含む漸化式が出てくる。しかし、どうせ単調増加という条件があるので、絶対値は外すことができて結…

問題概要 bool変数X[i] (|X| 解法 2SATを解くのと同じように考えれば解ける。例えばa&b=1だと!a->a, !b->bと置き換えれば良い。

問題概要 N*N(N区間内の値を全てフリップする。もう一つは指定された要素を答える。 解法 2次元のRange Sum Queryを利用すれば解ける。RSQはsegtreeでやってもよいが、練習がてらBITを用いて解いてみた。蟻本で紹介されてるのはBIT2本で1次元のRSQを処理して…

問題概要 方程式 A + B*x = C (mod 2^k)を満たす最小のxを求める問題。解がなければ指摘する。

問題概要 2次元平面上にN( 解法 まず凸包を作る。整数座標なので凸包は100個ちょいしか残らない。N^3だとTLEするのでキャリパーっぽくN^2でやる。底辺の2点の組み合わせを全探索する。もっと速く解けるらしい。

問題概要 10*10の盤面があり、各マスは黒か白である。任意の大きさの正方形で全ての黒いマスを被覆する。このとき、はみ出したり白のマスに重なってはいけない。最小枚数を求める問題。 解法 基本方針はBBだけど、下界は相当緩くてよい。正方形を考えるとき…