階差数列
とても教育的で典型的なしゃくとり法の問題！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。 が等差数列であるような組 の個数を求めよ。 制約 解法 (1)：しゃくとり法 今回の問題のように、数列中で条件を満たす区間を考える問題では、しゃ…
いわゆる「愚直シミュレーション」と呼ばれる分野の問題ですね。問題文で指示されたことを、とにかく愚直に忠実に実装できるかが問われています。地味な印象を受けるかもですが、大切なスキルです！ 問題へのリンク 問題概要 黒板に、はじめ 個の整数値 が書…
実装をどうしようかを色々悩んでしまう系 ジャッジページ AOJ の問題文 問題概要 本のつららが一列に並んでいる。それぞれ長さは となっている。各つららは以下のルールに従って長さが変わる。 一度でも長さが 0 になったならば、伸びることはない 左右のつ…
これを本番間に合わせられたなかったのは辛かった... あと、数え上げパートがあんなにスマートにはできなかった。無限に から落とせなかった... 問題へのリンク 問題概要 黒石さんと白石さんは、一列に並んだ 個のマスからなる盤面を使って遊んでいます。 マ…
差分だけ更新していく系の問題！！！ 問題へのリンク editorial 類題集 (めちゃむずいのもある) drken1215.hatenablog.com 問題概要 正の整数 が与えられる。長さ の数列 のスコアが次のように定まる。 各 に対して以下の値を合算する のとき： のとき： を…
最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった！ 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…
いもす法 問題へのリンク editorial 問題概要 要素からなる数列がある。初期状態では全要素の値が 0 である。以下の 回の操作を行なって得られる数列を出力せよ。 各クエリでは整数 が与えられる。区間 に対して、初項 1、交差 1 の等差数列を加算する 制約 …
操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …
操作を 回行った結果を求める系、苦手意識あるけど克服したい！ 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…
バチャやった。13 位相当で割とよかった。 ロリハした。 問題へのリンク 問題概要 長さ の整数列 , が与えられる。以下の条件を満たす 以上 以下の整数 と、整数 の組をすべて求めよ。 = が成立する 制約 考えたこと 整数列 を circular shift した上で、 と…
