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

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

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

AOJ ???? 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 つ選び、 の値を ずつ増やす すべての に対して が の倍数となるようにしたい。これを実現するための操作回数の最小…