ねこ鍋。良問だという話を聞いたので考えてみたらごり押し解を思いついたので実装した。 (cuteのmax)-(cuteのmin)で二分探索することを考える。そうすると、O(N)個の区間でナップサックをして、取れる重さの値をオスメスともに列挙できればよいことがわかる…

本番で解けなかった問題。区間DP。解説だと「区間を木にできるかだと4乗になって、区間を森にできるかどうかを考えると3乗に落ちる」と言われていましたが、「区間を木にできるかどうか」だけで3乗にできます。まず、DP[区間][一番最後の子x]: 区間の左端を…

700を埋め始めました。昨日今日でつぶした4問を載せます。全体的に(というか全部)筋肉。 AOJ 1314 Matrix Calculator ひたすら物量構文解析。行列積の結果が正方行列にしかならないクソバグを埋め込んだのに1ケースしか落ちず苦労した。テストケースが見える…

問題概要 凸多角形の辺上を速度xで、内部を速度yで動ける点が辺上の点から内部の点に移動する時間の最小値を求めよ。(頂点数) 解法 赤い辺が多角形の辺だとすると、真ん中の経路とるのであれば両端のどちらかの経路をとったほうがいいです(距離が適当な一次…

幾何ライブラリをちょっと整備したのでやってみた。解くたびにライブラリが増えるので生産性を感じる。それっぽい点を全部列挙して適当な線分がちゃんと多角形の中にあるかを判定する。O(2^n*n^4)で前処理がO(n^6)なのでTLEはやばそうだけどちゃんとbreakす…

問題 任意の2本を通る直線がちょうどn種類であるような最小の点の個数からなる点集合を出力せよ。 解法 まずk点が一般の位置にあるときk(k-1)/2本の直線が引ける。m個の点が同一直線上にあるとm(m-1)/2-1個直線が減るのでいい感じに直線を減らして目標の数に…

問題概要: N*Mの盤面にK個障害物があって飛車を3つ置いて互いに取り合わないようにする方法を数えろ。 N.M 解法: 適当に包除を考えて自明な場合を抜くと3個の飛車がL字型に並んでるやつを数えればいいことがわかるので頑張ってsegtreeで平面走査しながら数え…

見た目怖いけど実は簡単。各うさぎの偏角ソート順が分かればあとは隣り合う2つの角度を面積が大きくなるように山を登って行くだけなので偏角ソート順を全探索する。隣接する角度の和がpiより大きい場合にちょっと面倒なので微分の零点とかせずに適当に三分探…

新年なので目標です。とざんさんを真似して点数形式です。この形式だと無理そうなことも扱えるからよい。3段階のやつは2つめをクリアできれば良しとします。 センター試験 通ればいいのでこんな感じ。 足を得る 800 840 +6 +2 +2 二次 これも通ればいいので…