ferinの競プロ帳

競プロについてのメモ

2018-02-20から1日間の記事一覧

SRM730 div2 easy IntervalIntersections

概要 区間[x1,y1]、[x2,y2]が与えられる。この区間どちらとも共通部分を持つような最小の区間の長さを求めろ。 考えたこと 間の区間を取るかそもそも区間が被っているかのどっちか x1 < x2 と x2 > x1 で場合分けすればいいね x1の方が右ならx1-y2かすでに区…

SRM730 div1 easy StonesOnATree

概要 各頂点iに重みw[i]が設定されているn頂点の木が与えられる。 ある頂点に1つ石を置くか、石を一つ取り除く操作を繰り返すゲームをする。ある頂点に石を置くとき、その頂点の子全てに石が置かれている必要がある。 ゲーム中に取りうる、石が置かれている…

「みんなのプロコン」本選 2017 C - 倍数クエリ

問題ページ C - 倍数クエリ 平方分割はじめてだったので練習として書いた 考えたこと mod m で考えてよさそう 平方分割なことは知ってたので考察をすると各バケツが数字が現れる頻度をもっておくとよさそう まとめてバケツに加算する配列lazを用意しておけば…

COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君

問題ページ C - スペースエクスプローラー高橋君 CHTで解いてたけどmonotone minimaで解けるらしいので解くことにした 考えたこと f(i,j) = (i番のキャノンで区画jを破壊するエネルギー) 最小値がどんどん右下に移動していくのはそれはそう monotone minima…

SPOJ BRKSTRNG - Breaking String

問題ページ SPOJ.com - Problem BRKSTRNG Mongeを使ったDP高速化の練習で解いた 考えたこと 解説を読む X(i,j) = ([i,j)のコスト) みたいな感じで持ちたい W(i,j)は[i,j)を分割するのにかかるコストだから区間の幅でよさげ DP漸化式がKnuth-Yao speedupの形…