数列
いわゆる「相手との得点差を最大化したい」タイプのゲーム DP ですね！ 問題へのリンク 問題概要 太郎君と次郎君が数列 を使ってゲームをします。太郎君を先手として、交互に次の操作を行います。 数列の先頭要素または末尾要素を除去する 除去した値の分だ…
いわゆる「得点差を最大化したい」というゲーム DP！！ 問題へのリンク 問題概要 個の石が積まれた山を使って石取りゲームをします。先手と後手は交互に次の操作を行います。 個のいずれかの個数の石を取り除きます ただし、 が残っている石の個数よりも小さ…
少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね！ 問題へのリンク 問題概要 個の整数 が黒板に書かれている (各整数は 100 桁までありうる)。 奇数の精と、偶数の精がいる。 奇数の精は、黒板に書かれている数字がすべて奇数となるように…
素直な実装でも解けるけど、C++ の map 型や、Python の Counter 型が使えると、すごく簡単に解けます！ 問題へのリンク 問題概要 本のパスタがあって、それぞれ長さは である。 高橋君は 日間パスタを食べる。 日目にはそれぞれ長さが であるようなパスタを…
すごく典型的ないい問題！ この手の問題は、大抵、二分探索法でもしゃくとり法でも解ける。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらの数列から 1 つずつの値を選ぶ。選んだ値の差が 以下となるようにすることが可能かどうかを判定し、…
本当に ACL の convolution をそのまま試してほしいという問題ですね。 問題へのリンク 問題概要 整数列 と、整数列 が与えられる。 によって定義される整数列 を求めよ。 制約 解法 とにかく、ACL のドキュメントにそのままの式が書いてある！ https://atco…
ちょっと面白い問題！ 競プロ始めたばかりの方々に、計算量のことを意識させるのに良い問題かもしれない。 問題へのリンク 問題概要 どの 2 つの値も互いに相異なるような、長さ の数列 が与えられる。 この数列 の異なる 2 要素の和として表せる値の中に偶…
Binary Trie + 平方分割 問題へのリンク editorials 問題概要 数列 に対して、以下の 個のクエリを処理せよ。 クエリタイプ 1 (k x)： を xor に置き換える クエリタイプ 2 (l r x)： xor の値を出力する 制約 考えたこと これは TL で解法を見た上で解いた…
FPS による考察はやっぱり強力ですね！ 問題へのリンク 問題概要 長さ かつ総和 である非負整数列 のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。 「以下の操作のうちどちらかを選んで行うことを繰り返して、 の全ての要素を 0…
AND と XOR は、それぞれ「掛け算」と「足し算」に対応するので、行列累乗が使える！ 問題へのリンク 問題概要 個の整数の組 と が与えられる。 数列 は次の漸化式で定義される。 () AND XOR AND XOR ... XOR AND () の値を求めよ。 制約 考えたこと AND は…
データの持ち方をうまく工夫することで、計算量を改善する系の問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 個のクエリが与えられるので、それらを順に処理せよ。クエリは次の 3 種類ある。 x：数列 をすべて に書き換える i x： に を足す i…
順列を数え上げる系の問題、うまく「個数」を持った天才的な DP をするイメージ 問題へのリンク 問題概要 整数列 が与えられる。 この数列の 通りの順列のうち、 であるような がちょうど 個であるようなものの個数を 998244353 で割ったあまりを求めよ。 制…
「TDPC T - フィボナッチ」の亜種とも言える問題ですね。 問題へのリンク 問題概要 () によって定義される数列を考える。 整数 が与えられので、 AND を満たすすべての非負整数 に対する の総和を 998244353 で割った余りを求めよ。 制約 考えたこと この問…
Boston--Mori 法を履修した！ 問題へのリンク 問題概要 () によって定義される数列において、 を 1000000007 で割ったあまりを求めよ。 制約 解法 0-indexed にして考えることにする。つまり、 () によって定義される数列において、 を求めることにする。 こ…
シンプルながらも、学べるポイントがたくさんある問題ですね 問題へのリンク 公式解説へのリンク 問題概要 JOI 市には から までの番号が付けられた 人の住民がいて、住民 () の年齢は 歳です。 JOI 市の住民の年齢 が与えられます。 に対して、住民 と他…
これをグラフの問題だと思えるかどうか！ 問題へのリンク 問題概要 箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は である。 箱の中に 2 個以上のボールが残っている限り、下記の行動を繰…
久しぶりに bit ベクター高速化を使った。デバッグがしんどかった。 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。今、次の操作をちょうど 回実行する と を選ぶ と とを swap する 操作実行後の の値の最大値を求めよ。 制約 考えた…
シミュレーションの仕方を工夫する問題。数値ごとに index をまとめあげるデータを持つとうまくいく。 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 の順列 であって、 を満たすものを考える。そのような順列の (ただし である場合の の場合は…
BIT の使い方の練習問題。同時に、自分で BIT を書いたときにそれを verify できる問題でもある！ 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する 個のクエリに答えよ。 ：数列中の値 に を加算する (a[p] += x) ：数列 の区間 の総和…
よくあるデータ構造問題！！ めっちゃ色んな解法がある！ 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…
数列に対して、2 進法で表して、再帰的に上位桁から 0 と 1 で分類した木を作る！！！ こどふぉではよく見るやつですね。 問題へのリンク 問題概要 個の非負整数 が与えられる。ある非負整数 を上手に選んだときの、 の値の最小値を求めよ。 制約 考えたこと…
部分和問題の応用問題！ 問題へのリンク 問題概要 個の非負整数 が与えられれる。 これらの整数から 個選んで、総和が の倍数となるようにする。その値として考えられる最大値を答えよ。 の倍数にするのが不可能な場合は -1 を答えよ。 制約 前提知識 この問…
面白かった！ ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…
とても色んな解法が考えられる問題ですね。ハッシュで殴るのが最も簡単だとは思います。そのほかにもさまざまな解法が考えられます。 問題へのリンク 問題概要 2 つのサイズ の整数列 と が与えられます。 これらの数列に対して 回のクエリが与えられます。…
ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…
EDPC C - Vacation と良く似た問題だと思う！！ あと、幅が狭いグリッドでは DP が疑われることが結構多い！ 問題へのリンク 問題概要 長さが の数列が 2 つ ( と ) 与えられます。 各 に対して、 と のいずれかを選ぶことで、新たに数列 を作ります。 こう…
文字通り、与えられた数列を座標圧縮する問題ですね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 これらの数列から重複を除外して小さい順に並び直して得られる数列を とします。 各 に対して、 となるような を出力してください。 制約 座標圧…
コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
二分探索法の教育的典型問題ですね！！ 問題へのリンク 問題概要 正の整数からなる長さ の数列が 2 つ ( と ) 与えられます。 各 に対して を計算することで得られる 個の整数を考えます。 これらの整数を小さい順に並べたとき、 番目 (1-indexed) に来る値…
包除原理の一番簡単な場合を試せる問題 問題へのリンク 問題概要 個の整数 が与えられる。以下の条件を満たす整数 の組の個数を求めよ。 制約 考えたこと まず、 という条件がないバージョンを考えてみよう。そのときは単に 個のものから 2 個選ぶ場合の数を…
