の計算量までなら比較的すぐできる！ 問題へのリンク 問題概要 街 があって、街 間の行き来には だけの通行料がかかる。 回の市場がそれぞれ街 で行われ、 円えられる。 最初、無限の所持金を持っている。いくつかの市場に参加する (全く参加しなくてもよい)…

SWAG を履修した！ 問題へのリンク 問題概要 一次関数の列を考える。初期状態では空である。以下の 個のクエリを処理せよ。 クエリタイプ 1 ()：一次関数 を列の先頭に挿入する クエリタイプ 2 ()：一次関数 を列の末尾に挿入する クエリタイプ 3：列の先頭…

SWAG を履修した！ 問題へのリンク 問題概要 一次関数の列を考える。初期状態では空である。以下の 個のクエリを処理せよ。 クエリタイプ 1 ()：一次関数 を列の末尾に挿入する クエリタイプ 2：列の先頭の要素を削除する クエリタイプ 3 ()：列を としたと…

全方位木 DP の練習問題！！ が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみ…

2 つの文字列の最長の共通部分文字列 (部分列ではなく) を求める問題！ これ、蟻本の例題にもあるけど、POJ ではなく Yosupo Judge で解けるようになったのは大きい！ なお、Suffix Automation があれば本当に貼るだけみたい。 問題へのリンク 問題概要 2 つ…

タイトル "Lazy Segment Tree" の名の通り、遅延評価セグメント木の練習問題！ 問題へのリンク 問題概要 長さ の 0 と 1 のみからなる数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ()：数列の区間 内の各要素の値につい…

これ実は ACL Practice Contest の K 問題と同じらしい atcoder.jp 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ()：数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ()：数…

遅延評価セグメント木の練習！ 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ()：数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ()：数列の区間 内の要素の総和を 99824435…

二部マッチングの練習問題 問題へのリンク editorial へのリンク 問題概要 二次元平面上に 体の飛行機がある。飛行機 は座標 にいる。各飛行機に対して適切に 8 種類の向き付けをしたい (上・下・左・右・左上・左下・右上・右下)。 具体的には、 秒後におい…

グリッドを市松模様に塗って、「黒色マス」と「白色マス」で二部マッチングするという、超典型問題！ 問題へのリンク 問題概要 のグリッドが与えられます。 各マスは「障害物」が置かれているか、「空」であるかのいずれかです。入力データにおいては、障害…

本当に ACL の convolution をそのまま試してほしいという問題ですね。 問題へのリンク 問題概要 整数列 と、整数列 が与えられる。 によって定義される整数列 を求めよ。 制約 解法 とにかく、ACL のドキュメントにそのままの式が書いてある！ https://atco…

2-SAT は強連結成分分解の典型的な応用例！ 問題へのリンク 問題概要 旗 を数直線上に設置したい。旗 は、座標 または座標 に設置可能である。 ただし、どの 2 つの旗も、その距離が 以上となるようにする必要がある。 本の旗を設置することが可能かどうかを…

Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題！ 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…

セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。 セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります: データ構…