問題概要 15パズル風に空きマスに数字を移動させるゲームがある(ルールの詳細は略)。クリアできるのであれば最短手数を求める。無理なら指摘する。 解法 幅優先探索で間に合うらしい。状態の合流があるとはいえ意外。 以下の自分の実装では盤面をcharで圧縮…

問題概要 s個のビーズで数珠を作る場合の数を求める問題。色はc色を自由に選べる。s*c 解法 ポリアなどで反転を考えない場合の答を出す。それから左右対称な場合の数以外についてだけ2で割ればよい。左右対称な場合の数を数え上げるのは簡単。

問題概要 maximum closure problemの最適解と、それを達成するために必要な最小頂点数を求める問題。 解法 よく知られているように、最小カットでsource側に分離される頂点が答。最小性の証明についてはよく理解できていない。

問題概要 色々書いてあるけど、要するにヒストグラムの中の最大長方形を求める問題。 解法 All nearest smaller valuesの応用。

問題概要 n( 解法 コインの価値が高い順にCを越えないよう貪欲に詰めていく。次に、価値が低い順にCをぎりぎり越えるように貪欲に詰めていけばよい。うまく行く理由としては、まず前半の価値が高い順に越えないよう貪欲に詰めるのは倍数列の制約から明らかと…

問題概要 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個まで自由に取り除くことができる。最後に取った方が勝ち(=有効手が選べない方の負け)。どちらが勝つか判定する問題。…

問題概要 3つの文字列がある。全ての文字列を部分文字列に含むような最小の文字列の長さを求める問題。文字列長 解法 まず他の文字列に含まれる文字列は消す。その後、Z-algorithmでA-B, B-Cについてlongest prefixを求め、その分をA+B+Cから引く。順番につ…

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

問題概要 (1,1)から(N,M)(N,M 解法 全てのワープホールをトポロジカルソートしておく。ways(k,t)を「[0,k)までのワープホールが機能しているときの(1,1)からt番目のワープホールの入り口までの経路の個数」とする。ways(k,t)は除原理を用いることによりO(1)…

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

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

問題概要 0,1がかかれたH*W(H 解法 各行についてどこを反転するか全探索する。各列に対しては反転するか反転しないかは大きくなるようなのを選べば良い。愚直にやるとO(2^H*H*W)だけど、前処理かけてxorで求められるようにしておくとO(2^H*W)に落ちる。

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

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

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