毎日格上の問題を倒す*1やつの96日目です。
暫くこれです。ちゃんとAtCの格上も解いてはいますが。
コンテストリンク
https://kenkoooo.com/atcoder/#/contest/show/d7702885-8ae7-43b8-b7c9-16ea14a53752
結果
道路の建設案(難易度10)…65/100(ooooo-)
鉱物(難易度12)…40/100(ooo------)
最古の遺跡 3(難易度12)...0/100(---)
合計...105/300*2
解法
E - 道路の建設案 (Road Construction)
45度回して、求めるものをチェビシェフ距離にします。
すると、各点の距離の下界はX座標の差になります。これを利用します。
暫定トップを持っておいて、距離の下界が小さいペアから順に暫定トップを更新していきます。これは優先度付きキューを使用すればよいです。
わざわざ下界を設定したのは、これを考えておくとよさげなところで枝刈りができるからです。
ただ、この方針だと最後の小課題は何しても通りませんでした。
L - 鉱物 (Minerals)
小課題1
全探索です。
小課題2
すごく意味深です。
これは、前半と後半に分けて例えば並列二分探索を利用すれば解けます。
小課題3
ペアがないなら自分で作ればよいです。これはそんなに難しくありません。
ただし、この後はこの方針だと厳しそうです。
F - 最古の遺跡 3 (Ruins 3)
なにこれ、全探索もできません…
提出コード
道路の建設案
鉱物
感想
10-12-12は本番だと相当な虐殺回では？
