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

一次元 DP で「配る DP」が書きやすい問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 マス目に と記された マスの双六がある。1 からスタートして へ進みたい。 マス からマス () に進むことができて：100pt 獲得 マス からマス () に進むこ…

区間の左端と右端を添字にもちつつ、左端を除去したり右端を除去したりする DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 ブロック がこの順に一列に並んでいて、「左端のブロックまたは右端のブロックを除去する」という操作を 回行って…

LCS を求める DP の練習。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 2 つの文字列 が与えられる。 の部分列でも の部分列でもあるような文字列の長さの最大値を求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; int main() { string S, </bits/stdc++.h>…

ナップサック問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 宝箱には 個の品物が入っている。品物 の重さは 、価値は である。 太郎君は、いくつかの品物を選んで持ち帰りたいと考えている。しかし、彼のナップザックには容量制限があるの…

この時代多く見られた「グルーピング」の問題！ 問題へのリンク 問題概要 S 型ピース 1 個と c 型ピース 2 個を使って、下図のように Scc を 1 個作ることができる。 また、c 型ピース 2 個を使って S 型ピース 1 個を作ることもできる。 今、S 型ピースが …

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

制約が なのがびっくり。素直に連続部分列をすべて調べると TLE してしまう。そのような問題は B 問題で登場するイメージがないので、現代なら などとしそうだ。 問題へのリンク 問題概要 文字列 の連続する部分文字列であって、先頭が 'A' で末尾が 'Z' で…

一見、 の DP に見えたが、その必要はなかった。 問題へのリンク 問題概要 グーとパーしか出せないジャンケンを 回する。相手が各回に何を出すかが予めわかっている。ただし、どの時点でも (それまでに出したグーの回数) (それまでに出したパーの回数) を満…

ちょっと実装が重たい。 問題へのリンク 問題概要 グリッドが与えられる。最初、どのマスにもなんらかの色（整数値）がついている。 マス から辺で接しているマスへの移動を繰り返し、マス と色が異なるマスに入ることなく移動できるマスの集まりを、マス の…

再帰関数を使った全探索の練習！ こういうのは本当に練習になる。 問題へのリンク 問題概要 各マスが 0 または 1 であるような の二次元グリッド が与えられる。 グリッド上の各マスを渡り歩いていく移動経路のうち、次の条件を満たすものを考える。 1 回の…

ちょっとした算数の問題 問題へのリンク 問題概要 3 個の整数 が黒板に書かれている。 今、「3 個の整数のうち 1 つを選び、それを 2 倍した値に書き換える」という操作を 回行う。 操作後の 3 個の整数の和の最大値を求めよ。 制約 考えたこと 基本的な戦略…

算数的な問題 問題へのリンク 問題概要 高橋君は金色の硬貨が好きです。自分が持っている 500 円硬貨 1 枚につき 1000、5 円硬貨 1 枚につき 5 の「嬉しさ」を得る。 高橋君が 円もっているとき、高橋君の「嬉しさ」の最大値はいくらか？ 制約 考えたこと コ…

上手に場合分けして解いていこう。 問題へのリンク 問題概要 1 が書かれたカードが 枚、0 が書かれたカードが 枚、 −1 が書かれたカードが 枚ある。 これらのカードから、ちょうど 枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最…

連想配列のいい練習問題！ 問題へのリンク 問題概要 種類のビーンズがあって、 種類目のビーンズはおいしさが で色が である。ビーンズは混ぜられており、色でしか区別することができない。 あなたはビーンズの色を 1 つ選び、その色のビーンズをどれか 1 粒…

少し数学チックな問題！ 問題へのリンク 問題概要 二次元の座標平面上に 個の点がある。点 の座標は である。 これら 個の点から 4 個を選ぶ。選んだ 4 点が正方形の頂点となる場合についての、正方形の面積の最大値を答えよ。 制約 考えたこと であるような…

とても色んな解法が考えられそうだ。 問題へのリンク 問題概要 以上 以下の 個の整数から相異なる 個の整数を選んで並べて得られる数列 が与えられる。 今、この数列の中に である要素があるならば、その要素を 1 以上 以下の好きな整数に書き換えてよい。 …

何気にちゃんと証明しようとすると、結構大変な問題な気もする！ 問題へのリンク 問題概要 長さが である 個の文字列 が与えられる。 これらを好きな順番ですべて結合して得られる文字列のうち、辞書順最小のものを求めよ。 制約 考えたこと 直感的には、 を…

の制約が小さいので、「区間」を思い切って全部探索しよう！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 を満たすような についての、 の値の最大値を求めよ。 制約 解法 この手の問題で悩んでしまうのはもったいないと言えます！ まずは、コンピ…

いろんな解法がある！ 問題へのリンク 問題概要 以上 以下の整数のうち、 との差の絶対値が最も小さいものを求めよ。 制約 解法 (1)：for 文 一番確実な方法は、for 文を用いて、 をすべて調べることだと思われます。 が最小となるような を求めればよいでし…

集計処理の面白い問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 に出現する整数のうち、出現回数が最小である整数を出力せよ。そのようなものが複数あるときは、そのうちの最小の整数を出力せよ。 制約 解法 このような出現頻度に関する問題で…

とっても教育的な DP の問題！！！ 問題へのリンク 問題概要 高橋君の前に 個の料理が順に配られる。高橋君はその都度「食べる」「下げてもらう」を選択することができる。 番目の料理は、 のとき、解毒剤入りの、美味しさが の料理 のとき、毒入りの、美味…

すごく面白い問題！ いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…

めっちゃ面白い問題！！ 実はよく似た類題として次の問題がある！ atcoder.jp 問題へのリンク 問題概要 長さが の数列 が与えられる。この数列から 個の要素を削除する。 残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。 制約 考えたこと …

「ギリギリを考える」という考察の基本形と言える問題 問題へのリンク 問題概要 整数 が与えられるので、 を満たす整数 についての の最大値を求めよ。 制約 考えたこと この手の問題で考えることは、「端点のみ考えれば良いのでは」などと疑うこと。つまり…

文字列の動きをシミュレーションしながら最大値も更新していく！ 問題へのリンク 問題概要 整数 を持っていて、最初は 0 である。 長さ の文字列 に従って、これを使って 回の操作を行った。 回目の操作では、文字 が 'I' ならば を 1 増やし、'D' ならば を…

個から 個を選ぶ設定の問題！ 問題へのリンク 問題概要 個の整数値 が与えられる (負値もありうる)。 これらの整数から 個選んで積をとった値の最大値を、1000000007 で割った余りを求めよ。 制約 考えたこと 本質的に、次の 2 パターンに分かれると考えた。…

これはもう、editorial にある図がすべてなので備忘録程度に！ 問題へのリンク 問題概要 のグリッドがある。 個の石があり、石 は、 かつ を満たすようなマス に置くことができる。 ただし、どの行・どの列についても、2 個以上の石が置かれないようにする。…

Dilworth の定理から、DAG の最小パス被覆！！ かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…

の計算量までなら比較的すぐできる！ 問題へのリンク 問題概要 街 があって、街 間の行き来には だけの通行料がかかる。 回の市場がそれぞれ街 で行われ、 円えられる。 最初、無限の所持金を持っている。いくつかの市場に参加する (全く参加しなくてもよい)…