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

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

Greedy

AtCoder ABC 171 F - Strivore (600 点)

実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という!!! 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…

AtCoder ABC 169 E - Count Median (500 点)

未証明でも確信持てる系。でも、こういう風に「作れるものは連続している」というのはたまに見るパターン。そういう問題には「とりうる状態が連結」というタグをつけているので是非に!! drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 を次の…

AtCoder ABC 169 D - Div Game (400 点)

久しぶりに素因数分解する問題が来た!!!!!!!!!!! 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…

AtCoder ABC 140 D - Face Produces Unhappiness (400 点)

ABC では数少ない発想力系。 問題へのリンク 問題概要 L と R から成る 文字の文字列 が与えられる。文字列のスコアは次のようにして決められる。 各 index i について S[ i ] = 'L' ならば、i + 1 >= 0 かつ S[ i - 1 ] = 'L' のときに限り、1 を加算 S[ i …

Codeforces Round #638 (Div. 2) E. Phoenix and Berries (R2400)

本番なんとかブザービートが決まった! 問題へのリンク 問題概要 赤いベリーと青いベリーとがある。 組のビュッフェがあり、それぞれ赤いベリーが 個、青いベリーが 個入っている。 これらをカゴに詰めていきたい。1 つのカゴにはちょうど 個のベリーを入れ…

AtCoder ABC 149 D - Prediction and Restriction (400 点)

ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…

AtCoder ABC 163 E - Active Infants (500 点)

探索順序を上手に決めると、普通の DP になる系!!! EDPC の Zubton なんかもそうやね! 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…

AtCoder ABC 161 E - Yutori (500 点)

発想は AtCoder ABC 125 C - GCD on Blackboard (300 点) AtCoder ARC 074 D - 3N Numbers (500 点) とかに似てる。 問題へのリンク 問題概要 長さ の o と x で構成された文字列 が与えられる。 の index から 個選ぶ方法のうち 選んだ index はすべて o で…

AtCoder ABC 161 D - Lunlun Number (400 点)

この手の DFS、一時期全然見なかったけど、最近復活してきた! 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…

AtCoder ABC 159 E - Dividing Chocolate (500 点)

制約が縦方向の bit 管理を要求している感満載 問題へのリンク 問題概要 のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が 以下になるようにする。 これを実…

AtCoder AGC 043 C - Giant Graph (900 点)

これはマジで天才やと思うやが... いや本当にどこから Grundy 数を導けるのか、わからぬ... 問題へのリンク 問題概要 頂点数 のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数 のカルテシアングラフの独立集合のうち、以下の…

AtCoder Petrozavodsk Contest 001 D - Forest (600 点)

面白かった 問題へのリンク 問題概要 頂点 辺の森が与えられる。各頂点 には、値 が付いている。これにいくつかの辺を追加して、連結にしたい。 頂点 と頂点 とを結ぶのに必要なコストは である すでに辺がある二頂点間は結べない 一度辺を張るのに使用した…

Codeforces Round #618 (Div. 1) C. Water Balance (R2100)

これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…

AtCoder AGC 003 B - Simplified mahjong (400 点)

微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか? ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…

AtCoder AGC 003 E - Sequential operations on Sequence (1400 点)

この頃、数列を繰り返すのが流行ってたのかな 問題へのリンク 問題概要 長さ の恒等数列 () が与えられる。この数列に以下の操作を合計で 回行う。 番目の操作は、パラメータ であらわされ、以下のように行われる。 現在の数列を無限回繰り返した数列の先頭 …

CADDi 2018 E - Negative Doubling (800 点)

こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…

Codeforces Round #617 (Div. 3) F. Berland Beauty

面白かった!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺に対して、以下の条件を満たすように 1 以上 1000000 以下の整数値を割り振りたい。 条件は 個ある 番目の条件は、2 頂点 と整数値 が指定されて、 を結ぶパス上の辺の値の最小値が…

Codeforces Round #617 (Div. 3) E2. String Coloring (hard version)

これと同じでは!? atcoder.jp 問題へのリンク 問題概要 長さ の文字列 が与えられる。 いま、文字列の各 index に色を塗ることを考える。色を塗ったあと、隣接する異なる色をもつ 2 文字を swap することができる。swap した結果得られる文字列がソートさ…

CODE FESTIVAL 2016 qual A E - LRU パズル / LRU Puzzle (1200 点)

D 問題はコーナーケースゲーかと思ったらそうでもなかった。むしろこっちの方が苦しかった。 問題へのリンク 問題概要 要素からなる配列が 個あって、それぞれ最初は で初期化されている。以下の操作を 回終えた段階で、 個の配列が等しい状態とすることが可…

AtCoder ABC 153 F - Silver Fox vs Monster (600 点)

区間加算に対応したデータ構造の出番! 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…

AtCoder ABC 153 C - Fennec vs Monster (300 点)

な場合に注意。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。以下の操作を 回まで行うことができる: 整数を 1 つ選んで、0 にする 操作を行った後の、整数の総和として考えられる最小値を求めよ。 制約 考えたこと 素朴に考えれば、 が大きい順…

CODE FESTIVAL 2016 qual A D - マス目と整数 / Grid and Integers (800 点)

800 点埋めをしていく!!! 問題見て、コーナーケース怖い系かな...と思ったけど、ちゃんと一発で通せてよかった 問題へのリンク 問題概要 行 列のマス目があって、以下の条件を満たすように各マスに整数値を書き込みたい (整数値を とする): どのマスの数…

CODE FESTIVAL 2016 qual A C - 次のアルファベット / Next Letter (400 点)

辞書順最小の教育的例題!!! 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に以下の操作をちょうど 回行う。行った結果得られる文字列の辞書順最小なものを求めよ。 の文字を 1 つ選んで、1 文字進める。ただし 'z' は 'a' になる 制約…

Codeforces Round #609 (Div. 1) A. Long Beautiful Integer (R1700)

こういうのは、いかにシンプルにできるか... 問題へのリンク 問題概要 桁の整数 が与えられる (文字列として)。leading zero はない。整数 が与えられる。 以上の整数 であって の 桁目と 桁目の値は等しい という条件を満たす最小値を求めよ。 制約 考えた…

キーエンス プログラミング コンテスト 2020 E - Bichromization (900 点)

実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…

キーエンス プログラミング コンテスト 2020 B - Robot Arms (200 点)

区間スケジューリング問題そのものだった!!! ...とはいえ 200 点というのは衝撃!!! 問題へのリンク 問題概要 ある工場では、 数直線上に 個のロボットが設置されている。 ロボット は座標 に設置されていて、左右に長さ のアームを伸ばしている。 これ…

Codeforces #613 (Div. 2) F. Classical? (R2800)

勉強になった...けど、これ知らずにできるもんなの!? 問題へのリンク あと、LCM の最小値バージョンもある! drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …

AOJ 2423 コードアートオンライン / Code Art Online

最小包含円と、マッチングの二部構成問題 問題へのリンク 問題概要 個の円 ( と番号付けされている) と、 個の多角形 ( と番号付けされている) とが与えられる。 各円は、中心の座標と半径 各多角形は、各頂点の座標 が与えられる。すべての多角形が、いずれ…

Codeforces #613 (Div. 2) D. Dr. Evil Underscores (R1800)

こういう貪欲に突き進む処理を書くの、実はかなり苦手かもしれない 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。上手に正の整数 を選ぶことで、 XOR XOR ... XOR の値の最大値の最小値を求めよ。 制約 考えたこと 最小値を求めたいということ…

第6回 ドワンゴからの挑戦状 予選 D - Arrangement (800 点)

今回は惨敗したけど次回また頑張りたい!!! 問題へのリンク 問題概要 の順列であって、以下の条件を満たすもののうち、辞書順最小のものを求めよ。存在しない場合は -1 を出力せよ。 の右隣の値は ではない 制約 考えたこと 色々手を動かしてみると、条件…