順列を数え上げる系の問題、うまく「個数」を持った天才的な DP をするイメージ 問題へのリンク 問題概要 整数列 が与えられる。 この数列の 通りの順列のうち、 であるような がちょうど 個であるようなものの個数を 998244353 で割ったあまりを求めよ。 制…

すごく楽しかった。解析的に式で求められるのね。 問題へのリンク 問題概要 個の文字 R、 個の文字 G、 個の文字 B を並べてできる文字列のうち、部分文字列として含まれる RG がちょうど 個であるようなものの個数を 998244353 で割ったあまりを求めよ。 制…

opt さんの得意系って感じだった！ 問題へのリンク 問題概要 一辺の長さが整数 の正 角形がある。 頂点から始めて、周上に距離 1 ごとに黒い石か白い石を置いていく。 石の置き方のうち、各辺上にある白い石の個数が等しくなるようなものの個数を 998244353 …

木 DP のいい感じの練習問題だった！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる (重みは負のこともある)。 この木の辺の部分集合であって、各頂点 に接続する辺の本数が 本以下であるようなものに対して、辺の重みの総和の最大値を求めよ。 …

opt さんの「そのままだと優モジュラ最適化なので、青木君の選ぶ・選ばないをひっくり返せば劣モジュラ最適化。よって最小カットでできる」が賢かった。 競プロで言うところの「燃やす埋める」 問題へのリンク 問題概要 のグリッドがあって、各マス には整数…