問題概要 長さN,Mが周期的に現れる点線がある。点線をいくつか選んでどの区間も最大K個以上被覆されているようにしたい。また、端同士で境界ができたらそれは別の線分でカバーされている必要がある。最小いくつの点線を選ぶ必要があるか求め具体的に構成する…

結果。 4/5完。CとEの実装に時間がかかった。Bもバグを生みやすい方法でやってしまったのはまずい。デバッグは結構うまくやれていたと思う。

問題概要 (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に置き換えるだけでよい。

問題概要 頂点数V( 解法 各ノードに対して、そこを通った蟻がk匹死んだときにゴールまでたどり着ける確率をdpで計算できる。更新式は各ノードで左右の部分木のサイズごとの積だけ計算する必要があるけど、このタイプの木DPは計算量がO(V^2)で抑えられている…

問題概要 頂点数N( 解法 BFSするだけ。ただしEの補集合を陽に持つことはできないので、その部分だけ気をつける。

問題概要 文字列を,で結合する。

問題概要 フィボナッチ数を求める。

ちょっと考えたことをまとめてみました。どちらのアルゴリズムも区間を扱うものですが、例によって私の好みで半開区間を主に扱います。 二分探索とは何か 自分なりにまとめると、「ある点を境界に真偽が入れ替わるとき、その境界を効率的に求めるアルゴリズ…

問題概要 整数xを2進表記して、その文字列表現が長さ2以上の周期を持っているときxを周期的と定める。[L,R](L,R 解法 定石通り[1,X]に帰着させる。各長さごとにそれぞれ独立に考える。長さを固定すると、これは蟻本でも紹介されているメビウス関数を用いて数…

問題概要 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以上、とできるのでよい…

問題概要 最短路を求める問題。200でよいと思う。

問題概要 文字列Sが与えられる。隣接する文字を高々M回までswapできるとき、連続する同じ文字の長さの最大値を求める問題。 解法 最長なswap後の文字列を考えると、どれか一文字は動いていないと思ってよい。そうでないものも作れるが、固定した場合よりもよ…

結果。 またeasyを落とした。forループの向きが逆という自分にはよくあるミスなんだけど、どうやったら防げるんだ…。ループを見る度に向きを意識するのはちょっとコストが高すぎるし、何かもう脳みそのスタック容量不足とかそういうレベルでダメダメな気分に…

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

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

私はしゃくとり法を書くのが苦手です。なので、しゃくとり法について自分なりに考えてみました。 しゃくとり法って結局何？ 二分探索は「ある点を基準に真偽が入れ替わるとき、その基準となる点を見つけるアルゴリズム」と説明できるし、座標圧縮は「何かの…

問題概要 n( 解法 最適ルートは、右→左か左→右なので、今いる位置から右に進んだ場合と左に進んだ場合でそれぞれDPして最適解を求めておき、最後にその2つをマージするようにすればよい。うまく実装する自信がなかったので、初期位置をとる場合ととらない場…