NoviSteps2D
極端な場合を考えて考察した！ 問題へのリンク 問題概要 非負整数 (片方は正) が与えられるので、以下の条件を満たすような二次元グリッドを構築せよ（存在しない場合は、そのことを報告せよ）。 グリッドのマス数は 以上 以下 グリッドの各マスは白色または…
という制約がいかにも怪しい！ 問題へのリンク 問題概要 1 以上 20 以下の整数からなる、長さ の数列 が与えられる。 この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。 …
場からカードを手札に入れない方が良い場合があるの、すごい！ あと、局面状態を数値情報にエンコードするかを迷ったけど、エンコードしなくても通った。 問題へのリンク 問題概要 はじめ、高橋君は整数 の書かれた 枚のカードを持っていて、青木君は整数 の…
面白かった！ 交差数に関する問題に帰着される。 問題へのリンク 問題概要 座標平面上に、4 頂点の座標が であるような長方形があり、その長方形の周上または内部に、 とラベルのついた 個の点がある（どの 2 点も相異なる）。 について、同じラベル の 2 点…
方針を立てるのは難しくないけど、とにかく重たい問題だった。 問題へのリンク 問題概要 人 に対して合計 票が集まった。これらの人のうち条件「自分よりも多くの票を集めた人が 人未満」を満たす人が当選となる。 票のうち途中まで開票されて、各人 には 票…
が小さいことがいかにも怪しかったので、グラフを小さくすることを考えた。 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフがある。 辺 () は、頂点 から頂点 を結ぶ ( は 0 とする) 辺 () は、頂点 から頂点 を結ぶ このグラフ上の、頂点 0 を始点と…
シミュレーションと呼ばれるジャンルの中では、最も重たい部類の問題 問題へのリンク 問題概要 1 から までの整数の書かれたカードがこの順に並んでいる。このカード列に以下の 回の操作を行う。 回目の操作は、整数 （）によって表される。操作前のカードの…
資源配分問題などとも呼ばれる、貪欲法が使える問題！ 問題へのリンク 過去によく似た類題を出題したことがある。 drken1215.hatenablog.com 問題概要 正の整数からなる長さ の数列 がある。頂点 をもつ木をすべて考えたときの、 の最小値を求めよ ( は頂点 …
maspy さんの次のツイートがすべて！！ F(cnt,sum) という組と定数加算作用が遅延セグ木にのるというのはよく知られていると思いますが、これは要素に対する (0乗和, 1乗和) と解釈できて、組 (0,1,...,k 乗和) などに一般化できます。今回は要素 (x,y) に対…
この手の累積和高速化は難しい。 問題へのリンク 問題概要 長さ の数列 が与えられる。 この数列をいくつかの区間に分割する方法のうち、 番目の区間に含まれる数列の要素の総和が で割り切れるようなものの個数を 1000000007 で割った余りを求めよ。 制約 …
カタラン数をわかっていればできる！ 問題へのリンク 問題概要 正の整数 が与えられる。黒いボール 個と、白いボール 個を一列に並べる方法のうち、次の条件を満たすものの個数を 1000000007 で割った余りを求めよ。 【条件】 どの についても、列の左から …
LIS の応用問題。LIS を分かっていれば、その DP の過程を保存しておくことで、この問題が解けることがわかる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、要素 を含むような数列 の LIS が存在するかどうかを判定せよ。 (マルチテ…
の計算量までなら比較的すぐできる！ 問題へのリンク 問題概要 街 があって、街 間の行き来には だけの通行料がかかる。 回の市場がそれぞれ街 で行われ、 円えられる。 最初、無限の所持金を持っている。いくつかの市場に参加する (全く参加しなくてもよい)…
SWAG を履修した！ 問題へのリンク 問題概要 一次関数の列を考える。初期状態では空である。以下の 個のクエリを処理せよ。 クエリタイプ 1 ()：一次関数 を列の先頭に挿入する クエリタイプ 2 ()：一次関数 を列の末尾に挿入する クエリタイプ 3：列の先頭…
SWAG を履修した！ 問題へのリンク 問題概要 一次関数の列を考える。初期状態では空である。以下の 個のクエリを処理せよ。 クエリタイプ 1 ()：一次関数 を列の末尾に挿入する クエリタイプ 2：列の先頭の要素を削除する クエリタイプ 3 ()：列を としたと…
全方位木 DP の練習問題！！ が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみ…
セグメント木を用いた DP 高速化！ 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…
JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…
2 つの文字列の最長の共通部分文字列 (部分列ではなく) を求める問題！ これ、蟻本の例題にもあるけど、POJ ではなく Yosupo Judge で解けるようになったのは大きい！ なお、Suffix Automation があれば本当に貼るだけみたい。 問題へのリンク 問題概要 2 つ…
すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…
タイトル "Lazy Segment Tree" の名の通り、遅延評価セグメント木の練習問題！ 問題へのリンク 問題概要 長さ の 0 と 1 のみからなる数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ()：数列の区間 内の各要素の値につい…
これ実は ACL Practice Contest の K 問題と同じらしい atcoder.jp 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ()：数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ()：数…
遅延評価セグメント木の練習！ 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ()：数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ()：数列の区間 内の要素の総和を 99824435…
二部マッチングの練習問題 問題へのリンク editorial へのリンク 問題概要 二次元平面上に 体の飛行機がある。飛行機 は座標 にいる。各飛行機に対して適切に 8 種類の向き付けをしたい (上・下・左・右・左上・左下・右上・右下)。 具体的には、 秒後におい…
遅延セグ木 (区間加算 + 区間 max 取得) を用いた平面走査！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。点 の座標は である。 この 2 次元平面上でサイズが の長方形領域 (右辺と上辺は含まない) を自由に動かしていくとき、この長方形領域に覆…
最大流を流す練習問題 問題へのリンク 問題概要 人の人 がいる。ある人からある人には魔法パワーを渡していくことができる。具体的には、 組について 人 から人 に対して、最大で だけ魔法パワーを渡せる () ということが指定される。また、 人のうち、 人 …
この問題をキッカケに準完全二分木のライブラリを拡充した！ 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。頂点番号は である。各頂点 (> 2) について、親頂点は である。 この根付き木において、頂点 からの距離が であるような頂点の個数を求…
めっちゃいい Greedy 問題だった！！ 問題へのリンク 問題概要 個の商品があり、 番目の商品は、一般客は 円で購入でき、MMA 部員は 円で購入できる。なお、MMA 部員が一般客と比べて得できる商品もあれ得て、損する商品もあり得る。 人がいて、 人目は「一…
Z-algorithm や Suffix Array が使える面白い文字列検索問題！ 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たす文字列 の組が何個あるかを答えよ。 はいずれも空文字ではない である 制約 考えたこと この手の問…
セグ木とか必要なくて、本当に単純な実装で解けるの面白い 問題へのリンク 問題 制約 考えたこと まずは、生成可能であるための分かりやすい特徴付けを考えようと思った。数列の生成手順が、いかにも入れ子構造をしているので、カッコ列を連想した。 カッコ…
