Binary Search

2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest,D: Packmen Strike Back

http://codeforces.com/problemset/problem/883/Dこれは考察系のDP。場合分けでtrivialな場合は別で処理します。非自明(Pが2つ以上ある)の時、まず二分探索して、距離Kすすめるとき*をすべて覆えるか?という問題を解くことを考えます。dp(i):=i番目のPを使っ…

AtCoder Regular Contest 078E: Awkward Response

http://arc078.contest.atcoder.jp/tasks/arc078_cまず桁数を特定する。これは1, 10, 100,...と比較するとわかる。 それからは上の位から数字を特定していく。 例えば(10^3,10^4)の区間において49990を投げると、(10^3,5*10^3)でyes,[5*10^3,10^4)でNoとなる…

POJ2010: Moo University - Financial Aid

http://poj.org/problem?id=2010蟻本でpriority_queueと二分探索のどちらでも取り上げられているように解法が2通りある。1. http://omochan.hatenablog.com/entry/2017/06/30/214614 この問題と同じように、真ん中を決めてしまえば独立に考えられるので前後…

POJ 3104: Drying他

蟻本少しずつ埋めます。http://poj.org/problem?id=3104POJ久しぶりにしたので注意点を。(POJ以外の注意点もあり) cout,cinはios::sync_with_stdio(false)にしても遅いのでprintf,scanfを使う。 c++11は使えないのでtemplateらへんでcompile errorが生えるの…