maspypy

[問題案] Static Convex Hull (2 dimensional)

12

https://github.com/yosupo06/library-checker-problems/issues/808 の弱い版 # 問題概要 N 個の点を入力として与える。 凸包の頂点列を反時計回りに出力せよ。 # 検討 - 辺上の端点以外の点を含めて？外して？出力 ---- 点を含んでいるかとか、面積はとか、そういうのは必要なら、多角形に対する何かを問う問題を別に作ればよいと思う。

[問題案] wildcard pattern matching

3

Problem name: wildcard pattern matching ## Problem 文字列 $S, T$ がある。英小文字 / '?' 各 $i\leq |S|-|T|$ に対して、$S[i:i+|T|]$ が $T$ にマッチするかを判定し、結果を 01 列で出力せよ。 S = `?a?aa` T = `ba?` ANS =...

問題案 Incremental SCC

1

$N,Q$ が与えられる。 $N$ 頂点のグラフに $Q$ 回イベントが起こる。イベントは有向辺の追加である． $Q$ 行出力：イベントのたびに scc のデータを https://judge.yosupo.jp/problem/range_parallel_unionfind 形式で出力せよ

準備当時、Frobenius Form を経由する手法は想定されていなかった。 https://codeforces.com/blog/entry/124815 特性多項式が $p_1(x)p_2(x)\cdots$, $p_k\mid p_{k+1}$ となる非自明な行列を一応入れておきたい。 生成：N の分割を適当にとって deg p_i を決める → p_1 から順に p_k を決める → Frobenius Form を作る → ランダム行列 $P$ をとって $P^{-1}AP$ を出力

問題案：2変数 FPS operations

2

- Inv of 2-variable Formal Power Series - Exp of 2-variable Formal Power Series - Log of 2-variable Formal Power Series - Pow of 2-variable Formal Power Series - Sqrt...

202407 までに追加された問題を分類 manhattan mst が Graph に居たんですが，新問の euclidean mst と並べて Geometry に移動しました

[問題案] partially retroactive priority queue

3

# 雰囲気問題文 priority queue に対する操作の列 (op0, op1, ..., op{N-1}) を考える はじめ、op[i] は「何もしない」である Q クエリを処理し、処理するたびに、空な prique に対して (op0, op1, ..., op{N-1}) を行った最終結果の情報を出力せよ。 1 t x: op[t] を (push x) に変更 2...

https://github.com/yosupo06/library-checker-problems/issues/828 つくりました

木の形には star っぽいものが入っていると思われるが，クエリは一様ランダム生成されている． 次数の大きな頂点をたくさん選ぶテストケースなどがあるべき（次数の比率でランダムに選ぶとか） ---- 背景 点更新の際に周りの辺について更新を走らせる嘘解法が考えられる（解くときに一瞬考えた，すぐ棄却したが）． これは star を考えると全然ダメなのだが，クエリが一様ランダムに作られていると通ってしまうはず．