yukicoder.me 解説というよりかは、ACするまでに考えたこととそれからの高速化について考えたことのメモです。 具体的には、私の初AC時は${\rm O}(NM + M ^ {3} \log M)$ だったのですが、そこから ${\rm O} ( NM + M ^ {2} \log^{2} M ) $への高速化を行い…

yukicoder.me はじめに フック長の公式を初めて触る人が本問題の解説を自分なりに解釈しただけのものになります。表現や厳密性が怪しいところもあるかと思いますが、ご了承下さい。 問題概要 広義単調数列$A_1$、$A_2$、$\cdots$、$A_N$に対して、広義単調が…

式変形が大変だったりするのでメモ用。 2つの直線の交点 位置ベクトル$(s_1, t_1)$、$(s_2, t_2)$、方向ベクトル$(a_1, b_1)$、$(a_2, b_2)$としたときの交点座標。 方程式に直すと、 $$ y - t_1 = \frac{b_1}{a_1} (x - s_1) $$ $$ y - t_2 = \frac{b_2}{a_…

yukicoder.me 解法 燃やす埋める問題と呼ばれるものです。最大流(最小カット)を使います。 ・$x$番目の国に行かない ・$x$番目の国に行くけど、ツアーに行かない ・$x$番目の国に行き、ツアーにも行く という3択があります。まず、 M 個の条件がない場合は、…

yukicoder.me 解法の概要 中国余剰定理を用いた多倍長整数を必要としない解法です。 解法 密室の幅を$W$、奥行きを$H$、時間を$D$秒間止め、まみの座標を$ (M_x, M_y) $、ほむらの座標を$(H_x, H_y)$ 、弾丸の一秒間に進む速度を$ (V_x,V_y) $とします。 ま…