NoviSteps1D
木の直径の問題！ 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は、頂点 と頂点 を結んでおり、長さは である。 いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めよ。 制約 考えたこと もし仮…
包除原理した！ 問題へのリンク 問題概要 1 以上 以下の正整数 であって、ある正整数 と 2 以上の正整数 を用いて と表現できるものはいくつありますか？ 制約 考えたこと まず考えたのは、 は素数のみ考えれば良いということだった。たとえば、 というよう…
久々！ Functional Graph のサイクル検出と DP 問題へのリンク 問題概要 頂点数 の functional graph が与えられる (出次数 1 の有向グラフ)。 このグラフの 2 頂点 からなる順序対 であって、頂点 から頂点 へと至るウォークが存在するものの個数を求めよ (…
面白かった！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 の値を求めよ。 制約 考えたこと まず、 という制約が怪しい！！！ きっと、 として な計算量になるに違いないと思えた。 とりあえず、数列を元のまま考えるのではなく、…
個から 個を選ぶ設定の問題！ 問題へのリンク 問題概要 個の整数値 が与えられる (負値もありうる)。 これらの整数から 個選んで積をとった値の最大値を、1000000007 で割った余りを求めよ。 制約 考えたこと 本質的に、次の 2 パターンに分かれると考えた。…
周期性をうまいこと活用してなんとかする問題！ 問題へのリンク 問題概要 座標平面上で下の図のような白黒模様が与えられる (問題文より)。 左下の頂点が 、右上の頂点が であるような長方形領域内部の黒色部分の面積 (の 2 倍) を求めよ。 制約 考えたこと …
ChatGPT が問題文コピペのみで解けたと話題になった！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。 先手と後手が交互にゲームする。交互にまだ残っているカードのうち、表の値が等しいか、裏の値が等しいような 2 枚のカー…
というコーナーケースにやられた！ 問題へのリンク 問題概要 整数 が与えられる。 を で割った余りの一の位の値を求めよ。 (マルチテストケース) 制約 考えたこと まず最初に考えたのは「全体を で割った世界」で考えれば良いということ。 このことを正当化…
大敗してしまったので自戒を込めて。 問題へのリンク 問題概要 整数 が与えられる。 のグリッドであって、以下の条件を満たすものを構築せよ。 各マスの値は 0 または 1 である 個のマス の値はいずれも 1 である 行和はすべて である 列和はすべて である …
UnionFind を使って、差分更新を頑張る！ UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います！ 問題へのリンク 問題概要 のグリッドがあって…
セグメント木の練習問題です。 クエリタイプ 1, 2 のみなら、ただの RMQ ですね。クエリタイプ 3 は、セグメント木上の二分探索を実行する関数 max_right() が使えます。 問題へのリンク 問題概要 長さ の数列 がある。この数列に対して、以下の 2 種類のク…
重み付き Union-Find そのもの。もしくは、列挙可能 Union-Find 使ってマージテクでも。 問題へのリンク 問題概要 個の整数値 に関する制約条件が 個与えられる。 番目の制約条件では 3 つの整数の組 が与えられ、 という形をしている。ここで、次のクエリに…
DFS をちゃんと分かっているかが問われる！ DFS の動きをシミュレートする問題 問題へのリンク 問題概要 この問題はインタラクティブ問題である。 頂点数 、辺数 の連結かつ単純な無向グラフがある。ただし最初の入力として与えられるのは の値のみである。 …
まさに文字通り、強連結成分分解をしてください、という問題ですね。そしてこの問題は、Yosupo Judge の Strongly Connected Components が元になっているようです。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。 番目の辺は である。このグ…
Floor Sum が AtCoder 標準ライブラリに入ったのはびっくりした。結構マニアックな印象だった。 問題へのリンク 問題概要 この問題は ケース与えられる。整数 が与えられるので、 を求めよ。 制約 考えたこと 等差数列を で割った商の総和を求めたくなること…
気づき系。。。 こういうのを一瞬で思いつける人になりたい。 問題へのリンク 問題概要 長さ の文字列 が与えられる。先手と後手とで交互に 文字列中の文字を一文字選んで消していく、ただし 両端は消せない その文字を消すことで「同じ文字が隣り合っている…
