ABC-F
人生で初めて「マージテク」を学ぶなら、この問題！！！ 問題へのリンク 問題概要 箱 がある。箱 には最初色 のボールが入っている。以下の 回のクエリに答えよ。 整数 が与えられる 箱 のボールをすべて箱 に移動させる その後、箱 に入っているボールの色…
という制約がいかにも怪しい！ 問題へのリンク 問題概要 1 以上 20 以下の整数からなる、長さ の数列 が与えられる。 この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。 …
場からカードを手札に入れない方が良い場合があるの、すごい！ あと、局面状態を数値情報にエンコードするかを迷ったけど、エンコードしなくても通った。 問題へのリンク 問題概要 はじめ、高橋君は整数 の書かれた 枚のカードを持っていて、青木君は整数 の…
evima さんの別解で解いた。 問題へのリンク 問題概要 頂点数 の単純な木が与えられる。この木に辺を 1 本追加して得られるグラフのうち、次の条件を満たすものの個数を求めよ。 単純グラフである サイクルをちょうど 1 つ含み、そのサイクルに含まれる頂点…
が小さいことがいかにも怪しかったので、グラフを小さくすることを考えた。 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフがある。 辺 () は、頂点 から頂点 を結ぶ ( は 0 とする) 辺 () は、頂点 から頂点 を結ぶ このグラフ上の、頂点 0 を始点と…
包除原理した！ 問題へのリンク 問題概要 1 以上 以下の正整数 であって、ある正整数 と 2 以上の正整数 を用いて と表現できるものはいくつありますか？ 制約 考えたこと まず考えたのは、 は素数のみ考えれば良いということだった。たとえば、 というよう…
平面走査の典型問題だけど、とにかく重くて辛かったのと、コーナーケースになかなか気づけなかった。 問題へのリンク 問題概要 数直線上に 個の区間がある。区間 は である ()。 = 区間 が、与えられた 個の区間のうち何個と交差するか としたときに、 の範…
資源配分問題などとも呼ばれる、貪欲法が使える問題！ 問題へのリンク 過去によく似た類題を出題したことがある。 drken1215.hatenablog.com 問題概要 正の整数からなる長さ の数列 がある。頂点 をもつ木をすべて考えたときの、 の最小値を求めよ ( は頂点 …
maspy さんの次のツイートがすべて！！ F(cnt,sum) という組と定数加算作用が遅延セグ木にのるというのはよく知られていると思いますが、これは要素に対する (0乗和, 1乗和) と解釈できて、組 (0,1,...,k 乗和) などに一般化できます。今回は要素 (x,y) に対…
苦手系の問題だけど、解けてよかった。 問題へのリンク 問題概要 正の整数 が与えられる。はじめ空である集合 が与えられるので、次のクエリに答えよ。 クエリタイプ 1 x：集合 に整数値 がない場合は挿入し、ある場合は削除する クエリタイプ 2 x：集合 に…
LIS の応用問題。LIS を分かっていれば、その DP の過程を保存しておくことで、この問題が解けることがわかる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、要素 を含むような数列 の LIS が存在するかどうかを判定せよ。 (マルチテ…
面白かった。JOI でもありそうな問題。長方形を 3 枚並べるのは典型らしい。 問題へのリンク 問題概要 のグリッドがあって、各マス には数値 が描かれている。 このグリッド上で の正方形を重ならないように 3 枚並べるとき、これらの正方形に覆われたマスの…
すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…
重み付き Union-Find そのもの。もしくは、列挙可能 Union-Find 使ってマージテクでも。 問題へのリンク 問題概要 個の整数値 に関する制約条件が 個与えられる。 番目の制約条件では 3 つの整数の組 が与えられ、 という形をしている。ここで、次のクエリに…
遅延セグ木 (区間加算 + 区間 max 取得) を用いた平面走査！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。点 の座標は である。 この 2 次元平面上でサイズが の長方形領域 (右辺と上辺は含まない) を自由に動かしていくとき、この長方形領域に覆…
実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…
個の区間を、プチ区間たちを用いて、最小コストですべて被覆しようという問題。DP 状態の持ち方を工夫することで計算量を小さくしたい。 問題へのリンク 問題概要 個の区間があって、長さが である。これらすべてを 2 種類の区間で被覆したい。 長さが であ…
とても教育的問題！！ 蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ！！！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。 各辺 には、美しさ と、コスト がついている。 頂点 0 …
怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…
遅延評価セグメント木の練習問題！ 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列 が与えられる。次の 2 種類のクエリに答えよ。 クエリ (1 L R)：文字列 の区間 内における、1 が連続する区間の長さの最大値を答えよ クエリ (2 L R)：文字列 …
「戻す DP」または「FPS」で！ 問題へのリンク 問題概要 最初、箱は空である。以下の操作を 回行う。各操作後において、以下の値を答えよ。 箱に入っているボールをいくつか選ぶ方法であって、ボールに書かれた数値の総和が となる方法の個数を 998244353 で…
少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…
高速な解法もあるっぽいけど、愚直に解いた。 問題へのリンク 問題概要 一直線上に 個の宝が座標 に配置されている。一方、長さが である 本の棒がある。次の条件を満たす整数 の個数を求めよ。 各 に対して、座標 の点を始点とするように棒を置いたとき、棒…
2-SAT の「密」を解消する累積 OR テクを学んだ！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも…
最初、各マスをタスクに見立てて、タスクの依存関係を考える DAG 上で DP できないかなどと考えたけど、うまくいかなかった。普通にグリッドを左から舐めていく DP でよかった！ 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …
次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…
セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…
DFS をちゃんと分かっているかが問われる！ DFS の動きをシミュレートする問題 問題へのリンク 問題概要 この問題はインタラクティブ問題である。 頂点数 、辺数 の連結かつ単純な無向グラフがある。ただし最初の入力として与えられるのは の値のみである。 …
下手を打つと密なグラフになって TLE してしまう！！ スーパーノードを作ることでグラフを sparse にするテク！ 問題へのリンク 問題概要 以上 以下の整数値からなる 個の有限集合 が与えられる。 以下の操作を最小回数繰り返すことによって、「 と をともに…
メビウス関数を用いた約数系包除原理を使いこなそう！ 問題へのリンク 問題概要 (表現改) 文字 '.' と '#' のみからなる長さ の文字列 が与えられる。今、文字 '#' をいくつか '.' に書き換えることによって、文字列 が周期的文字列となるようにしたい。 な…
