解いた問題 (1/23 ~ 1/30)

Problem - E - Codeforces
とりあえず番兵として -linf と +linf を $a$ 、 $b$ の両端に $0$ と $n+1$ を追加。
$b_i$ と $b_{i+1}$ の間で LIS を見るだけになるが、隣り合った要素が $1$ 以上の差を持っていなければならない。
全要素から自分の index を引くと自然と達成できる。
$a_{b_i}$ より小さくなったものは、どうせ絶対に動かさなければならないので、 $a_{b_i}-j$ とでもしておけば OK。

Calendar Ambiguity
数学という感じの問題。解説 AC。
問題を要約すると 1/1 から何日経過したか？の mod $w$ が月と日にちを入れ替えても等しくなる $X$ 月 $Y$ 日の組合せの数を求めるということ。
$X$ 月 $Y$ 日は 1/1 から $Xd+Y$ 日経過している、 $X$ と $Y$ が入れ替わっても $w$ での剰余は等しくなるため、
$Xd+Y \equiv Yd+X\ (mod\ w)$
より
$(X-Y)(d-1)\equiv 0\ (mod\ w)$
となる。
$d-1$ は常にかかってくるため、 $X-Y$ が $w/gcd(w,d-1)$ の倍数となれば良い。そのような $X, Y$ の組合せを $X,Y\leq \min(m,d)$ の範囲で計算すると正答が得られる（ $X,Y$ は入れ替わるので、両方が $m, d$ の制約内に収まるようにしなければならないため）。