解空間:O(N^2)通りの選択肢
これは典型らしいので、このセグメント木の使い方は今後押さえる！ 問題へのリンク 問題概要 正の整数からなる数列 が与えられる。 一般に、数列 に対して、 とする。まず の値を求めて、その後、次の 回のクエリに答えよ。 【クエリ】 整数 が与えられるの…
ちょっと工夫が必要な感じ 問題へのリンク 問題概要 長さ 正整数列 と、正の整数 が与えられる。 数列の区間であって、総和を で割った余りと、区間内に含まれる要素の個数とが等しいものの個数を求めよ。 制約 考えたこと 結構ややこしい。落ち着いて条件を…
上手に式変形しよう！ 問題へのリンク 問題概要 正の整数からなるサイズ の数列 が与えられる。次の条件を満たす組 の個数を求めよ。 制約 考えたこと 条件が不思議だ。普通は よりも の方が大きいことが多いのに、 となる条件を問うとは。 さて、この手の数…
条件を上手に言い換えよう！ 問題へのリンク 問題概要 個の整数 が与えられる。 が平方数 という条件を満たすような組 の個数を求めよ。 制約 考えたこと これは「条件の言い換え」を頑張る問題。「 が平方数」という条件を扱いやすいように言い換えよう。こ…
「区間の値の和」を見たら、累積和をとろう！！ 問題へのリンク 問題概要 数列 と整数 が与えられる。 数列の連続する区間であって、その総和が に一致するものが何個あるかを求めよ。 制約 考えたこと 0-indexed で考える。 数列 の累積和を としよう。この…
すごく面白い問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から異なる 2 つの文字列を選ぶ方法であって、それらの文字列が互いにアナグラムとなっているものの個数を求めよ。 制約 考えたこと まずは、問題の条件をわかりやすく…
「主客転倒・寄与分解」の典型問題！ 問題へのリンク 問題概要 1 から 9 までの数字からなる 桁の整数値 が与えられる。 この整数値の連続する区間を取り出してできる整数値の総和を求めよ。（998244353 で割らない。） 制約 考えたこと この手の問題では、 …
これ面白かった！ 問題へのリンク 問題概要 数列 が与えられる。この数列の連続する部分数列について「その総和を で割った余り」を考える。 連続する部分数列をすべて考えたときの、「その総和を で割った余り」の総和を求めよ。 制約 考えたこと この問題…
が関係ないやんけ！ 問題へのリンク 問題概要 高橋君は街 の順に訪れる。街 ではりんごの価値は 円である。 高橋君は街 で 円でりんごを好きな数だけ買うことができて、 を満たす街 でそのりんごを好きな数だけ 円で売ることができる。ただし、高橋君はりん…
set の使い方を覚えよう！ 問題へのリンク 問題概要 文字列 が与えられる。 の連続する部分文字列として考えられるものの個数を求めよ。 制約 考えたこと の連続する部分文字列をすべて取り出して、それを set に格納して、そのサイズを求めれば良い。 の連…
操作によってできるものの個数を数え上げる系の問題の最も基本的な問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を 1 回行ってできる文字列が何種類あるかを求めよ。 を満たす を好きなように選んで、 の 文字目と 文字目を swap …
とても教育的で典型的なしゃくとり法の問題！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。 が等差数列であるような組 の個数を求めよ。 制約 解法 (1)：しゃくとり法 今回の問題のように、数列中で条件を満たす区間を考える問題では、しゃ…
円環上の Zero-Sum Ranges!! 問題へのリンク 問題概要 円周上に 個の地点 がこの順に時計回りに並んでいる。地点 から地点 （ のとき とする）まで時計回りに移動するのに要する時間は である。 次の条件を満たす の個数を求めよ から時計回りに へと到達す…
の制約が小さいので、「区間」を思い切って全部探索しよう！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 を満たすような についての、 の値の最大値を求めよ。 制約 解法 この手の問題で悩んでしまうのはもったいないと言えます！ まずは、コンピ…
多重 for 文に慣れよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 を満たす整数の組 の個数を求めよ。 制約 解法 多重 for 文に慣れましょう！ 数列 の 番目と、数列 の 番目をすべて調べるのは、次のような 2 重の for 文で記…
いろんな解法あり。 問題へのリンク 問題概要 頂点数 の無向木が与えられる。各頂点 には色 が塗られている。 このグラフにおいて、 であるような頂点組 () についての、2 点 間の距離の総和を求めよ。 制約 考えたこと マージテクで考えた。例によって頂点 …
久々！ Functional Graph のサイクル検出と DP 問題へのリンク 問題概要 頂点数 の functional graph が与えられる (出次数 1 の有向グラフ)。 このグラフの 2 頂点 からなる順序対 であって、頂点 から頂点 へと至るウォークが存在するものの個数を求めよ (…
しゃくとり法の練習問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 この数列の連続する区間であって、総和が 以下であるものの個数を求めよ。 制約 解法 (1)：しゃくとり法 editorial に詳しく書かれている。 github.com コー…
これはちょっと整理が大変な問題。時々問題文に登場する 0.5 という数値がなんなのかを知れる問題とも言える。 問題へのリンク 問題概要 個の区間がある。各区間は 4 タイプあり、 タイプ 1：区間 タイプ 2：区間 タイプ 3：区間 タイプ 4：区間 となってい…
二重 for 文の練習！ 鉄則本の例題なので解法はメモ程度に。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらから要素を 1 つずつ選び、和が となるようにすることが可能か判定せよ。 メモ 二重の for 文を使おう！ コード #include <bits/stdc++.h> using na</bits/stdc++.h>…
人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した！ 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…
この問題を思い出した！ 問題へのリンク 問題概要 素数 と、 個の 1 以上 以下の整数 が与えられる。 を満たす整数 が存在するような の組の個数を数え上げよ。 制約 考えたこと 一瞬、原始根を考えたくなったが、原始根ではなく「位数」を考えた方が計算量…
次の問題にとても似ていた！ drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…
最長回文を求める問題！ 問題へのリンク 問題概要 文字列 が与えられる。 の連続する部分文字列のうち、回文であるものについて、最長の長さを求めよ。 考えたこと この問題は次の 2 ステップに分かれている。 の連続する部分文字列を全種類抜き取る それら…
問題を典型パーツに分解して考察を積み上げていく系の、とても教育的な問題！ 問題へのリンク 問題概要 個の文字列 と文字列 が与えられる。以下の条件を満たす の組の個数を求めよ。 と をこの順に連結してできる文字列から、いくつかの文字を選び、順序を…
「二分探索 lower_bound()」「累積和」を活用する、とてもとても典型的かつ教育的な問題ですね。 問題へのリンク 問題概要 サイズ の数列 と、サイズ の数列 が与えられる。 これらの数列から 1 個ずつ選んでできる 通りの各ペア についての、 の総和を求め…
Z-algorithm や Suffix Array が使える面白い文字列検索問題！ 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たす文字列 の組が何個あるかを答えよ。 はいずれも空文字ではない である 制約 考えたこと この手の問…
セグ木とか必要なくて、本当に単純な実装で解けるの面白い 問題へのリンク 問題 制約 考えたこと まずは、生成可能であるための分かりやすい特徴付けを考えようと思った。数列の生成手順が、いかにも入れ子構造をしているので、カッコ列を連想した。 カッコ…
有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…
くしらっちょ君と一緒に解いた！ 実装が辛い。 問題へのリンク 問題概要 頂点数が である凸多角形が与えられる。この凸多角形の面積を とする。 今、凸多角形の隣接しない 2 頂点を結ぶ直線によって凸多角形を 2 つの多角形に分ける。そして、2 つの多角形う…
