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

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

全部混ぜて解く

AtCoder ABC 355 D - Intersecting Intervals (2Q, 茶色, 400 点)

ものすごく教育的な典型問題! 色んな方法が考えられるが、ここでは区間ソートで解いてみる。 問題へのリンク 問題概要 数直線上に 個の区間が与えられる。 番目の区間は である。 これら区間の組であって、共有点をもつ (端点含む) ものの個数を求めよ。 制…

AtCoder ABC 085 D - Katana Thrower (2Q, 緑色, 400 点)

昔ながらの典型考察 Greedy 問題。 問題へのリンク 問題概要 本の刀がある。 刀 を振ると、敵に だけダメージを与える。何度でも振ることができる 刀 を投げると、敵に だけダメージを与える。刀 を失うので、もう投げることも振ることもできなくなる 敵に …

JOIG 2024 C - 座席 2 (難易度 6)

色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…

AtCoder ABC 330 F - Minimize Bounding Square (青色, 525 点)

すごく典型盛り合わせな教育的問題! 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…

yukicoder No.2422 regisys?

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

AtCoder ABC 235 E - MST + 1 (水色, 500 点)

MST の理解が問われる面白い教育的問題! 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き単純無向グラフ が与えられる。なお、各辺の重みはすべて互いに異なることが保証されている。 の最小全域木を とする (一意に定まることが示せる)。 このグ…

CPSCO2019 Session4 D - Boring Sequence (400 点設定)

一目二分探索ゲーだし、実際二分探索で解けるのだけど、実はもっとすごく楽に解ける!! 問題へのリンク 問題概要 長さ の整数列 が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。 与えられた数列において、最大…

CPSCO2019 Session3 G - Grand Election (800 点設定)

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った! 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…

Codeforces CodeCraft-20 (Div. 2) F. Battalion Strength (R2800)

実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…

Chokudai SpeedRun 002 L - 長方形 β (600 点)

面白かった 問題へのリンク 問題概要 個の長方形がある。各辺の長さは整数値である。 この長方形から何個か選んでマトリョーシカを作りたい。最大で何重にできるか? 長方形の縦と横をひっくり返してもよい。 制約 考えたこと もし長方形が縦横ひっくり返す…

AtCoder ABC 106 D - AtCoder Express 2 (水色, 400 点)

いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が何個あるかを…