均等に分ける
自明な上界を達成できるパターンだった！ 問題へのリンク 問題概要 長さ の非負整数列 が与えられる。この数列はどの隣接する二項も値が異なる。 この数列をなるべく多くの 項の非負整数列へと分解せよ。分解とは 分解された各非負整数列の各項を足すと、も…
最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…
好き 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような 個の正の整数 の組合せをすべて考えたとき、 の最大公約数として考えられる最大値を求めよ。 考えたこと を素因数分解して、各素因子たちを に振り分けることを考える。 このとき、各…
これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…
かなり悩んだ 問題へのリンク 問題概要 (ARC 100 D / ABC 102 D) 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だ…
いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たいのん。こういうのを素早く通せるようになりたいん。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷…
slack 勉強会で 600 点の DP として話題になってやってみたん。 DP 自体は素朴だけど、計算量解析含めると 700 点でもいい気はする。 Grouping 問題へのリンク 問題概要 (ARC 067 E) 人をグループ分けしたい。 人は互いに区別される。 どのグループの人数も …
