けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

ABC-Ex

AtCoder ABC 318 Ex - Count Strong Test Cases (橙色, 650 点)

コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…

AtCoder ABC 314 Ex - Disk and Segments (赤色, 625 点)

本当に三分探索で通るのね! これらの問題を思い出した drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 本の線分がある。この平面上の円盤 (円周と内部を含む) のうち、 本の線分すべてと共有点をもつようなも…

AtCoder ABC 302 Ex - Ball Collector (橙色, 625 点)

undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…

AtCoder ABC 303 Ex - Constrained Tree Degree (橙色, 600 点)

プリューファーコード! それを知っていれば FPS 解法は自然。 問題へのリンク 問題概要 以上 以下の整数集合の部分集合 {} が与えられる。 頂点に と番号のついた頂点数 の木であって、各頂点の次数が集合 に含まれているようなものの個数を 998244353 で割…

AtCoder ABC 259 Ex - Yet Another Path Counting (橙色, 600 点)

opt さんとのスペースで解いた! いくつか典型を見落としていたのでメモ!! 問題へのリンク 問題概要 のグリッドがあって、マス には値 が記されている。 いずれかのマスから始めて右または下に隣接するマスへの移動を 0 回以上繰り返すことで得られる経路…

AtCoder ABC 300 Ex - Fibonacci: Revisited (銅色, 600 点)

「TDPC T - フィボナッチ」の亜種とも言える問題ですね。 問題へのリンク 問題概要 () によって定義される数列を考える。 整数 が与えられので、 AND を満たすすべての非負整数 に対する の総和を 998244353 で割った余りを求めよ。 制約 考えたこと この問…

AtCoder ABC 281 Ex - Alchemy (赤色, 600 点)

この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…

AtCoder ABC 280 Ex - Substring Sort (銅色, 600 点)

Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった! 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…

AtCoder ABC 283 Ex - Popcount Sum (橙色, 600 点)

floor sum と聞いて!! 問題へのリンク 問題概要 以上 以下の整数のうち、 で割って 余るものを考える。そのような整数の popcount 値の総和を求めよ。 ( ケース与えられる) 制約 考えたこと TL を見て、floor sum と知った上での考察。 「popcount の総和…

AtCoder ABC 213 H - Stroll (赤色, 600 点)

オンライン分割統治 FFT 面白いね!! 公式解説がとても丁寧なので、備忘録程度に 問題へのリンク 問題概要 頂点数 のが与えられます。 組の頂点対に対して、次のように無向辺を張っていきます。 組めの頂点対に対しては 長さ 1 の辺が 本 長さ 2 の辺が 本 …

AtCoder ABC 212 H - Nim Counting (橙色, 600 点)

コンテスト中にアダマール変換を思い出せたのはよかった! 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…