maspypy
maspypy
問題名: Incremental Convex Hull # 問題概要 はじめ $S$ は空集合である。 $Q$ 回次を行え。 - `0 x y`： $S$ に点 $(x,y)$ を追加する - `1 x y`： $(x,y)$ が $conv(S)$ の内部に含まれるか、境界上であるか、外部にあるかを答える - `2`：現在の凸包の面積の 2...
大きな $n$ だと RE が出る種類の愚直解（配列大きすぎなど）の solutions は、なにか想定されている指定方法はありますか。 1. wrong = true を入れて目視チェック 2. wrong = false, allow_tle = true を入れて、$n$ が大きいときはわざと無限ループさせる等 1 だと目視なのが筋が悪い感じがする。 wrong = true という字面が誤解を招きやすい。 2 だと待機時間が長くなる。 という気がします。何度か準備していて複数回感じた疑問なので、わりと典型的な状況だと思います。
問題名：min_of_mod_of_linear ## 問題 （案1） $f(x) = ax+b \bmod m$ とする. $L\leq x < R$ における $f$ の最小値を出力せよ。 （案2） $f(L), \ldots, f(x-1) > f(x)$ を満たす $x$ 全体は $O(\log m)$ 個の等差数列の和集合である。この等差数列を適当な形で出力させる。 ##...
## 問題 素数 $p$ が与えられる。$Q$ 回次を解け：$s(n,k) \bmod p$ を求めよ。 ## 制約 - $p\leq 5000$、素数 - $0\leq k\leq n\leq 10^{18}$ ## 資料 解説を書きました。https://maspypy.com/stirling-%e6%95%b0%e3%82%92-p-%e3%81%a7%e5%89%b2%e3%81%a3%e3%81%9f%e4%bd%99%e3%82%8a%e3%81%ae%e8%a8%88%e7%ae%97 第 1, 2 種ともに、$O(p^2)$ 前計算のもと、クエリごとに $O(\log_pn)$ 時間でできる。 ##...
問題ID: multivariate_cyclic_convolution 問題名: Multivariate Cyclic Convolution # 問題概要 k変数の多項式 f(x_1, x_2, ..., x_k), g(x_1, x_2, ..., x_k) が与えられる。これを掛けて mod (x_1^{n_1}-1, x_2^{n_2}-1, ..., x_k^{n_k}-1) を取ったものを求めてください。 # 想定アルゴリズム 1 の 2^n 乗根と...
問題名: Convolution on the multiplicative monoid of Z/NZ # 問題概要 整数列 a_0, a_1, ..., a_{N-1}, b_0, ..., b_{N-1} が与えられる。c_0, ..., c_{N-1} を求めよ。 c_k = \sum_{ij=k mod N}a_ib_j # 入力 N\leq...
https://github.com/yosupo06/library-checker-problems/issues/851 をつくりました。
https://judge.yosupo.jp/problem/cycle_detection の無向グラフ版。多重辺あり、ループなし。
https://judge.yosupo.jp/help https://judge.yosupo.jp/submissions/?problem=common_interval_decomposition_tree&user=&status=&lang=&order=%2Btime&page=0&pagesize=100
## 問題概要 (N, M) 無向単純グラフ $G$ と、始点 $s$, 終点 $t$ が与えられる。 順列 $p = (p_v)_v$ であって以下を満たすものの存在判定・構築。 - 各辺を、 $p_u < p_v$ のときに $u$ から $v$ を向き付けたとする。このとき、任意の頂点 $v$ に対して、 $v$ を通る...