こんにちは、ふるやん（@furuya1223）です。
本日、大阪大学プログラミングコンテスト（OUPC）2020 が開催されましたね。
記事執筆時点は開催前日なので、無事に開催できたことを祈っています。
さて、このたび私は Writer を務め、D, F, I 問題を作成しました。
私が作成した問題について、解説を書いていきたいと思います。
D. 仲良しスライム
結論から言うと、小さい方から $\frac{nB}{A+B}$ 番目（0-origin, 切り捨て）の強さに揃えることが最適となります。$n$ は対象のスライムの数。
ウェーブレット行列、優先度付きキュー2本、セグメントツリー上で二分探索などでこれが高速に達成できるので解けます。
以下、証明。
$i$ 番目のスライムの強さを $x$ に変更するために必要なコストを $C_i(x)$ とします。 このとき、 $C_i(x)$ は以下のように表されます。
$$C_i(x)=\cases{-B(x-X_i)\ (s \le X_i)\\ A(x-X_i)\ (s > X_i)}$$
この関数は下に凸な関数となります（ $y=C_i(x)$ のグラフがV字の形になります）。
$n$ 番目までのスライム全体の強さを $x$ に揃えるときに必要なコスト $C(x)$ は、関数 $C_i(x)$ を用いて以下のように表されます。
$$C(x)=\sum_{i=1}^n C_i(x)$$
それぞれの $C_i(x)$ が下に凸な関数であるため、その和である関数 $C(x)$ も下に凸な関数となります。 また、$y=C(x)$ のグラフの傾きは $-nB$ から $nA$ へ（負から正へ）変化します。
したがって、最小値を与える $x$ の値は、傾きが $0$ 以下から正に転じる値となります。この値を求めます。
※ 傾きが負から $0$ 以上に転じる値としても解けます
以下、$X_i$ はソート済みとします。
$y=C(x)$ のグラフの $X_i<x<X_{i+1}$ の区間の傾きは、$Ai-B(n-i)$ と表されます。したがって、これが正となる最小の $i$ は
$$Ai-B(n-i)>0$$
より
$$i>\frac{nB}{A+B}$$
を満たす最小の正整数となります。
その値は、$\frac{nB}{A+B}$ の小数部分を切り捨てて整数とした値に 1 を加えた値となります。
したがって、小さい方から $\frac{nB}{A+B}$ 番目（0-origin, 切り捨て）の強さに揃えることが最適となります。
F. Alternating Path
(頂点番号, 直前の辺の長さ, 次に増加すべきか) のタプルを頂点とした拡張グラフ上でダイクストラ法による最短経路探索を行うことを考えます。
この拡張グラフの頂点は元のグラフの辺ごとに $2$ 個作られるため、$2M$ 個となります。
では、この拡張グラフの辺数について考えてみましょう。
元のグラフの頂点 $i$ の入次数 $a$, 出次数を $b$ とします。
このとき、拡張グラフにおける、頂点番号が $i$ である頂点は $2a$ 個になります。
その $2a$ 個の頂点それぞれから $b$ 本の辺が生えるため、頂点番号が $i$ の辺から出る辺の数は合計で $2ab$ 本となります。ただし実際には連続で増加あるいは減少するような遷移は無効であるため、半分が削減できて $ab$ 本になります。
したがって、拡張グラフにおける辺の数は $O(M^2)$ となり、拡張グラフを陽に持つことはできません。
また、グラフを陽に持たない場合でも、ダイクストラ法をそのまま用いると時間計算量が $O(M^2\log N)$ となり TLE になってしまいます。
そこで、ダイクストラ法の中で無駄なチェックを削減する枝刈りを考えましょう。
ダイクストラ法の途中で、ある辺が増加に使用されたとします。このときの、遷移後の累計距離を $d_1$ とします。
ダイクストラ法の途中で、同じ辺が再び増加で使用されたとします。このときの、遷移後の累計距離を $d_2$ とします。
この2回の遷移の行き先は（直前の長さ、次に増加すべきかも含めて）同じ頂点になります。
ダイクストラ法のアルゴリズムから、$d_1 < d_2$ であることが分かるため、実際にはこのように同じ辺が増加で複数回使用されることはありません。
減少も同様です。
したがって、ある辺が増加（もしくは減少）で使われた場合、それ以降の増加（あるいは減少）ではその辺は無視して良いことになります。
同様の考察で、ある辺がチェックされたものの遷移に使用されなかったという場合にも、その辺は今後無視して良いということが言えます（2回目のチェックで使用されるのなら1回目のチェックで使用されるはず）。
したがって、増加用と減少用に元のグラフを持ち、増加・減少で辺がチェックされるたびに対応するグラフから辺を削除していくことで、無駄な探索を削減することができて高速に答えが得られます。
この枝刈りによって、合計 $2M$ 本の辺が高々1回チェックされるため、計算量が $O(M\log N)$ となり間に合います。
I. カフェオレ
カフェオレを（牛乳の量, コーヒーの量）として二次元座標上の点、あるいはベクトルとして表現します。
また、与えられたカフェオレを好きな量だけ混ぜて作れるカフェオレ（それぞれの量が整数とは限らない）を二次元座標上の領域として表現します。整数の条件は最後まで考慮しません。
$i$ 番目までのカフェオレを用いて作れるカフェオレの領域について考えると、まず $i=0$ のときは使用できるカフェオレが無いので $(0, 0)$ のみが作れるカフェオレの領域となります。
続いて、$i=1$ の場合は、$(0, 0)$ と $(m_1, c_1)$ を結ぶ線分上の領域が作れるカフェオレの領域となります。
さらに、$i=2$ の場合は、この線分をベクトル $(m_2, c_2)$ で並行移動させたときに線分が通る領域となります。すなわち、2本のベクトル $(m_1, c_1)$, $(m_2, c_2)$ で張られる平行四辺形の領域が作れるカフェオレの領域となります。
続いて、$i=3$ の場合、この平行四辺形を $(m_3, c_3)$ に沿って平行移動させたときに、平行四辺形が通る領域が、$3$ 番目までのカフェオレを混ぜて作れるカフェオレの領域となります。なぜなら、$i=2$ までで作れるカフェオレに対して、それに $(m_3, c_3)$ の $0$ から $1$ 倍を足して作れるカフェオレは、$3$ 番目までのカフェオレで作れるからです。
以降同様に、$i$ 番目のカフェオレを追加すると、$i-1$ 番目までで作れるカフェオレの領域を表す凸多角形を元の位置からベクトル $(m_i, c_i)$ に沿って動かしたときに通過する領域（凸多角形）が新たな領域となります。
この凸多角形は、$(0, 0)$ を始点として、与えられたカフェオレを偏角の小さい順に足していったときに描く軌跡を周とする点対称な凸多角形になります。
この凸多角形を構成する頂点は、偏角の小さい順に足すことで得られます。
これにより、凸多角形が与えられたときに、その内部及び周に存在する格子点の個数を数える問題に帰着されました。
ピックの定理により、多角形の内部にある格子点の個数を $i$、辺上にある格子点の個数を $b$ とするとこの種の多角形の面積 $S$ は以下の式で求められます。
$S=i+\frac{b}{2}-1$
面積 $S$ と周上の格子点の数 $b$ を計算できれば、上の式から内部の点の数が分かります。
面積は、それぞれの辺と原点から構成される三角形の面積を合計して得られます。
格子点の数は、それぞれの辺上（端点を除く）に存在する格子点の数と頂点数を合計すれば得られます。
以上より、この問題が解けました。
また、ピックの定理を用いない解法として、floor_sumを用いて格子点の数を数える解法が存在します。
これは、ある線分と、その両端点を通り $y$ 軸に平行な直線2本と $x$ 軸によって囲まれる台形に存在する格子点の数を高速に数える手法を用いるものです。