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

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

AtCoder625点

AtCoder ABC 354 G - Select Strings (4D, 橙色, 625 点)

Dilworth の定理から、DAG の最小パス被覆!! かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…

AtCoder ABC 326 G - Unlock Achievement (橙色, 625 点)

2 変数劣モジュラ関数の和の最小化を最小カットにするやつ! 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…

AtCoder ABC 314 Ex - Disk and Segments (赤色, 625 点)

本当に三分探索で通るのね! これらの問題を思い出した drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 本の線分がある。この平面上の円盤 (円周と内部を含む) のうち、 本の線分すべてと共有点をもつようなも…

AtCoder ABC 313 G - Redistribution of Piles (橙色, 625 点)

floor sum!!! コンテスト中に思いつけてよかった! 問題へのリンク 問題概要 皿 があって、皿 には 個の石が乗っている。また、空の袋がある。 あなたは以下の 2 種類の操作を好きな順番で 0 回以上何度でも行うことができる。 石が 1 個以上載っている皿…

AtCoder ABC 302 Ex - Ball Collector (橙色, 625 点)

undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…