ABC467 参加記

2026/07/18

私です。

ABC467 に参加しました。4完です。岩井星人に勝ちました。おそらく2回目です。

E, F どっちも私が解ける難易度を優に超えているので、これはなかなかいい結果に見えます。嬉しいです。

単位がよくわからなくて、とてもちゃんとしていない問題です。

$W / (\frac{H}{100})^2$ が答えです。

$S_i =$ keep のときの $B_i - A_i$ の総和が答えです。

めっちゃ DP 臭がしますが、違います。

$A[i]$ が決まると $A[i+1]$ も決まるので、

の2つのケースそれぞれでシミュレーションを行い、それらの min が答えです。

いきなりの幾何です。心臓に悪いのでやめてほしい。

大事なのは、

です。

まず、P == R && Q == S なら同じ円を使えばいいので Yes です。

あとは、 $PQ$ の垂直二等分線と $RS$ の垂直二等分線が交わるかを考えます。

交わるなら、そこを共通の中心にすればいいです。

ただ、垂直二等分線をちゃんと求めるのはめんどくさいので、まず $PQ$ と $RS$ が平行かを見ます。

$PQ$ と $RS$ が平行じゃないなら、垂直二等分線同士も平行じゃないので必ず交わります。なので Yes です。

じゃあ $PQ$ と $RS$ が平行なら No かというと、そうでもなくて、垂直二等分線が一致する場合があります。

それは $PQ$ と $RS$ の中点を結んだベクトルと $PQ$ が垂直かを見れば判定できます。

垂直なら垂直二等分線が一致するので Yes、そうでないなら No です。

以上です。

最後に

E問題はModInt上で二分探索できたら解けたかも。

F問題は各クエリで解く問題自体は区間スケジューリングに見えるんだけど、違うんですかね。

ここ最近の上がり幅が異常ですが、精進が全く間に合っていないので不安です。怖い。

では、また。