ferinの競プロ帳

競プロについてのメモ

2018-09-26から1日間の記事一覧

JAG夏合宿2018 day3 D - Prefix Suffix Search

問題ページ 解法 単語のリストwをソートしたものを使うと二分探索で接頭辞がpの単語の集合がわかる。各単語を反転したリストw_invをソートした物を使うと二分探索で接尾辞がsの単語の集合がわかる。wとw_invをそれぞれ座標軸にとった二次元平面上にプロット…

Typical DP Contest K - ターゲット

問題ページ 解法 円なので2次元っぽいが円の中心のy座標が0なのでこれは1次元の問題である。各円は[x-r,x+r]の区間に置き換えられこの区間でK重に内包されているよな区間があればそれはレベルKのターゲットである。区間がたくさん来たので終端でソートしてみ…

JAG夏合宿2018 day2 J - AB Sort

問題ページ 解法 解説にある通りAを+1, Bを-1に置き換えて累積和を取って標高図を書いてみる。操作を終えたあとの最終的な文字列はA…AB…Bとなる。標高図のminが最終的な標高図のminになるまでとそこから標高図のmaxが最終的な標高図のmaxになるまでの2つに分…

JAG夏合宿2018 day2 F - Point Sequences

問題ページ 解法 直線の交点を求める操作はO(1)でできるので点列dを作成していき新たな交点を作成できないような状況になればそれが何回目か出力するとすればよい。ただし普通にlong double等で計算すると公式解説の通り誤差がとんでもないことになる。分数…

JAG夏合宿2018 day2 E - Self-contained

問題ページ 解法 問題の条件を満たす集合は以下の2通りである。 等差数列になっている 0, x, 2x, 3x, 4x, 5x, … 0 a b a+b の形になっている (a=bもa=b=0もありえる) 等差数列であればどのような2数を選んでもその差が集合に含まれている。等差数列は各公差d…