数列
これ好き！楽しい！！ 問題へのリンク 問題概要 長さ の数列 で定義される、全 ステップの操作が与えられる。操作は整数 に対して行うものであり、 回目の操作は次のものである: を % で置き換える 個の整数 それぞれに対して ステップの操作を行って得られ…
DP の添字を mod をとった値にするテクニック 問題へのリンク 問題概要 個の正の整数 が与えられる。これらの中からいくつか選びたい。選んだ整数のスコアを以下で定める。 整数の総和を として + % スコアの最大値を求めよ。 制約 考えたこと そもそも「整…
この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…
in-place な DP にもっと慣れていきたい 問題へのリンク 問題概要 個の数列がある。 個目の数列は 個の要素からなる。 個目の数列の 番目の要素は と表す。 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を とする。 数…
中盤枠という感じで作られた 問題へのリンク 問題概要 の番号を振られた 個の頂点があります。 最初、これらを繋ぐ辺はありません。 あなたはいくつかの辺を追加してこのグラフを連結にしたいと思いました。 頂点 と を繋ぐ辺を追加するには のコストがかか…
難しかったー！！平方分割かな...とまでは思ったので、もっと粘り強く考えられるようにならないと...！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の 4 種類のクエリを 回処理してください。 クエリ 1: が与えられるので、 () を に更新する…
XOR について完全理解することが求められる...！ 問題へのリンク 問題概要 を偶数とする。 個の 0 以上の整数 であって、以下の条件を満たすものを求めよ。 個の整数のうち 番目を除外した 個の整数の XOR 和が となる 制約 考えたこと が偶数というのが不気…
差分更新を上手にやっていくという、とても教育的な問題！！！ そして、よく似た類題として、以下の問題がある！！ atcoder.jp 今回の問題へのリンク 問題概要 個の整数 が与えられる。以下の 回のクエリに答えよ。 各クエリでは 2 つの整数 が与えられる 数…
どこかでめっちゃ似たのを解いたことあると思ったらコレだった！ drken1215.hatenablog.com 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 個の整数 の空でない部分集合 は 通りあるが、そのそれぞれについて、 = の部分集合のう…
考え方自体は典型的ではある 問題へのリンク 問題概要 個の整数 が与えられる。 これらから 2 個選んで XOR をとって得られる整数 ( 個ある) の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと XOR をみたら、とにかく「各桁ごとに考える」とい…
じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…
最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^; 問題へのリンク 問題概要 個の整数 が与えられる。これらから 2 つを選んで積をとって得られる 個の整数のうち、…
実装を柔軟にしたい 問題へのリンク 問題概要 体のスライムがあって、初期状態では、それぞれの色は となっている。以下の操作を繰り返すことで全てスライムを消滅させたい。そのために必要なコストの最小値を求めよ。 色 のスライムを消滅させる (コストは …
操作の仕方が Euclid の互除法そのものになっているタイプの問題。 問題へのリンク 問題概要 要素数 の数列 が与えられる。これに対して以下の操作を好きな回数だけ行うことができる: 整数を 2 つ選び、その差の絶対値をとり、それを数列に新たに挿入する 整…
答えが 0, 1, 2 の三通りしかないとなれば、mod で絞るのをやりたくなる！ 受験数学では定番のテクニックだ！！！ 問題へのリンク 問題概要 長さ の、1, 2, 3 のみからなる数列が与えられる。この数列に対して、 隣接する要素の差を書き出す という操作を、…
面白かった。間違いやすいけど、このくらいなら！！！ 問題へのリンク 問題概要 長さ の正の整数からなる二つの数列 、 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 と が一致するようにすることは可能か？ の要素を一つ選んで する の要…
このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい！！！ 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるよう…
確かに AtCoder で完全既出だった！ drken1215.hatenablog.com 問題へのリンク 問題概要 要素の数列 が与えられる。これらから 2 つ選んで和をとって得られる 個の整数の XOR 和を求めよ。 制約 #include <bits/stdc++.h> using namespace std; const int INF = 1<<30; int </bits/stdc++.h>…
これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…
実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう！ 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…
この頃、数列を繰り返すのが流行ってたのかな 問題へのリンク 問題概要 長さ の恒等数列 () が与えられる。この数列に以下の操作を合計で 回行う。 番目の操作は、パラメータ であらわされ、以下のように行われる。 現在の数列を無限回繰り返した数列の先頭 …
面白かった 問題へのリンク 問題概要 要素の数列 が与えられる。以下の条件を満たすような部分数列のうち、要素和の最大値を求めよ。 抜き出した数列のどの 2 項についても「値の差分」と「index の差分」とが等しい 制約 考えたこと たとえば の場合は、こ…
操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …
こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…
すごい面白かった！！！ 問題へのリンク 問題概要 整数 が与えらえたときに、漸化式 を満たす数列 が与えられる。これに対して以下の 個のクエリに答えよ: 1 つのクエリは 2 以上の整数 が指定され、 を満たすような正の整数 に対して、 の総和を求め、10000…
LIS の亜種だけど、雰囲気違って面白い！ 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。この部分列であって 狭義単調増加 後の index に出てくるやつは前の index にでてくるやつの倍数になっている という条件を満たすものの最長の長さを求め…
D 問題はコーナーケースゲーかと思ったらそうでもなかった。むしろこっちの方が苦しかった。 問題へのリンク 問題概要 要素からなる配列が 個あって、それぞれ最初は で初期化されている。以下の操作を 回終えた段階で、 個の配列が等しい状態とすることが可…
こういうのをちゃんと解けるようになったのは成長！ 問題へのリンク 問題概要 (意訳) 以下の 個のクエリに答えよ。 番目のクエリでは、数列 が与えられる。この数列に以下のいずれかの操作をほどこして、 となるようにしたい。その最小回数を求めよ。 を任意…
すごく面白かった！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。ここから何個か選ぶ。選んだ値を としたとき、そのスコアを以下のように定義する。 選んだ値のメディアンを とする 奇数個の場合は真ん中の値 偶数個の場合は真ん中の 2 つの値の…
勉強になった...けど、これ知らずにできるもんなの！？ 問題へのリンク あと、LCM の最小値バージョンもある！ drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …
