上手に式変形しよう！ 問題へのリンク 問題概要 正の整数からなるサイズ の数列 が与えられる。次の条件を満たす組 の個数を求めよ。 制約 考えたこと 条件が不思議だ。普通は よりも の方が大きいことが多いのに、 となる条件を問うとは。 さて、この手の数…

条件を上手に言い換えよう！ 問題へのリンク 問題概要 個の整数 が与えられる。 が平方数 という条件を満たすような組 の個数を求めよ。 制約 考えたこと これは「条件の言い換え」を頑張る問題。「 が平方数」という条件を扱いやすいように言い換えよう。こ…

「区間の値の和」を見たら、累積和をとろう！！ 問題へのリンク 問題概要 数列 と整数 が与えられる。 数列の連続する区間であって、その総和が に一致するものが何個あるかを求めよ。 制約 考えたこと 0-indexed で考える。 数列 の累積和を としよう。この…

連想配列の良い練習問題！ 問題へのリンク 問題概要 正の整数からなる数列が良い数列であるとは、数列に含まれる任意の整数値 について、数列中に がちょうど 個含まれていることをいう。 与えられた数列 に対して、いくつかの要素を削除することで、よい数…

意外と整理するのが大変だと思う。map を使って整理しようとするのも自然だが、もうちょっと簡単に解くことを考えよう。 問題へのリンク 問題概要 文字列を投稿すると得点が与えられるコンテストに、 個の文字列 がこの順に投稿され、それぞれ 点が与えられ…

ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…

区間を伸ばしたり縮めたりしながら、それに伴う「挿入」や「削除」に対処するデータ構造を考える系の問題！ 問題へのリンク 問題概要 数列 について、連続する 個の要素の種類数の最大値を答えよ。 制約 考えたこと 数列の幅 の区間をすべて調べるには、次の…

連想配列の練習問題！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。この数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、整数列を順に見ていったときの「 個目の値 の要素」の index を答えよ（存在しない場合は -1）…

これ面白かった！ 問題へのリンク 問題概要 数列 が与えられる。この数列の連続する部分数列について「その総和を で割った余り」を考える。 連続する部分数列をすべて考えたときの、「その総和を で割った余り」の総和を求めよ。 制約 考えたこと この問題…

map の練習問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、 かつ を満たす最大の整数 を求めよ（存在しない場合は -1）。 制約 考えたこと 基本的には次の情報を管理できる配列が欲しい。 last[v]：その時点で、 を満たす最大の …

スタックの応用問題！ ヒストグラムの最大長方形を求めるアルゴリズムと似たようなスタックの使い方をする！ 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの値は互いに相異なる。 各 に対して、次の条件を満たす整数 の個数を求めよ。 なる任…

「前回の値」を保持しながらシミュレーションする系 問題へのリンク 問題概要 ボタンを押すと、1 個の飴がもらえるが、前回飴をもらってから 秒間はもらえない。 高橋君は 回ボタンを押した。それぞれ 秒後に押した（これらは単調増加）。 何回飴をもらえた…

この時代、この手の Greedy はたくさんあったのね！ 問題へのリンク 問題概要 長さ の数列 が与えられる。「数列の要素を 1 つ選び、+1 するか、-1 する」という操作を行うことで、次の状態を達成したい。ただし、 とする。 すべての に対して、 である すべ…

bit 全探索が意外と思い浮かびづらいかもしれない。 問題へのリンク 問題概要 個の正の整数 が与えられる。これらの整数を A, B の 2 グループに分ける。 の最大値を求めよ。 制約 考えたこと bit 全探索を使うと、 個のものに対して「0」「1」の値を割り当…

コンテスト中最初に挑んだが解けず、その後も結局解けなかった。gcd convolution を思い出せなかった。 問題へのリンク 問題概要 長さ の正の整数からなる数列 、 が与えられる。これらの数列に対して 個のクエリが与えられる。 【クエリ】 正の整数 が与え…

