という制約がいかにも怪しい！ 問題へのリンク 問題概要 1 以上 20 以下の整数からなる、長さ の数列 が与えられる。 この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。 …

が小さいことがいかにも怪しかったので、グラフを小さくすることを考えた。 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフがある。 辺 () は、頂点 から頂点 を結ぶ ( は 0 とする) 辺 () は、頂点 から頂点 を結ぶ このグラフ上の、頂点 0 を始点と…

苦手系の問題だけど、解けてよかった。 問題へのリンク 問題概要 正の整数 が与えられる。はじめ空である集合 が与えられるので、次のクエリに答えよ。 クエリタイプ 1 x：集合 に整数値 がない場合は挿入し、ある場合は削除する クエリタイプ 2 x：集合 に…

LIS の応用問題。LIS を分かっていれば、その DP の過程を保存しておくことで、この問題が解けることがわかる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、要素 を含むような数列 の LIS が存在するかどうかを判定せよ。 (マルチテ…

面白かった。JOI でもありそうな問題。長方形を 3 枚並べるのは典型らしい。 問題へのリンク 問題概要 のグリッドがあって、各マス には数値 が描かれている。 このグリッド上で の正方形を重ならないように 3 枚並べるとき、これらの正方形に覆われたマスの…

すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…

重み付き Union-Find そのもの。もしくは、列挙可能 Union-Find 使ってマージテクでも。 問題へのリンク 問題概要 個の整数値 に関する制約条件が 個与えられる。 番目の制約条件では 3 つの整数の組 が与えられ、 という形をしている。ここで、次のクエリに…

怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…

「戻す DP」または「FPS」で！ 問題へのリンク 問題概要 最初、箱は空である。以下の操作を 回行う。各操作後において、以下の値を答えよ。 箱に入っているボールをいくつか選ぶ方法であって、ボールに書かれた数値の総和が となる方法の個数を 998244353 で…

最初、各マスをタスクに見立てて、タスクの依存関係を考える DAG 上で DP できないかなどと考えたけど、うまくいかなかった。普通にグリッドを左から舐めていく DP でよかった！ 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …

DFS をちゃんと分かっているかが問われる！ DFS の動きをシミュレートする問題 問題へのリンク 問題概要 この問題はインタラクティブ問題である。 頂点数 、辺数 の連結かつ単純な無向グラフがある。ただし最初の入力として与えられるのは の値のみである。 …

メビウス関数を用いた約数系包除原理を使いこなそう！ 問題へのリンク 問題概要 (表現改) 文字 '.' と '#' のみからなる長さ の文字列 が与えられる。今、文字 '#' をいくつか '.' に書き換えることによって、文字列 が周期的文字列となるようにしたい。 な…