総和を求める
「主客転倒・寄与分解」の典型問題！ 問題へのリンク 問題概要 1 から 9 までの数字からなる 桁の整数値 が与えられる。 この整数値の連続する区間を取り出してできる整数値の総和を求めよ。（998244353 で割らない。） 制約 考えたこと この手の問題では、 …
これ面白かった！ 問題へのリンク 問題概要 数列 が与えられる。この数列の連続する部分数列について「その総和を で割った余り」を考える。 連続する部分数列をすべて考えたときの、「その総和を で割った余り」の総和を求めよ。 制約 考えたこと この問題…
愚直シミュレーションをする問題。ただ、ある程度は計算量を知らないとドツボにハマる可能性がある。 問題へのリンク 問題概要 あるシャワーは、スイッチを押すとその後 秒間お湯が出る (延長するわけではない)。 時刻 (単調増加) にスイッチを押したとする…
「x 軸と y 軸を独立に考えられる」と「主客転倒・寄与分解」の合わせ技！！ 問題へのリンク 問題概要 座標平面上に、 本の直線 と、 本の直線 がある。 これらの直線のうち 4 本を選んでできる長方形領域は 個あるが、それらの面積の総和を 1000000007 で割…
for 文の練習！ 問題へのリンク 問題概要 個の整数 のうち、最大値と最小値を除外した 個の整数の総和を求めよ。 制約 個の整数はすべて互いに相異なる 解法 まず 個の整数を「配列」として受け取りましょう (C++ では vector<int> 型など)。 その後、配列に対し</int>…
for 文の練習問題！ 問題へのリンク 問題概要 HP が であるモンスターを倒したい。 種類の必殺技を順に使っていく。 種類目の必殺技はモンスターの HP を だけ減らすことができる。 モンスターの HP を 0 以下にすることができるかどうかを判定せよ。 考えた…
set を使おう！ 問題へのリンク 問題概要 長さ の整数列 と、正の整数 が与えられる。 以上 以下の整数のうち、数列 に一度も含まれないものについての総和を求めよ。 制約 考えたこと まず、 となる。 この値から「1 以上 以下の整数のうち、数列 に一度以…
配列の中に配列型式の添字を入れるような処理（A[B[i]] のような）を書けるようになろう！ 問題へのリンク 問題概要 あるコンテストでは 問が出題され、配点はそれぞれ 点であった。 参加者のすぬけ君は、このうちの 問 問を解いた。 すぬけ君の得点はいくら…
配列の要素を for 文で順に調べていけば良い系！ 問題へのリンク 問題概要 本の木にそれぞれ 個の実がなっている。それぞれの木から実を収穫する。ただし、 実っている木の実が 10 個以下の木からは木の実を収穫しない 10 個以上の実があるならば、10 個を残…
for 文を使わなくても解けるけど、使えると楽！ 問題へのリンク 問題概要 10 冊の本を買った。その総額と、そのうちの 9 冊の価格が分かっている。残り 1 冊の本の価格を求めよ。 考えたこと まず総額の入力データを読み込みましょう。 そのあと、9 個の整数…
これは面白い！ 問題へのリンク 問題概要 文字 v, w のみからなる文字列 が与えられる。 この文字列中の下に尖っている箇所の個数を求めよ（v は 1 個、w は 2 個）。 考えたこと for 文を用いて、文字列 の文字を順に見ていき、それが v ならば 1 を足し、w…
いろんな解法あり。 問題へのリンク 問題概要 頂点数 の無向木が与えられる。各頂点 には色 が塗られている。 このグラフにおいて、 であるような頂点組 () についての、2 点 間の距離の総和を求めよ。 制約 考えたこと マージテクで考えた。例によって頂点 …
面白かった！ 問題へのリンク 問題概要 整数 が与えられる。 整数 の十進法表記を 個 concat してできる整数を 998244353 で割った余りを求めよ。 制約 考えたこと まず、整数 が 桁だとしよう！ このとき、求めたい値は次のように表現できる。 よって、 と…
すごく教育的問題！ 問題へのリンク 問題概要 非負整数 が与えられるので、次の値を 998244353 で割った余りを求めよ。 & 制約 考えたこと この手の問題は「主客転倒」して、上記の総和を各桁ごとに考えればよいと相場が決まっている！！！ 具体的には、次の…
面白かった！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 の値を求めよ。 制約 考えたこと まず、 という制約が怪しい！！！ きっと、 として な計算量になるに違いないと思えた。 とりあえず、数列を元のまま考えるのではなく、…
人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した！ 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…
「二分探索 lower_bound()」「累積和」を活用する、とてもとても典型的かつ教育的な問題ですね。 問題へのリンク 問題概要 サイズ の数列 と、サイズ の数列 が与えられる。 これらの数列から 1 個ずつ選んでできる 通りの各ペア についての、 の総和を求め…
FPS + 負の二項係数 問題へのリンク 問題概要 長さが で総和が であるような、正の整数のみからなる数列 すべてについての の総和を 998244353 で割ったあまりを求めよ ( ケース)。 制約 解法 (1)：FPS 求めたいものは である。これはちゃんと計算すると、 …
一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！ その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！ 問題へのリンク 問題概要 頂点数 、辺数 の単…
Suffix Array の典型問題 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列として登場しうる文字列をすべて考える。重複は除外する。これらの文字列の長さの総和を求めよ。 制約 考えたこと 次の問題とほと…
部分和問題の応用問題！ 問題へのリンク 問題概要 個の非負整数 が与えられれる。 これらの整数から 個選んで、総和が の倍数となるようにする。その値として考えられる最大値を答えよ。 の倍数にするのが不可能な場合は -1 を答えよ。 制約 前提知識 この問…
これを機会に SA-IS を整備した！ 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…
ABC C にありそうな教育的問題！ 問題へのリンク editorial 問題概要 正の整数 が与えられる。 かつ を満たすすべての整数組 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 (テストケース数) 考えたこと 結局、 を計算すればよい。それぞれ…
色んな解法がありそう。 問題へのリンク 問題概要 個の正の整数 が与えられる。 を満たすすべての非負整数列 に対する の総和を 1000000007 で割ったあまりを求めよ。 制約 解法 (1)：経路数への帰着 (僕の解法) 二項係数を扱う方法論として、経路数へと帰着…
この回の前の回の LCMs といい、約数系包除がこの時期流行ってたのかな。 問題へのリンク 問題概要 整数 が与えられる。 以上 以下のすべての整数 に対し、 に以下の操作を繰り返すことによって次に に戻るまでの操作回数 (戻らない場合 0) を足し合わせた値…
添字 GCD 畳み込みの練習問題！ 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…
添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…
りんごさんセット！！！ 問題へのリンク 問題概要 次元空間において () を満たす部分の体積を とすると は整数値となる。この整数値を 1000000007 で割ったあまりを求めよ。 制約 考えたこと 最初は色々迷走していた。三次元の場合を考えていて思っていたの…
本番は「どのように に分けても絶対値和は等しい」ということに気づかず、ものすごくエグい二項係数計算を頑張って綺麗な表式を得た。 問題へのリンク 問題概要 長さが の数列 が与えられる。 数列を 個ずつのペア (順序の違いは考慮する) に分ける方法は 通…
「要素を 1 個ずつ追加していくときに値がどう変化していくか」を観察する方向でずっと考えていて迷走してしまった... 問題へのリンク 問題概要 正の整数 と、 個の整数 が与えられる。 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 解法 個…
