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

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

探索順序を工夫して解く

JOIG 春合宿 2023 day2-1 Smartphone (難易度 8)

JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…

AtCoder ARC 026 C - 蛍光灯 (試験管青色)

セグ木上で DP する問題として、人生で最初に解くべき問題と言えるかもしれない! 問題へのリンク 問題概要 個の区間がある。各区間 は、 で重みは である。 これらの区間からいくつか選ぶ方法のうち、 全体を被覆するものについて、最小重みを求めよ。 制約…

AtCoder ABC 323 D - Merge Slime (緑色, 425 点)

素朴なシミュレーションが通るものの、それを正確に実装するのも結構大変 問題へのリンク 問題概要 種類のスライムがいる。 種類目のスライムは、サイズが であり、 体いる。 一般にサイズが であるスライムを 2 体合体させて、新たにサイズが のスライムを …

yukicoder No.2422 regisys?

めっちゃいい Greedy 問題だった!! 問題へのリンク 問題概要 個の商品があり、 番目の商品は、一般客は 円で購入でき、MMA 部員は 円で購入できる。なお、MMA 部員が一般客と比べて得できる商品もあれ得て、損する商品もあり得る。 人がいて、 人目は「一…

AtCoder ABC 267 G - Increasing K Time (橙色, 600 点)

順列を数え上げる系の問題、うまく「個数」を持った天才的な DP をするイメージ 問題へのリンク 問題概要 整数列 が与えられる。 この数列の 通りの順列のうち、 であるような がちょうど 個であるようなものの個数を 998244353 で割ったあまりを求めよ。 制…

AtCoder ARC 050 D - Suffix Concat (試験管橙色)

めっちゃ面白い問題だった! Suffix Array の練習問題。 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 の suffix は空文字列を除いて 個ある。これらの suffix を適切な順序で連結させて 1 つの文字列を作るとき、それが辞書順最…

Educational Codeforces Round 9 C. The Smallest String Concatenation (R1700)

すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…

JOIG 春合宿 2022 day1-1 Relay (難易度 6)

面白かった! ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…

AtCoder ABC 246 C - Coupon (灰色, 300 点)

ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…

JOIG 2021 D - 展覧会 2 (AOJ 0704, 難易度 6)

「競プロ典型 90 問 001 - Yokan Party」とよく似た問題! 問題へのリンク editorial 前提知識 基本的な二分探索 問題概要 枚の絵が一直線上に順に並んでいます。 枚目の絵は座標 の位置にあり、その価値は です。 今これらの絵から 枚の絵を選びます。この…

AtCoder ABC 091 C - 2D Plane 2N Point (ARC 092 C) (水色, 400 点)

とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…

AtCoder ABC 187 D - Choose Me (茶色, 400 点)

ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…

AtCoder ABC 137 D - Summer Vacation (水色, 400 点)

これは難しい!!! 誘惑されそうな嘘解法がたくさんある!! 問題へのリンク 問題概要 件の日雇いアルバイトがあります。 件目の日雇いアルバイトを請けて働くと、その 日後に報酬 が得られます。 あなたは、これらの中から 1 日に 1 件まで選んで請け、働…

JOI 本選 2010 C - つらら (AOJ 0551, 難易度 6)

実装をどうしようかを色々悩んでしまう系 ジャッジページ AOJ の問題文 問題概要 本のつららが一列に並んでいる。それぞれ長さは となっている。各つららは以下のルールに従って長さが変わる。 一度でも長さが 0 になったならば、伸びることはない 左右のつ…

Codeforces Round #687 (Div. 1) C. New Game Plus! (R2200)

すごい面白い!! 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…

AtCoder ARC 108 E - Random IS (赤色, 700 点)

変なところでハマらないようにしたい... 問題へのリンク 問題概要 の順列 が与えられる。いま、これらの順列の各要素に印をつけていくことを考える。ただし、「印のついた要素が左から順に単調増加となるように並んでいる」という条件を常に満たす必要がある…

AtCoder AGC 048 B - Bracket Score (青色, 700 点)

めちゃくちゃ面白かった 問題へのリンク 問題概要 この問題では、"(", ")", "[", "]" からなる文字列を考える。 文字列 は,以下のいずれかの条件を満たすとき、良い括弧列と呼ぶ。 は空文字列である ある良い括弧列 が存在し、"(", , ")" をこの順に連結す…

CPSCO2019 Session3 C - Make a Team (300 点設定)

これかなりいい問題だと思う!!! テスターをしていて、最初は 3 人じゃなくて 人だったけど、3 人にしたことでいい感じに 300 点問題になった! 問題へのリンク 問題概要 人がいて、それぞれレーティングは となっている。 人の中から 3 人を選ぶ方法のう…

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

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

AOJ 2333 僕の友達は小さい (JAG 夏合宿 2010 day2-D) (500 点)

これ面白い!! 問題へのリンク editorials 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選ぶ方法のうち、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 選んだ数の総和は 以下である 選んだ数の総…

Codeforces Grakn Forces 2020 G. Clusterization Counting (R2700)

めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…

ACL Contest 1 A - Reachable Towns (水色, 300 点)

えーーー、300 点!? 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…

AOJ 3190 Ribbons on A Perfect Binary Tree (AUPC 2020 day3-F)

こういうのは探索順序を適切に定めることがめっちゃ重要! 問題へのリンク 問題概要 高さ の完全二分木と、 長さが 2 のリボンが 本 長さが 4 のリボンが 本 ... 長さが のリボンが 本 が与えられる。各リボンは、完全二分木において「葉」と「葉」を始点と…

AtCoder ABC 163 E - Active Infants (黄色, 500 点)

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

Codeforces Round #598 (Div. 3) E. Yet Another Division Into Teams (R2200)

DP 復元非本質>< 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とす…

Codeforces CodeCraft-20 (Div. 2) E. Team Building (R2300)

これは楽しい!!! 順番をうまく決めれば、全部の情報を持たなくても、個数のみの情報に落とせる系。 問題へのリンク 問題概要 要素の数列 と、 の二次元数列 が与えられる。 個の の中から 個を選び、 残りの 個の index の中から 個分、 の行ベクトルを選…

Codeforces Round #625 (Div. 1) C. World of Darkraft: Battle for Azathoth (R2000)

セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい! 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…

第6回 ドワンゴからの挑戦状 2020 予選 E - Span Covering (赤色, 1100 点)

すごく面白かった!!!!!!! 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …

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

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

AtCoder ABC 151 E - Max-Min Sums (水色, 500 点)

こういう系の「個別要素に分解して考える」という問題が三連発だ!!!!! これもあれも! drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…