解空間:O(N^2)個のペア
この問題を思い出した！ 問題へのリンク 問題概要 素数 と、 個の 1 以上 以下の整数 が与えられる。 を満たす整数 が存在するような の組の個数を数え上げよ。 制約 考えたこと 一瞬、原始根を考えたくなったが、原始根ではなく「位数」を考えた方が計算量…
2 つの文字列の最長の共通部分文字列 (部分列ではなく) を求める問題！ これ、蟻本の例題にもあるけど、POJ ではなく Yosupo Judge で解けるようになったのは大きい！ なお、Suffix Automation があれば本当に貼るだけみたい。 問題へのリンク 問題概要 2 つ…
次の問題にとても似ていた！ drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…
問題を典型パーツに分解して考察を積み上げていく系の、とても教育的な問題！ 問題へのリンク 問題概要 個の文字列 と文字列 が与えられる。以下の条件を満たす の組の個数を求めよ。 と をこの順に連結してできる文字列から、いくつかの文字を選び、順序を…
「二分探索 lower_bound()」「累積和」を活用する、とてもとても典型的かつ教育的な問題ですね。 問題へのリンク 問題概要 サイズ の数列 と、サイズ の数列 が与えられる。 これらの数列から 1 個ずつ選んでできる 通りの各ペア についての、 の総和を求め…
包除原理の一番簡単な場合を試せる問題 問題へのリンク 問題概要 個の整数 が与えられる。以下の条件を満たす整数 の組の個数を求めよ。 制約 考えたこと まず、 という条件がないバージョンを考えてみよう。そのときは単に 個のものから 2 個選ぶ場合の数を…
いろんな方法が考えられそう！ 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…
添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…
AGC っぽくない気がするけど、好き 問題へのリンク 問題概要 とする (素数である)。 個の非負整数 が与えられる。 の値を求めよ。 制約 考えたこと 「和を で割ったあまり」ではなく、「 で割ったあまりの和」であることに注意。それでも、とりあえず以下の…
これ！！！！！HUPC 2019 day2 セットで出したやつや！！！ 問題へのリンク 問題概要 二次元平面上に 個の点 がある。 これらのうちの 2 点のマンハッタン距離として考えられる最大値を求めよ。 制約 考えたこと 2 点の位置関係としては、以下の 2 パターン…
XOR について a ^ a = 0 な性質を上手く使う問題として。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。 整数 が与えられ、ツリー上のパスであってパス上の重みの XOR 和が となるものが何個あるかを数えよ。 制約 考えたこと 根を 1 つ決め…
素直な問題だったけど、重たかった 問題へのリンク 問題概要 のグリッドが与えられる。各マスには白黒で塗られている。 黒マスの 3 つ組であって、それがマンハッタン距離の意味で正三角形になっているようなものが何個あるか数え上げよ。 制約 考えたこと …
高速ゼータ変換の練習第二弾！ 問題へのリンク 問題概要 長さ の整数列 があります。 を満たすすべての整数 について、以下の問題を解け: を < , を満たす整数とするとき、 の最大値を求めよ。 制約 考えたこと 個の要素を一斉に変換する何かをさせている感…
