SRM 607 Div2

SRM 607 Div2

Easy BoundingBox

たくさんの点が与えられる。これらの点を内包する最小の矩形の面積を求める。

Med PalindromicSubstringsDiv2

vectorS1とS2が与えられる。これらを連結したSに含まれる回文はいくつか。

普通にO(N3)で判定していったらTLEになる。回文の両端に同じ文字をつけるとそれは回文みたいなあれでO(N2)程度に減らせる

文字列に関するアルゴリズムとかデータ構造とか 篠原研究室:東北大学

Hard CombinationLockDiv2

ダイヤル錠がある。これをSからTにする。隣接する複数の数字を同時に同じ方向に動かせる。最小で何回でTにできるか。

DPで解けるらしいです。

Codeforces #244 Div2

A Plice Recuits

警察署がある。はじめは一人も警察官がいない。N個の事象がおきる。与えられた数字が-1なら事件が起き。正整数ならその人数の新人を雇う。新人は雇われた後に起きた事件を一つだけ解決する。解決されない事件の数を答えよ。

B Prison Transfer

N人の囚人が居て、そのうちの連続するC人を別の収容所に送りたい。C人の犯した犯罪の卑劣さがすべてTを超えないように選ばなければならない。何通りの選び方があるか。

全探索するとO(N2)で間に合わないのでセグメント木を使います。O(N log N)でいいんだよね。はじめは配列サイズが足りなくてTLEが出て、配列の大きさを直したらACになったのでよくわからない

C

都市があってN個の合流点がありそれぞれに係留地を作るためのコスト、そしてM個の道が与えられる。 道は一方通行。ある係留地から進んで戻ってこれるところにパトロールに行くことができる。すべての合流点にパトロールに行くために最低限作る必要のある係留地と建設コストとその方法の数を求める

強連結成分でかっこいいことをするようです

まとめ

codeforces難しすぎやしませんかね。文字列の勉強しないと