drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 unrated公式コン グルーピングの数え上げ問題 数え上げ問題 DP シーケンシャルDP 考察：順序を工夫して解く 箱根駅伝DP 調和級数 二項係数 順序の工夫：選択肢が狭い方から決めていく 小さいところで帳尻を合わせる グルーピング(算数) DP状態削減テク:全部分集合でなく個数のみ持つ 今なら解ける！！！ 問題へのリンク 問題概要 人を何チームかに分けたい (チーム同士は区別しない)。 人目の人は 人以下のチームに入るようにする必要がある。そのようなチームの分け方は何通りあるか、 で割ったあまりを求めよ。 制約 考えたこと もし無制約だったらいわゆるスターリング数っぽい問題！！！ そしてこの手の DP は昔は見えなかったけど、今なら見える！！！ とりあえず を大きい順に並べておく。 このとき、a を大きい順に見て、 人目の所属するグループ人数が のどれになるのかを割り当てていくような問題になる。こういう割り当てっぽい構造をした DP は難しいけど慣れれば見える。 箱根駅伝 D… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2019%2F03%2F28%2F221700" title="MUJIN 2018 F - チーム分け (600 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20N Hatena Blog https://hatena.blog 2019-03-28 22:17:00 rich https://drken1215.hatenablog.com/entry/2019/03/28/221700 1.0 100%