しゃくとり法のいい練習問題！！ 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 整数列の連続する部分列のうち、「同じ数値が 2 箇所以上登場しない」という条件を満たす最大長を求めよ。 制約 考えたこと 今回の問題には、次のような著しい構…

想定解法とちょっと違うやり方したっぽい 問題へのリンク editorial 問題概要 個のマスが横一列に並んでいる ()。 匹のペンギンがマス にいる。 あなたは，次の操作を好きな回数行うことができる。 ペンギンを 1 匹選び、左または右へ向かって滑らせる ペン…

いかに上手に実装するか！ 問題へのリンク 問題概要 長さ の ">" と "<" のみかななる文字列 が与えられる。 長さ の非負整数列 は， すべての について次の条件をみたすとき、良い非負整数列と呼ぶ。 = "<" のとき： = ">" のとき： 良い非負整数列の要素の…

面白かった。でも茶色ってことは流石になさそう......(コンテスト中は、全部の XOR 和が 0 かどうかを判定する、という嘘解法が AC になっていたらしい) 問題へのリンク 問題概要 個の非負整数 が与えられる。これらを円環状に上手に並べることで、 「どの整…

こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…

面白かった！ 問題へのリンク 問題概要 頂点数が の木であって、各頂点 から最も遠い頂点への距離がそれぞれ であるような木が存在するかどうかを判定せよ。 制約 考えたこと 面白そう！！！！！！似た見た目の問題としては、次の問題もあった。 drken1215.h…

添字 GCD 畳み込みの練習問題！ 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…

添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…

コーナーケースがエグい 問題へのリンク editorial 問題概要 個の非負整数 が与えられる。これらの並び替え であって が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 とする。 制約 考えたこと エグい場合分けが…

原始根 + NTT 問題へのリンク 問題概要 素数 と、数列 、 が与えられる。 各整数 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 添字積 convolution はできるのかと一瞬戸惑う。しかし が素数であることに着目すると、原始根 を介…

AGC っぽくない気がするけど、好き 問題へのリンク 問題概要 とする (素数である)。 個の非負整数 が与えられる。 の値を求めよ。 制約 考えたこと 「和を で割ったあまり」ではなく、「 で割ったあまりの和」であることに注意。それでも、とりあえず以下の…

ペル方程式の練習 問題へのリンク 問題概要 数列 は次の漸化式で定義される。 この数列の母関数 を定義する。正の整数 が golden であるとは、 を満たす が有理数であることをいう。具体的には ... となっている。小さい方から 30 番目までの golden 整数の…

から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…

区間加算操作は、「差分」をとる (いもす法) と、2 点加算になる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して以下の操作を好きな順序で好きな回数だけ行うことで、数列の値がすべて 0 になるようにすることが可能かどうか、判定せよ…

本番は「どのように に分けても絶対値和は等しい」ということに気づかず、ものすごくエグい二項係数計算を頑張って綺麗な表式を得た。 問題へのリンク 問題概要 長さが の数列 が与えられる。 数列を 個ずつのペア (順序の違いは考慮する) に分ける方法は 通…

頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…

結構教育的！！ 問題へのリンク 問題概要 個の正の整数 が与えられる。 これらのうちのどの 2 つも互いに素であるとき、"pairwise coprime" そうではなく 個の最大公約数が 1 であるとき、"setwise coprime それ以外のとき、"not coprime" と出力せよ。 制約…

愚直にやると 本の辺がある問題に対して、上手にやる系の問題 問題へのリンク 問題概要 グリッドグラフがある。 広義単調増加な正整数列 があり、それぞれの長さは となっている。 頂点 と頂点 は、重みが である無向辺で結ばれている 頂点 と頂点 は、重み…

近年非常によく見る DP 高速化系問題！！ 問題へのリンク 問題概要 長さ の 3 つの数列 が与えられる。 いま、数列 をいくつかの連続する部分列に分割することを考える。 分割 に対して、スコアを、各区間についての以下の値の最小値として定める。 その区間…

こういう条件を言い換えながら数え上げる問題好き！ 問題へのリンク 問題概要 タプリスちゃんは現在、長さ 1 の数列 を持っている。 タプリスちゃんは に対して、以下のいずれかの操作を選んで行うことを 回繰り返すことにした。 の末尾に または を追加する…

本当にただ全探索するだけ！！！ でも意外とこういうのが思いつかれにくいかもしれない。 問題へのリンク 問題概要 (意訳) 長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは で与えられる。適切…

5 + 7 + 5 = 17 なの、よくできてる！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…

一目二分探索ゲーだし、実際二分探索で解けるのだけど、実はもっとすごく楽に解ける！！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。 与えられた数列において、最大…

これ、てんぷら君のおかげで随分とシンプルな問題になった！ 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。各 に対して、 xor xor xor としたときの xor xor xor の値を求めよ。 制約 解法 XOR に関する問題は各桁ごとに考えるのは常套手段では…

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った！ 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…

形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…

「要素を 1 個ずつ追加していくときに値がどう変化していくか」を観察する方向でずっと考えていて迷走してしまった... 問題へのリンク 問題概要 正の整数 と、 個の整数 が与えられる。 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 解法 個…

これ好き！！ 問題へのリンク editorial 問題概要 長さ の整数列 と、長さ の整数列 が与えられる。 すべての に対する % の値の総和を求めよ。 制約 考えたこと や の値が 以下であることがポイントに思えてくる。一般に に対して = % の総和がどう求められ…

総和が一定値になるような数列の数え上げ、最近よく見る！ 問題へのリンク 問題概要 整数 が与えられる。 すべての項が 3 以上の整数で、その総和が であるような数列の個数を 1000000007 で割ったあまりを求めよ。 制約 解法 (1)：素直に DP まずは素直な D…

mex！！！それにしても、ならし計算量解析系が来たのびっくり！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、0 以上の整数で のいずれとも等しくない値のうち最小値を求めよ。 制約 考えたこと とりあえず次のような配列を用意したく…