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

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

ある量を決めるとGreedy

AtCoder ABC 133 D - Rain Flows into Dams (400 点)

時々こういうの見る気がする。とりあえず求めたい値を と置いてみる感じ。 問題概要 を奇数とする。整数 が与えられるので ... を満たすような を求めよ。 制約 は奇数 考えたこと 問題の構造として 「 を決めると、残りが芋づる式にすべて決まってしまう」 …

AtCoder ABC 128 F - Frog Jump (600 点)

ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける 調和級数になるタイプの全探索 というタイプの問題。結構重たい。AGC なら C 問題でありそう。 問題へのリンク 問題概要 個の地点 にそれぞれ のスコ…

AtCoder ABC 128 D - equeue (400 点)

こういう全探索が意外と出てこないという意見はよく聞くよね。 同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。 問題へのリンク 問題概要 あなたは誕生日プレゼントとして友人から dequeue D を貰いま…

AtCoder ABC 116 D - Various Sushi (400 点)

学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった! 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…

AtCoder ARC 074 D - 3N Numbers (500 点)

昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…

Tenka1 2019 C - Stones (300 点)

これをもっと早く 問題へのリンク 問題概要 長さ の白黒列が与えられる。最小個数のマスの白と黒を入れ替えることで、「黒」と「白」とが連続している箇所がないようせによ。 制約 考えたこと つまりは「白白白白黒黒黒黒黒」のように 左 left 個が白 右 N -…

Codeforces 552 DIV3 G. Minimum Possible LCM (R2400)

天才か!!! 問題へのリンク 問題概要 個の整数 が与えられる。 < となる であって、LCM() が最小となるものを求めよ。 制約 考えたこと という制約がいかにも怪しい。この制約が意味するのは 配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな…

AtCoder AGC 004 A - Divide a Cuboid (200 点)

割と難しい気がする。数学センスが少し必要な感じ 問題へのリンク 問題概要 のブロックが の直方体状に並んでいます。 高橋君は各ブロックを赤色または青色で塗ろうとしています。 このとき、次の条件が成り立つようにします。 赤いブロックも青いブロックも…

Educational Codeforces 62 C - Playlist

楽しかった 問題へのリンク 問題概要 個のアイテムがあって、それぞれ時間 と美しさ の属性がある。今、 個の中から 個選びたい。選んだアイテムたちのスコアは (選んだアイテムの時間の総和) × (選んだアイテムの美しさの最小値) で決まる。このスコアの最…

AtCoder AGC 001 C - Shorten Diameter (600 点)

ツリーの問題!!!!!!!! 見るからにツリー DP っぽいのだけど、なかなかに頭が混乱する感じ。 この問題の心得は「最適解はどんな形をしているんだろう」を考えることかなと思う。それによって「こういうものだけ探索すれば良い」というのが見えて来る…

AOJ 3056 Equilateral Triangle (RUPC 2019 day2-F)

計算量的な詰めが甘かった。二分探索要らなかった。 問題へのリンク 問題概要 凸な 角形が与えられる。この 角形を完全に含むような正三角形の一辺の長さの最小値を求めよ。 制約 考えたこと 座標系として くらいの大きさまであるので、EPS は くらいがいい…

AtCoder ABC 117 D - XXOR (400 点)

以下の典型思考で解けるけど、苦手意識...^^; XOR な問題は各桁ごとに見る の動ける範囲が 以下と指示されているときは、 を上位ビットから見ていったときに、それがどこまで と一致するかを考える (桁 DP でおなじみの考え方) 問題へのリンク 問題概要 個の…

AtCoder AGC 029 C - Lexicographic constraints (700 点)

弱かった。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 文字列の列 であって の文字数が である 辞書式順序で < < < を満たすもののうち、登場文字数の最小値を求めよ。 制約 考えたこと が狭義単調増加だったら、"a" の個数だけで行けるので…

CODE FESTIVAL 2018 qual A E - オレンジとみかん (800 点)

解き切りたかった 問題へのリンク 問題概要 オレンジが 個、みかんが 個ある。これを 人で分け合う ( が の倍数であることは保証される)。 それぞれの人 について、オレンジとみかんそれぞれ 1 個あたりの満足度が で与えられる。 うまく分けて、各人の満足…

AtCoder ABC 104 C - All Green (300 点)

すごく教育的な「bit 全探索 + Greedy」なん!!! 問題へのリンク 問題概要 100 点問題, 200 点問題, 300 点問題, ..., 100× 点問題がそれぞれ 問ずつある。 今、精進して合計で 点以上獲得したい。ただし、100× 点問題を 問すべて解いた場合にはボーナスと…

AtCoder ARC 098 E - Range Minimum Queries (600 点)

ARC 098 E Range Minimum Queries 問題概要 長さ N の数列 A と整数 K が与えられる。 この配列に、以下の操作を Q 回行います。 長さ K の連続する部分列を 1 つ選ぶ。 そして、選んだ部分列に含まれる K 個の要素のうち最小のもの(複数ある場合はその中で…