OUPC β

　Fが解けずの五完でした。writerさんの解説記事まとめはここ。

コンテストへのリンク
コンテスト後のツイート

Product Grid

　KがLCMになるのは分かるけど、その後の計算量削減部分は難しい。

　Kの素因数はすごく多い（かもしれない）けど、各$A_{1, i}$は小さく素因数も少ないことを利用する。コンテスト中よく思いつけたな……。

Increasing Path

　Pathの長さが短い辺から処理していくと良さそうなのはそうで、それを実現するため、（最後に通った辺の長さ, 今までの総距離, 点の番号）を持ってダイクストラしました。

　ただ、今、解説を読んで後で考えるとこの解法は怪しそう。「ある点での最短距離が何度も更新される」「その点からたくさんの辺が出ている」ようなグラフだとTLEになりそう。

　この問題だと、「通る辺の距離が真に大きくならなくてはいけない」ので、そういうグラフでも計算量はある程度抑えられる気がします（ちゃんと考えていないけど）が、広義単調増加でOKだったらこの解法は完全にダメでしたね。

ビブンケイスウ

・二字以上の項は必要ない→セグ木に乗る

　という問題。

　コンテスト後、writerさんはギャグだとツイートしていて、当時自分もそう思ったけど、「こういうのがセグ木に乗る」というところはなかなか本質的ですね。

　二字以上の項が必要ないと分かっても、セグ木に乗せる部分を自力で思いつけたかは疑問です。