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

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

2019-06-22から1日間の記事一覧

AtCoder ABC 131 E - Friendships (500 点)

順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…

AtCoder ABC 131 D - Megalomania (400 点)

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題!!! 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべて…

AtCoder ABC 131 C - Anti-Division (300 点)

「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では (B 以下の整数のうちの〜を満たすものの個数) から (A-1 以下の整数のうちの〜を満たすものの個数) を引く とすると、すごくやりやすい!!!!! このテクニックは大昔の topcode…

CPSCO 2019 session2 E - Mogu Mogu Gummi (600 点)

二乗の木 DP のいい練習問題!!!!! ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…

AtCoder ABC 130 F - Minimum Bounding Box (600 点)

時刻 に対する面積関数 の最小化問題。 全体で三分探索をするのは嘘。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点は初期位置から出発して秒速 1 の速度で上下左右のいずれかに動いている。 このとき、 点の の値の最小値を求めよ。 制約 考…