黄色diff
これは面白かった。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。 について、 である 制約 考えたこと グラフの問題として考えることにした。つまり、0-indexed で表現すると 頂点数 、…
本当に色んな解法がある問題っぽい！！ 問題へのリンク 問題概要 頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。 クエリタイプ 1：頂点 間に辺を結ぶ クエリタイプ 2：頂点 の双方に隣接する頂点がある…
面白かった。JOI でもありそうな問題。長方形を 3 枚並べるのは典型らしい。 問題へのリンク 問題概要 のグリッドがあって、各マス には数値 が描かれている。 このグリッド上で の正方形を重ならないように 3 枚並べるとき、これらの正方形に覆われたマスの…
コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…
備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …
モノグサでバチャやって、なんとか通した！ 問題へのリンク 問題概要 の順列 が与えられる。この順列に対して「2 個の要素を選んで swap する」という操作を実行して、 「順列から誘導される Functional Graph の連結成分の個数が 1 個」 という状態を実現し…
o......f...(.....)... のようなパターンで、(.....) の中身が消せるような場合を最初見落とした。 問題へのリンク 問題概要 長さ の文字列 に対して、次の操作を好きな回数だけ行える。操作後の文字列の長さとして考えられる最小値を求めよ。 が連続する部…
「平均値の最小化」に基づく二分探索 + 最小全域問題 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の重み付き単純無向グラフが与えられる。各辺 は、重みが であり、長さが である。 グラフの辺集合のうち、すべての頂点を連結にするものを考える。そのよ…
少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…
最初 DP で迷走して、期待値の線形性を使って まで来れた。でも、Polynomial Taylor Shift なる解法もあるらしい！ 問題へのリンク 問題概要 個のキャンディがあって、各キャンディの色は正の整数 で表されている。 各 に対して、 個のキャンディから 個のキ…
高速な解法もあるっぽいけど、愚直に解いた。 問題へのリンク 問題概要 一直線上に 個の宝が座標 に配置されている。一方、長さが である 本の棒がある。次の条件を満たす整数 の個数を求めよ。 各 に対して、座標 の点を始点とするように棒を置いたとき、棒…
点素パスのパッキング系の問題、出ないな〜〜と思っていたら出た！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。3 頂点 が指定される。 2 頂点 を端点とする単純パスであって、頂点 を通るものが存在するかどうか判定せよ。 制約 …
二重辺連結成分分解とか low-link とか色々考えたけど、結果的に最後は「ただ DFS 木を作るだけ」になるという、すごく印象的な問題！ 問題へのリンク 問題概要 以上 以下の整数からなるサイズ の 2 つの数列 、 が与えられる。 今、0 と 1 のみからなるサイ…
Z-algorithm や Suffix Array が使える面白い文字列検索問題！ 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たす文字列 の組が何個あるかを答えよ。 はいずれも空文字ではない である 制約 考えたこと この手の問…
すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…
セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…
くしらっちょ君と一緒に解いた！ 実装が辛い。 問題へのリンク 問題概要 頂点数が である凸多角形が与えられる。この凸多角形の面積を とする。 今、凸多角形の隣接しない 2 頂点を結ぶ直線によって凸多角形を 2 つの多角形に分ける。そして、2 つの多角形う…
AND と XOR は、それぞれ「掛け算」と「足し算」に対応するので、行列累乗が使える！ 問題へのリンク 問題概要 個の整数の組 と が与えられる。 数列 は次の漸化式で定義される。 () AND XOR AND XOR ... XOR AND () の値を求めよ。 制約 考えたこと AND は…
すごく楽しかった。解析的に式で求められるのね。 問題へのリンク 問題概要 個の文字 R、 個の文字 G、 個の文字 B を並べてできる文字列のうち、部分文字列として含まれる RG がちょうど 個であるようなものの個数を 998244353 で割ったあまりを求めよ。 制…
opt さんの得意系って感じだった！ 問題へのリンク 問題概要 一辺の長さが整数 の正 角形がある。 頂点から始めて、周上に距離 1 ごとに黒い石か白い石を置いていく。 石の置き方のうち、各辺上にある白い石の個数が等しくなるようなものの個数を 998244353 …
面白かった 問題へのリンク 問題概要 以下の素数のみを素因数に持つ正整数を -smooth number と呼ぶ。 整数 および 、100 以下の素数 が与えられるので、 以下の -smooth number の個数を求めよ。 制約 考えたこと コンテスト中には、愚直 DFS を頑張って通…
レピュニット数を題材とした問題。 問題へのリンク 問題概要 を 個並べた数と、 を 個並べた数の最小公倍数を で割ったあまりを求めよ。 制約 考えたこと を並べた数をレピュニット数とよぶ。数学的に面白い性質が色々ある。 レピュニット数の最大公約数は、…
残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…
めっちゃ面白い問題だった！ 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…
これを機会に SA-IS を整備した！ 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…
原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…
Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。 問題へのリンク 問題概要 個の区間が与えられる。 個目の区間は となっている。 Alice と Bob は次のようなゲームを行う。 まだ残っている区間のうち、「今までに選ばれた…
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
