けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

YosupoLibraryChecker

Yosupo Library Checker - Longest Common Substring

2 つの文字列の最長の共通部分文字列 (部分列ではなく) を求める問題! これ、蟻本の例題にもあるけど、POJ ではなく Yosupo Judge で解けるようになったのは大きい! なお、Suffix Automation があれば本当に貼るだけみたい。 問題へのリンク 問題概要 2 つ…

Yosupo Library Checker - Range Affine Range Sum

これ実は ACL Practice Contest の K 問題と同じらしい atcoder.jp 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ():数…

Yosupo Library Checker - Sum of Floor of Linear

floor sum の verify! 問題へのリンク 問題概要 正の整数 が与えられる。 の値を求めよ ( ケース与えられる)。 制約 解法 ACL practice C 問題の解法、および、ACL の実装を参考にして実装した。 atcoder.jp コード #include <bits/stdc++.h> using namespace std; // sum_</bits/stdc++.h>…

Yosupo Library Checker - Point Add Rectangle Sum

一点加算を含む、長方形領域内部の総和取得クエリに答えていく!動的二次元 BIT や、BIT on Wavelet Matrix などで通せる。 問題へのリンク 問題概要 二次元平面上に 点ある。 番目の点の座標は であり、重みは である。次の 個のクエリに答えよ。 クエリタ…

Yosupo Library Checker - Rectangle Sum

色んな解法があると思う。動的二次元 BIT や Wavelet Matrix など。ここでは、BIT on Wavelet Matrix (加算クエリはないのでやや過剰) で通してみた。 問題へのリンク 問題概要 二次元平面上に 点ある。 番目の点の座標は であり、重みは である。次の 個の…

Yosupo Library Checker - Static Range Frequency

Wavelet Matrix の機能の verify 第二弾!!! 問題へのリンク 問題概要 サイズ の数列 が与えられる。次の 個のクエリに答えよ。 区間 において値 が出現する回数を答えよ。 制約 考えたこと これも Wavelet Matrix の典型機能である。rank() という関数が…

Yosupo Library Checker - Range Kth Smallest

数列の区間について、 番目に小さい値を求めていく。Wavelet Matrix で処理できる典型クエリ! 問題へのリンク 問題概要 サイズ の数列 が与えられる。次の 個のクエリに答えよ。 区間 において 番目 (0-indexed) に小さい数を答えよ 制約 考えたこと Wavele…

Cartesian Tree の実装 〜 stack を用いた O(N) 時間構築

Cartesian Tree を実装しよう! 具体的には、Yosupo Library Checker の問題「Cartesian Tree」を通すことにする。 問題概要 長さ の数列 (互いに異なる) から誘導される Cartesian Tree を求めて出力せよ。 具体的には Cartesian Tree の各頂点について、そ…

Yosupo Library Checker - A + B

Yosupo Judge で最初に解くであろう問題 問題へのリンク 問題概要 2 つの整数 が与えられるので、 を出力してください。 制約 考えたこと 10Q 相当の問題。標準入力ができる人なら解けるはず。 コード #include <iostream> #include <vector> using namespace std; int main() </vector></iostream>…

Yosupo Library Checker - Polynomial Taylor Shift

面白かった! 問題へのリンク 問題概要 整数係数の多項式 と、整数定数 が与えられる。 を展開したときの各係数を 998244353 で割った余りを求めよ。 制約 考えたこと Polynomial Taylor Shift については、次の記事に詳しく書いた。計算量は となる。 drken…

Yosupo Library Checker - Sort Points by Argument

偏角ソートの verify 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。各点の座標は である。これらの点を偏角 ( とする) が小さい順にソートせよ。 ただし、点 の偏角は であるとする。また、偏角が等しい点の順序は問わない。 制約 考えたこ…

Yosupo Library Checker - Shortest Path

Library Checker というと難しいイメージがあるけど、この問題のように基本的な問題もある。でも、「最短路の復元」を要求する問題は意外と少ないので、とても貴重な問題! 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き有向グラフが与えられる。…

Yosupo Library Checker - Partition Function

ここでは の計算量の解法を実装した。本当は FPS を使えば の計算量でできる。 問題へのリンク 問題概要 非負整数値 が与えられる。 の分割数を 998244353 で割った余りを求めよ。 制約 考えたこと ここでは、この記事に書いた の計算量の解法を実装した。 q…

Yosupo Library Checker - Strongly Connected Components

強連結成分分解の verify 問題へのリンク 問題概要 単純とは限らない、頂点数 、辺数 の有向グラフが与えられる。 このグラフを強連結成分分解して、トポロジカルソート順に出力せよ。 制約 解法 まず、強連結成分分解自体の意味は次の記事に書いた。 drken1…

Yosupo Library Checker - Binomial Coefficient (Prime Mod)

「二項係数 mod 素数」を verify する問題 問題へのリンク 問題概要 素数 が与えられる。整数 の組が 組与えられるので、それぞれについて を で割ったあまりを求めよ。 制約 解法 ここで書いた方法を実装することで AC できる。ただし、modint は自前のもの…

Yosupo Library Checker - Number of Substrings

Suffix Array を用いる練習問題! ACL practice contest にもある。 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 考えたこと 実は、AtCoder Library Practice Contest に全く同じ問題がある! drk…

Yosupo Library Checker - Primality Test

Miller-Rabin 法や、モンゴメリ乗算を試せる問題ですね! 問題へのリンク 問題概要 クエリが 個与えられる。 各クエリでは正整数 が与えられるので、素数かどうか判定せよ。 制約 解法 Miller-Rabin 法が使える。次のようなアルゴリズムである。 のとき:素…

Yosupo Library Checker - Cycle Detection (Undirected)

これも Yosupo Judge の問題名でタイトル検索しても出てくるように。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。 番目の辺は頂点 を結ぶ。単純グラフとは限らない。 与えられたグラフにサイクルが含まれるならば、辺素かつ頂点素なサイクル…

Yosupo Library Checker - Cycle Detection (Directed)

Yosupo Judge の問題名でタイトル検索しても出てくるように。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。 番目の辺は頂点 を結ぶ。単純グラフとは限らないが、自己ループはない。 与えられたグラフにサイクルが含まれるならば、辺素なサイ…