概要 格子点上で、n 組の始点と終点 $(a_1, a_2, \ldots, a_n), (b_1, b_2, \ldots, b_n)$ が定まっているとして、それらが交差しないようなパスの選び方をカウントできる定理である。（$a_i$ をどの $b_j$ と対応付けるか、まで含めて。） 後にこの定理を用…

はじめに 2018年12月8, 9日に横浜で行われた ACM-ICPC 2018 Asia Yokohama Regional の参加記です。 プラクティス～懇親会あたりまでの話を大雑把にまとめようと思います。 チームについて 自分はチーム Zerokan_Sunshine として kazuma, nakano と一緒に出…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2884 解法 二分探索 + 桁DP ……ではなく貪欲に解く。 基本的に上の桁から順番に数字を確定させていって、 n 番目を超えないギリギリを選択する、というよくあるやり方。 当然だが各桁は小さ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2787 解法 一番上の行のすべての家は special pipe 確定だから、(W + 1) / 2 > K なら不可能であり、それ以外は可能である。 それ以外については、一旦 special pipe を使わないとして考え…