最大回数・最大個数を求める
全探索思考に慣れてさえいれば、 の解法ならすぐに思いつく。少し工夫して、 の解法になる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の部分数列 であって が等差数列である である という条件を満たすものを考える。それらの数列の最大長…
という制約がいかにも怪しい！ 問題へのリンク 問題概要 1 以上 20 以下の整数からなる、長さ の数列 が与えられる。 この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。 …
ランレングス圧縮！ 問題へのリンク 問題概要 文字 'O', 'X' からなる長さ の文字列 が与えられる。 「'O' のみからなる連続 個の文字をすべて 'X' に書き換える」という操作を最大で何回行えるか？ 制約 考えたこと ランレングス圧縮が有効な問題。ランレン…
ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…
連想配列で集計するといい感じに解ける！ 問題へのリンク 問題概要 枚の靴下があって、靴下 の色は という整数値で表される。 色の等しい靴下をペアにするとき、最大で何ペア作れるか？ 制約 考えたこと 次のように考えたい。 色ごとに靴下が何個あるかを整…
これ意外と難しいと思う！ 問題へのリンク 問題概要 4 個の整数 (1, 2, 3, 4 のいずれか) が与えられる。これら整数に対して、 「2 個同じ整数があったら 2 個まとめて消す」 という操作を最大で何回できるか？ 考えたこと 整理が大変だけど、色んな解法があ…
平面走査の典型問題だけど、とにかく重くて辛かったのと、コーナーケースになかなか気づけなかった。 問題へのリンク 問題概要 数直線上に 個の区間がある。区間 は である ()。 = 区間 が、与えられた 個の区間のうち何個と交差するか としたときに、 の範…
この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ！ 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…
これはもう、editorial にある図がすべてなので備忘録程度に！ 問題へのリンク 問題概要 のグリッドがある。 個の石があり、石 は、 かつ を満たすようなマス に置くことができる。 ただし、どの行・どの列についても、2 個以上の石が置かれないようにする。…
ちょっと整理が難しい文章題。 問題へのリンク 問題概要 りんごが 個、りんごの欠片が 個ある。 1 個のりんごを砕くと、りんごの欠片が 個できる 2 個のりんごの欠片を使うと、アップルパイが 1 個できる 今ある材料から、最大で何個のアップルパイが作れる…
とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…
企業合コンで解いた。ギャグ系だった。 問題へのリンク 問題概要 円周上に 個の点があって、2 個ずつ 組のペアを作って線分で結ぶ。 すでに 組のペアができていて、線分が結ばれている。残りの点についてペアを作って線分を作っていったときの交差数の個数の…
ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索！ 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…
壁にぶつかるまで動く設定の迷路問題！ 問題へのリンク 問題概要 のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。 プレイヤーは最初、マス にいる (0-indexed)…
グリッドを市松模様に塗って、「黒色マス」と「白色マス」で二部マッチングするという、超典型問題！ 問題へのリンク 問題概要 のグリッドが与えられます。 各マスは「障害物」が置かれているか、「空」であるかのいずれかです。入力データにおいては、障害…
前から "PC" 詰めしていけば OK！！ 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 '.' か 'T' が書かれている。今、次の操作をできるだけ多く行いたいとする。 左右に 2 文字連続した "TT" を "PC" に置き換える 操作回数の最大化を目指…
とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…
2 種類の操作がある系の問題！こういうのは操作の手順を単純化して考えられる場合が多い 問題へのリンク 問題概要 正の整数 が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく を 倍する に を足す が 以上となってはならない…
久しぶりに素因数分解する問題が来た！！！！！！！！！！！ 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…
このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい！！！ 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるよう…
区間 DP な問題って、あまり見なくなったなと。貴重なので記録。 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 隣接する二項を選び、それらの値が等しいとき (v とする)、その 2 つの値を削除して、…
すごく面白かった！ 問題へのリンク 問題概要 ある数値が与えられる。ただしその数値は非常に桁数が大きいことがあるので、数値を 10 進法で表したときの文字列をランレングス圧縮した状態で与えられる。具体的には 組の値 が与えられて、 の順に、数値 が …
区間スケジューリング問題そのものだった！！！ ...とはいえ 200 点というのは衝撃！！！ 問題へのリンク 問題概要 ある工場では、 数直線上に 個のロボットが設置されている。 ロボット は座標 に設置されていて、左右に長さ のアームを伸ばしている。 これ…
嘘に悩んだ。なぜ嘘だと気付けなかった... 問題へのリンク 問題概要 以下の問いに 回答えよ (各問いは完全独立)。 個の区間 が与えられる。これらの区間の Union 個数とは、重なりのある部分をマージしてできるグループの個数のことである。 個の区間からど…
かなり辛いことを頑張ったけど、本当はすごく明快な問題だった！！ 問題へのリンク 問題概要 個の整数 がある。各 に対して、以下の答えを求めよ。 残っている整数から、どの 2 つも互いに異なる 個の整数を選んで抜き取ることを繰り返したい 抜き取れる回数…
これほとんど drken1215.hatenablog.com と同じ問題！！！ 問題へのリンク 問題概要 を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。 ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを…
久しぶりのカッコ列の整合判定問題！！！ カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…
一瞬罠があるのではと怖くなるやつ 問題へのリンク 問題概要 'W' と 'B' で構成された文字列が与えられる。 "BW" を "WB" に置き換える変換を好きな回数行える。最大回数を求めよ。 考えたこと 問題の操作はつまりは 'W' を左に動かす操作と読み替えられる。…
結構好きな問題 ABC 100 C - *3 or /2 問題概要 N 個の整数 a1, a2, ..., aN があって 1 回の操作で以下が行える 各整数について「3 倍」「2 で割るなら 2 で割る」のいずれかを行う どれかの整数については「2 で割る」の方をしなければならない 最大で何回…