計算量改善のことを本当に知らないと、TLE に悩むかもしれない。 問題へのリンク 問題概要 長さ の 2 つの数列 、 が与えられる。 1 以上 以下の整数 を選んで、 の最大値を求めよ。 制約 考えたこと 最も素直に考えると、次のように二重 for 文を用いて解き…

for 文の練習！ 問題へのリンク 問題概要 個の整数 のうち、最大値と最小値を除外した 個の整数の総和を求めよ。 制約 個の整数はすべて互いに相異なる 解法 まず 個の整数を「配列」として受け取りましょう (C++ では vector<int> 型など)。 その後、配列に対し</int>…

座標圧縮せよ、という問題 問題へのリンク 問題概要 長さ の数列 が与えられるので、座標圧縮せよ。 制約 考えたこと 座標圧縮は次の記事に詳しく書いた。 drken1215.hatenablog.com コード #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; v</bits/stdc++.h>…

スタックを用いて解決できる典型問題 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、 かつ を満たす最大の を求めよ (存在しない場合は -1)。 制約 メモ スタックを使うと の計算量で解ける。詳細は鉄則本を参照。 コード #include <bits/stdc++.h> usi</bits/stdc++.h>…

この手のスタックの問題はもうすっかり常識と化した！ 問題へのリンク 問題概要 ビル がこの順に並んでいる。ビル の高さは である。 各 に対して、ビル の間にビル より高いものがないような () の個数を求めよ。 制約 考えたこと いかにもスタックを使いそ…

きちんとした手続きを経て求めたいところ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。この数列に次の操作を繰り返して、数列の項がすべて相異なるようにしたい。できあがる数列の項数の最大値を求めよ。 【操作】 数列から 3 個の整数を選…

が関係ないやんけ！ 問題へのリンク 問題概要 高橋君は街 の順に訪れる。街 ではりんごの価値は 円である。 高橋君は街 で 円でりんごを好きな数だけ買うことができて、 を満たす街 でそのりんごを好きな数だけ 円で売ることができる。ただし、高橋君はりん…

多重 for 文の練習！ 問題へのリンク 問題概要 2 つの数列 、 が与えられる。数列 からそれぞれ 1 個ずつ選んでできる 個のペアについて 「その和」と「その最大値」の積 を求めて、それらの総和を求めよ。 制約 考えたこと 2 つの数列からそれぞれ要素をと…

for 文を回す処理を 回やる問題 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 が与えられる。 を に変更したときの、 の値を答えよ。（なお、クエリごとに変更は引き継がれない。） 考えたこと …

second best を求める系の問題 問題へのリンク 問題概要 個の相異なる整数 が与えられる。 この数列のうち 2 番目に大きいものについて、それが の何番目の要素であるかを求めよ。 制約 解法 (1)：max と second max を管理する 1 つ目の方法として、最大値…

「最大値と最小値の差」を最小化せよと言われたら、最大値または最小値を固定すると上手くいくことが多い！ 問題へのリンク 問題概要 サイズが であるような 4 つの数列 が与えられる。 これらの数列から 1 個ずつ要素を選んで とする。 の値の最小値を求め…

ちゃんと証明しようとすると、結構大変！ 問題へのリンク 問題概要 人の生徒がいて、生徒 の身長は である。 これらの生徒を 2 人ずつ 組に分けて、どの組も身長差が 以下となるようにしたい。 そのようなことが可能かどうかを判定せよ。 制約 考えたこと こ…

とても教育的な問題！ ちゃんと解くには、計算量の理解が必要となる問題である。 問題へのリンク 問題概要 3 つの数列 が与えられる。これらの数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、 からそれぞれ 1 個ずつ選んで和を…

とても教育的で典型的なしゃくとり法の問題！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。 が等差数列であるような組 の個数を求めよ。 制約 解法 (1)：しゃくとり法 今回の問題のように、数列中で条件を満たす区間を考える問題では、しゃ…

set を使おう！ 問題へのリンク 問題概要 長さ の整数列 と、正の整数 が与えられる。 以上 以下の整数のうち、数列 に一度も含まれないものについての総和を求めよ。 制約 考えたこと まず、 となる。 この値から「1 以上 以下の整数のうち、数列 に一度以…