けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

今が良いほど未来も良いGreedy

AtCoder AGC 049 B - Flip Digits (緑色, 600 点)

簡単なバグを埋め込んでしまった... 問題へのリンク 問題概要 長さ の "0" と "1" のみからなる 2 つの文字列 が与えられる。 に対して以下の操作を繰り返し行うことで に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。 中の "01" …

AtCoder AGC 040 C - Neither AB nor BA (橙色, 800 点)

これまた楽しい数え上げ!!! 解説があまりにも天才だけど、解説の方法が思いつかなくても一応できた!!! 問題へのリンク editorial 解説放送 問題概要 "A", "B", "C" のみからなる長さ の文字列であって、以下の条件を満たすものの個数を 998244353 で割…

AOJ 2681 Parentheses (JAG 春コン 2014 E) (500 点)

めちゃくちゃ面白かった! 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…

AtCoder ABC 180 D - Takahashi Unevolved (茶色, 400 点)

2 種類の操作がある系の問題!こういうのは操作の手順を単純化して考えられる場合が多い 問題へのリンク 問題概要 正の整数 が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく を 倍する に を足す が 以上となってはならない…

AtCoder ABC 176 C - Step (灰色, 300 点)

Greedy の一番簡単なパターン 問題へのリンク 問題概要 人が 1 列に並んでおり、前から 番目の人の身長は です。 それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。 条件:踏み台を込めて身長を比較した…

AOJ 3174 No Palindromes (HUPC 2020 day3-C)

これ楽しい! 問題へのリンク 問題概要 長さ の英小文字のみからなる文字列 が与えられます。 の文字を入れ替えることによって、次の条件を満たす文字列 を作ることができるかどうかを判定してください (可能ならば具体例を 1 つ挙げてください)。 のどの長…

AtCoder ABC 148 D - Brick Break (灰色, 400 点)

とても教育的な Greedy かもしれない! 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列からいくつかの値を取り除くことで、数列が となるようにしたい。 取り除くべき個数の最小値を求めよ。どのように取り除いても の形にで…

AtCoder ABC 143 E - Travel by Car (青色, 500 点)

この Floyd--Warshall は天才すぎる! 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…

Codeforces Round #584 - Dasha Code Championship A. Paint the Numbers (R900)

誤読して大きく出遅れた... 問題へのリンク 問題概要 個の整数 があたえられる。これを何個かのグループに分けて、各グループについて「グループ内のすべての整数がグループ内の最小値で割り切れる」という条件を満たすようにしたい。 これを実現するための…

Codeforces Global Round 2 E - Pavel and Triangles (R1900)

こういう貪欲は確実に抑えて行きたい 問題へのリンク 問題概要 長さが の線分がそれぞれ 本ずつある。 これらから三角形は最大で何個作れるか? 制約 考えたこと 面白そう!!!!! な量を扱う問題リストにまた 1 問加えられる!!!!! この手の問題では…

AtCoder AGC 013 A - Sorted Arrays (茶色, 300 点)

個人的には超苦手系。。。 でもちゃんと Greedy 思考を整理すればできる。こういうのは Greedy 思考の「型」を理解することが大事そう。 問題へのリンク 問題概要 長さ の数列 が与えられる。 を何箇所かで切って、 の連続した部分であるようないくつかの数…

AtCoder AGC 011 A - Airport Bus (緑色, 300 点)

頭の整理がちょっと大変な問題 問題へのリンク 問題概要 人が次々とバス停に到着する ( 人の到着時刻が で与えられる)。以下の条件を満たすように乗客たちをバスに乗せていきたい。 どの乗客もバス停に到着してから 分以内に出発させる 1 台のバスには 人ま…

AtCoder AGC 009 A - Multiple Array (茶色, 300 点)

教育的 Greedy 問題! 問題へのリンク 問題概要 個の整数からなる数列 と数列 がある。以下の操作を好きな回数だけ行える: 以下の整数 を 1 つ選び、 の値を ずつ増やす すべての に対して が の倍数となるようにしたい。これを実現するための操作回数の最小…

AtCoder AGC 029 B - Powers of two (水色, 600 点)

「交換しても悪化しない」というのは Greedy の証明の共通構造だとは思う。 問題へのリンク 問題概要 個の正の整数 がある。 これらの 個の整数に対応する 頂点のグラフを考えて、和が の形で表せる 2 数間に辺を引く。 このグラフの最大マッチングを求めよ…