Greedy
よくある priority queue の使い方！ 問題へのリンク 問題概要 個の正の整数 から重複を許して何個か選んだ総和として考えられる値のうち、小さい方から 番目の値を求めよ。 制約 考えたこと この手の priority queue の使い方はよくある。「小さい順に 個を…
順列を題材とした面白い問題。トポロジカルソートの問題でもある。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすもののうち、辞書順最小のものを求めよ。 【 番目の条件】 は よりも先に来る 制約 考えたこと グラフの問題として考えて…
Greedy の基本でもある。 問題へのリンク 問題概要 駅 があって、駅 から駅 へと、時刻 以降、 秒ごとに発車する列車があって、移動に 秒かかる。他の駅間を移動する列車はない。また、 は の倍数であることが保証される。 各 に対して、駅 を時刻 0 に出発…
初歩的な Greedy の問題と言える。 問題へのリンク 問題概要 以上 以下の整数からなる数列 であって、 は で割り切れる という条件を満たすものを考える。そのような数列の長さの最大値を求めよ。 制約 考えたこと 基本的には、なるべく小さい値でスタートし…
バケットを用いた集計処理や、Greedy の練習！ 問題へのリンク 問題概要 個の整数 が与えられる。いくつかの整数を他の好きな整数に書き換えることで、数列に含まれる整数値の種類数が 以下となるようにしたい。 書き換える整数の個数の最小値を求めよ。 制…
面白かった！ 問題へのリンク 問題概要 英小文字および文字 '?' からなる文字列 が与えられる。 の各 '?' を英小文字に置き換えてできる文字列のうち、次の条件を満たす辞書順最小のものを求めよ。 (条件) 文字列 を連続する部分文字列として含む 制約 考え…
Greedy の本当に初歩の問題といえる。 問題へのリンク 問題概要 整数 1 がある。この整数に対して、以下のいずれかの操作を 回行う。 操作 A：整数値を 2 倍する 操作 B：整数値に を足す 操作後の整数値の最小値を求めよ。 制約 考えたこと 基本的に、「も…
実装が少し大変だった。そして、両端から Greedy で追い詰めていけばよいのは思いつかなかった。チームメイトが思いついていた。 問題へのリンク 問題概要 1 から までの整数が書かれたカードが合計で 枚あり、整数 の書かれたカードは 枚ある。各 に対して…
長さが大きい順に処理していこう！ 問題へのリンク 問題概要 長さが の棒がある。 これらの棒を 4 個選んで長方形を作りたい。作れる長方形の面積の最大値を求めよ。長方形を作れない場合は 0 と答えよ。 制約 考えたこと できるだけ大きい長さの棒を使いた…
で解けた！ 同じ値が連続する場合の対処に苦慮した。 問題へのリンク 問題概要 強さが のスライムが一列にこの順に並んでいる。 に対して、次の問に答えよ。 【問】 初期状態で左から 番目にいるスライムが高橋君である。高橋君が下記の行動を好きな回数だけ…
ソートの練習！ 問題へのリンク 問題概要 個の整数 から 選んで総和をとる。 総和を取った値の最大値を求めよ。 制約 考えたこと 個の整数 を大きい順に並べておいて、大きい順に 個とって足せばよい。 C++ では、大きい順にソートするのは sort(l.begin(), …
これ面白かった！ ABC-E で出題されて水色 Diff などがあり得そうな雰囲気。 問題へのリンク（仮） 問題概要 正の整数 が与えられる。 以上 以下の整数のうち、popcount が最小のものを求めよ。複数ある場合は、そのうちの最小の整数を求めよ。 制約 考えた…
面白かった！ 解説 AC した！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。このグラフの辺の順列であって、次の条件を満たすものを 1 つ求めよ（なければ -1 を出力せよ）。 【条件】 頂点数 、辺数 のグラフに対して、上記の順序…
これはややこしい！ 問題へのリンク 問題概要 マス が一列に並んでいる。最初、 個のマスに石が入っており、マス には 個の石が入っている。あなたは以下の操作を好きな回数行うことができる。 「マス に石があるとき、マス からマス へと石を 1 つ移動させ…
辞書順最小と言われたら......！！ 問題へのリンク 問題概要 文字 'd', 'p' からなる長さ の文字列 が与えられる。 この文字列のある区間をとって、その区間を 180 度回転させる（reverse した上で、'd' と 'p' を入れ替える）。 こうしてできる文字列のうち…
問題を言い換えるのが少し難しい 問題へのリンク 問題概要 頂点数 の木が与えられる（頂点番号 ）。 この木に対して「葉を 1 つ選んで削除する」という操作を繰り返す。頂点 1 を削除するまでの操作回数の最小値を求めよ。 制約 考えたこと 0-indexed で考え…
これ結構難しくて、嵌まる人は嵌まってしまうと思う！！ 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 2 つの整数 で表される。 のとき：ポーション が現れる それを拾うかどう…
面白い。各値に対する答えを予め整理して求めておく手法は頻出！ 問題へのリンク 問題概要 個の品物がある。品物 は、重さが であり、価値が である。 いくつかの品物を、総和が 以下となるように選ぶとき、選んだ品物の価値の総和の最大値を求めよ。 制約 …
この時代、この手の Greedy はたくさんあったのね！ 問題へのリンク 問題概要 長さ の数列 が与えられる。「数列の要素を 1 つ選び、+1 するか、-1 する」という操作を行うことで、次の状態を達成したい。ただし、 とする。 すべての に対して、 である すべ…
集計処理の応用問題 問題へのリンク 問題概要 一般に、文字列 からいくつかの文字を抜き出して、それを並び替えることによって文字列 を作れるとき、 から を作れるという。 英小文字からなる 個の文字列 が与えられる。 のいずれからも作れる文字列 のうち…
が関係ないやんけ！ 問題へのリンク 問題概要 高橋君は街 の順に訪れる。街 ではりんごの価値は 円である。 高橋君は街 で 円でりんごを好きな数だけ買うことができて、 を満たす街 でそのりんごを好きな数だけ 円で売ることができる。ただし、高橋君はりん…
一見、 の DP に見えたが、その必要はなかった。 問題へのリンク 問題概要 グーとパーしか出せないジャンケンを 回する。相手が各回に何を出すかが予めわかっている。ただし、どの時点でも (それまでに出したグーの回数) (それまでに出したパーの回数) を満…
操作回数を最小化せよ、という問題だけど、実際には「複数ある場合は辞書順最小のものを求めよ」という部分に本質がある問題！ 問題へのリンク 問題概要 文字列 は文字数が等しい。 に対して「1 文字変更する」という操作を繰り返すことで にしたい。 そのう…
ちゃんと証明しようとすると、結構大変！ 問題へのリンク 問題概要 人の生徒がいて、生徒 の身長は である。 これらの生徒を 2 人ずつ 組に分けて、どの組も身長差が 以下となるようにしたい。 そのようなことが可能かどうかを判定せよ。 制約 考えたこと こ…
Euler Tour して、遅延評価セグ木（区間加算 + 区間 min）に乗せて......という解法を考えていたところに、あまりにもシンプルな想定解法を目にして、感動した！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる。 に対して、次の問に答えよ。 個…
ちょっとした算数の問題 問題へのリンク 問題概要 3 個の整数 が黒板に書かれている。 今、「3 個の整数のうち 1 つを選び、それを 2 倍した値に書き換える」という操作を 回行う。 操作後の 3 個の整数の和の最大値を求めよ。 制約 考えたこと 基本的な戦略…
文字列を左から見ていき、隣接する 2 文字が異なる箇所を見つけるやいなや、マルバツスタンプを使う、という Greedy でよい！ 問題へのリンク 問題概要 マルスタンプ、バツスタンプ、マルバツスタンプの 3 種類がある。 マルスタンプを使うと、文字 'O' を印…
面白かった！ 問題へのリンク 問題概要 人がいて、人 の考察力、実装力、運はそれぞれ である。 これら から 3 人を選ぶ。ただし、3 人全員について「考察力・実装力・運のうちのいずれかについては他 2 人よりも真に高い」という条件を満たさなければならな…
今や超有名な Greedy 問題「コインの枚数最小化問題」 問題へのリンク 問題概要 JOI 雑貨店には硬貨は 500 円、100 円、50 円、10 円、5 円、1 円の硬貨が十分な枚数ある。 円の買い物をして 1000 円を支払った太郎くんに、硬貨の枚数が最小となるようにお釣…
面白い問題！ 問題へのリンク 問題概要 箱 とボール がある。ボール は箱 に入っていて、その重さは である。 これから、ボールの入っている箱を移すことで、どの箱にもちょうど 1 個ずつボールが入っている状態にしたい。ボールを移すコストは、そのボール…
