問題概要 頂点数n( 解法 どれを潰すか全探索して毎回強連結成分分解して間に合う。

問題概要 長さN( 解法 半分全列挙でよい。

問題概要 N個の重み付き区間[a[i],b[i]), w[i]が与えられる。a = {0,1,2,...,n-1}である。[1,n)を全て被覆するのに必要な最小コストを求める問題。n 解法 dp[i] = {i個目の区間を使う場合、それ以降を全て被覆するのに必要な最小コスト}とすると、dp[i] = w[…

結果。 uwiさんとチームで参加。全完で1位という素晴らしい結果だった。自分が書いたのはG,I,J,K。デバッグの調子が良かったのでWAは1個に抑えることができた。

問題概要 文字列Sに部分文字列Tがいくつ含まれるか数える問題。KMPやZ-algorithmの検証用。

問題概要 平面上の4点A,B,C,Dが与えられる。AとCから同時に出発し、BとDに同時に到着する。途中での最短距離を求める問題。 解法 三分探索のライブラリ検証用。距離時刻に対して凸でunimordalなので適用可能。多分手で解析的に解くことも出きるはず。

問題概要 4,7からなる文字列S(|S| 解法 置換はとりあえず無視して、各iに対してF(S[0:i])を求めておく。また、F(S[i:$])も求めておく。これにより4と7の切り替わる位置を全探索することができる。位置iで切ったときの最大値はF(S[0:i])+F(S[i:$])になるから…

問題概要 無向重み付きグラフが与えられるのである点からある点までの最短路のパスの総数を求める問題。 解法 サイズが小さいのと重みが非負なのでDijkstraするまでもなく(位置、距離)を組にしたDPでやるのが簡単。

問題概要 P( 解法 貪欲に選べばよい。

問題概要 2次元平面上にN( 解法 どの3点も同一直線上にないので、N=4以外のときは自由に選べる。N=4のときは単純に全探索すれば良い。多分純粋に全探索でも間に合うけどN=4のときの計算しやすさとTLE対策に一応凸法とってからやってみたら余裕だった。

問題概要 配列に、各要素にある値を加えて置換or各要素にある値をxorする作業をr( 解法 全探索する。ただしxorを2回繰り返すのは元に戻るだけなので探索しないようにする。こうすると計算量はF_30 * 長さくらいになって間に合う。

問題概要 サイコロを振ったら出た目の数だけ飴がもらえる。飴をC( 考えたこと DP臭。 まだよく分かっていない。

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

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

問題概要 f(X)=A~X~B~X~Cとなる関数Xがある。A,B,C,Xは空でない文字列である。f(X)=S(|S| 解法 どこで分離するかで全探索する。もちろんXの箇所は長さが同じになるように考えるのだけど、定数小さいからO(N^5)ですむし、if文一個付け加えるだけでO(N^4)に落…

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

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

問題概要 多項式がふたつあたえられるので、f(x)/g(x)でxを無限に飛ばしたときの収束先を求める。 解法 最高位の係数だけを見れば良い。

問題概要(適当) 長方形の中に円を敷き詰めるゲームでどちらが先に置けなくなるか求める。 解法 1個も置けないときだけ先手負けでそれ以外は先手勝ち。

蟻本を参考にして解いた。ところで蟻本は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を処理して…

問題概要 N( 解法 ある島を基準にして、右(or 左)に行って何回橋を渡れるか、を戻ってこれる場合と戻ってくる必要がない場合に分けてそれぞれdpで計算すればよい。

問題概要 H*W(H,W 解法 よく理解できていない…。各マスについて、自マスを含む同じ行、列についてxorをとったものを反転したものが答えになっている。パリティ符号みたいなもの？

問題概要 N(3*Rが成り立っている。dist(i,j) 解法 異なる連結成分の点は距離が離れているので、ランダムに回転してx座標でソートした後適当に近いところだけを調べていけばよい。 R置きのグリッドを引いて最も近くにある格子点を考えるのが綺麗な解法。

問題概要 1日1円ずつ貯金する。貯金額がw[i]円を越えたら以後x日間さらに1 or その日からの経過日数 or 経過日数の2乗だけさらに貯金する。目標額w[i]を達成するのが何日になるかとy[i] (y[i] 解法 一日ずつシミュレーションする。区間への定数、1次式、2次…

問題概要 N( 解法 とりあえず目標点が低いので強さに関して極大な手の中からランダムに選ぶ解答で通った。