最大スコア
いろんな解法がある！ 問題へのリンク 問題概要 以上 以下の整数のうち、 との差の絶対値が最も小さいものを求めよ。 制約 解法 (1)：for 文 一番確実な方法は、for 文を用いて、 をすべて調べることだと思われます。 が最小となるような を求めればよいでし…
集計処理の面白い問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 に出現する整数のうち、出現回数が最小である整数を出力せよ。そのようなものが複数あるときは、そのうちの最小の整数を出力せよ。 制約 解法 このような出現頻度に関する問題で…
とっても教育的な DP の問題！！！ 問題へのリンク 問題概要 高橋君の前に 個の料理が順に配られる。高橋君はその都度「食べる」「下げてもらう」を選択することができる。 番目の料理は、 のとき、解毒剤入りの、美味しさが の料理 のとき、毒入りの、美味…
すごく面白い問題！ いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…
めっちゃ面白い問題！！ 実はよく似た類題として次の問題がある！ atcoder.jp 問題へのリンク 問題概要 長さが の数列 が与えられる。この数列から 個の要素を削除する。 残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。 制約 考えたこと …
「ギリギリを考える」という考察の基本形と言える問題 問題へのリンク 問題概要 整数 が与えられるので、 を満たす整数 についての の最大値を求めよ。 制約 考えたこと この手の問題で考えることは、「端点のみ考えれば良いのでは」などと疑うこと。つまり…
文字列の動きをシミュレーションしながら最大値も更新していく！ 問題へのリンク 問題概要 整数 を持っていて、最初は 0 である。 長さ の文字列 に従って、これを使って 回の操作を行った。 回目の操作では、文字 が 'I' ならば を 1 増やし、'D' ならば を…
個から 個を選ぶ設定の問題！ 問題へのリンク 問題概要 個の整数値 が与えられる (負値もありうる)。 これらの整数から 個選んで積をとった値の最大値を、1000000007 で割った余りを求めよ。 制約 考えたこと 本質的に、次の 2 パターンに分かれると考えた。…
これはもう、editorial にある図がすべてなので備忘録程度に！ 問題へのリンク 問題概要 のグリッドがある。 個の石があり、石 は、 かつ を満たすようなマス に置くことができる。 ただし、どの行・どの列についても、2 個以上の石が置かれないようにする。…
Dilworth の定理から、DAG の最小パス被覆！！ かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…
の計算量までなら比較的すぐできる！ 問題へのリンク 問題概要 街 があって、街 間の行き来には だけの通行料がかかる。 回の市場がそれぞれ街 で行われ、 円えられる。 最初、無限の所持金を持っている。いくつかの市場に参加する (全く参加しなくてもよい)…
とても典型的で教育的な「燃やす埋める」の練習問題！ 問題へのリンク 問題概要 枚のカード があり、カード を使用するには だけコストがかかる。 一方、いくつかのカードを使用した場合、次の 種類のボーナス があり、ボーナス をクリアすると だけスコアを…
面白かった。JOI でもありそうな問題。長方形を 3 枚並べるのは典型らしい。 問題へのリンク 問題概要 のグリッドがあって、各マス には数値 が描かれている。 このグリッド上で の正方形を重ならないように 3 枚並べるとき、これらの正方形に覆われたマスの…
頭を柔らかくして考えよう。 問題へのリンク 問題概要 3 個の整数 から 2 個選んで和をとる。 この和の最大値を求めよ。 解法 3 個の整数 から 2 個選んだ和は の 3 通りがある。これらの最大値を求めればよい。 #include <bits/stdc++.h> using namespace std; int main() </bits/stdc++.h>…
頑張って頭を整理しよう！ 問題へのリンク 問題概要 整数 が与えられる。 , となるように整数 を選ぶとき、 の最大値を求めよ。 解法 を最大にするためには、 を最大にする を最小にする ようにすればよい。よって、 , のときに は最大であり、最大値は であ…
文字列として処理した方が楽。 問題へのリンク 問題概要 3 桁の正の整数 が与えられる。これらの整数の桁和の最大値を求めよ。 制約 整数 はそれぞれ文字列として受け取った方が楽だと思われる。そうすると、 たとえば、3 桁の整数を表す文字列 A について …
ちょっと整理が難しい文章題。 問題へのリンク 問題概要 りんごが 個、りんごの欠片が 個ある。 1 個のりんごを砕くと、りんごの欠片が 個できる 2 個のりんごの欠片を使うと、アップルパイが 1 個できる 今ある材料から、最大で何個のアップルパイが作れる…
JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…
慎重に解いた。ノーペナで解けたのは収穫。 問題へのリンク 問題概要 のグリッドに、以下の条件を満たすように 個のルークと 個のポーンを配置することが可能かどうかを判定せよ (ルークとポーンを合わせて駒と呼ぶ)。 どのルークについても、それと同じ行・…
面白かった！ 問題へのリンク 問題概要 個の正の整数 を 個のグループに分ける。ただし、どのグループの要素数も 1 個以上 2 個以下でなければならない。 最適なグループ分けをしたときの、各グループの要素の総和の二乗の総和の最小値を求めよ。 制約 考え…
整理するのが難しい！ 問題へのリンク 問題概要 3 個の 1 桁の整数 が与えられる。 このうちの 2 個を選んで並べて 2 桁の整数を作る。さらに、その残りの 1 個の整数をそれに足す。 こうしてできる整数の最大値を求めよ。 解法 たとえば、3 個の整数が のと…
3 人一組になる問題 問題へのリンク 問題概要 人がいる。 人が 1 グループになることができる。作れるグループの個数は最大何個か？ 解法 を で割った商が答えとなる。その余りの人数だけ余ることになる。 #include <bits/stdc++.h> using namespace std; int main() { int </bits/stdc++.h>…
すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…
Project Selection がピッタリハマる問題！ 問題へのリンク 問題概要 個の家 がある。家 に入るためには のコストがかかるが、その代わり の利得が得られる。また、各家 に対して、次の 個の制約条件が付随している。 家 に入ることなくして、家 に入ること…
lower_bound() 系の教育的問題 問題へのリンク 問題概要 一直線上に 個の点がある。点 の座標は である。 この直線上で幅 の区間を配置する。左端の座標を とするとき、 を満たす の個数をスコアとする。最大スコアを求めよ。 制約 考えたこと まず重要な考…
式がいかめしくて戸惑うけど、DP 自体は比較的単純 問題へのリンク 問題概要 個の値 が与えられる。 これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 個の整数 を選んだとしたとき、 で与えられる。このスコアの最大値を求めよ。 制約 考えたこ…
「与えられたグラフを強連結成分分解すると DAG になるので、DAG 上で DP する」というのが想定解だが、フローでも解けると話題になった問題！ 問題へのリンク 問題概要 頂点数 の有向グラフがある。最初、すべての頂点は白色である。以下の操作を 2 回行う…
o......f...(.....)... のようなパターンで、(.....) の中身が消せるような場合を最初見落とした。 問題へのリンク 問題概要 長さ の文字列 に対して、次の操作を好きな回数だけ行える。操作後の文字列の長さとして考えられる最小値を求めよ。 が連続する部…
会議設定時間を 0 時、1 時、2 時、...、23 時をそれぞれ全探索するのが一番分かりやすいと思う！ 問題へのリンク 問題概要 キーエンス社員の 個の拠点に対して同時に会議を設定したい。拠点 には社員が 人いて、時差 (世界標準時で 0 時のときの時刻) は で…
「平均値の最適化」を二分探索に帰着させる系の典型問題！ 問題へのリンク 問題概要 体のモンスターがいて、それぞれ質量は 、魔力は である。 また、 体のお助けモンスターがいて、それぞれ質量は 、魔力は である。 今、これら 体のモンスターからちょうど…
