ferinの競プロ帳

競プロについてのメモ

2019-12-13から1日間の記事一覧

AOJ2749 ぼくのかんがえたさいきょうのおふとん

問題ページ ぬくもり需要 をソートしておくと,おふとんを増やす操作のみに置き換えられる.したがっておふとんを積む順番は記録せずに,使ったおふとんの集合だけ記録すればよくなる. 日目使った布団の集合 最小の不快度の和としたDPを考える.このDPの遷…

aoj2397 Three-way Branch

問題ページ 障害物がなければ行列累乗をすればよい.障害物に対応するため障害物が存在する行ごとに区切って考える.行列累乗で 列目に到達する方法を求めたあと,障害物が存在する位置に到達する方法を0通りに置き換える. で解けた. #include <bits/stdc++.h> using name</bits/stdc++.h>…

AOJ2256 ケーキ分割問題

問題ページ 直線 上の点 を決めたときに, 上のどの位置に点を置けば2等分できるか? を原点として 点を偏角でソートする.このとき 番目と 番目の点の間を通るような線分を引くと,2等分することができる. と 番目の点を結ぶ線分が のときに取る 座標 から…