AtCoder600点
分割統治 FFT 面白いね！！ 公式解説がとても丁寧なので、備忘録程度に 問題へのリンク 問題概要 頂点数 のが与えられます。 組の頂点対に対して、次のように無向辺を張っていきます。 組めの頂点対に対しては 長さ 1 の辺が 本 長さ 2 の辺が 本 ... 長さ …
面白かった！！ より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…
コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。 問題へのリンク 問題概要 個の区間が与えられる。 個目の区間は となっている。 Alice と Bob は次のようなゲームを行う。 まだ残っている区間のうち、「今までに選ばれた…
面白かった。リハビリになった。 問題へのリンク 問題概要 長さ の "B", "W", "R" からなる文字列が与えられます。これに対して、次の操作を 回繰り返して、最終的に得られる文字 (1 文字) を答えよ。 それぞれの隣り合う 2 文字に対して それらが同じ文字な…
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
な bit DP としてよく知られている問題ですね！ 問題へのリンク EDPC U - Grouping の類題と言える！ atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…
この問題、実は、北大合宿 HUPC の有志コン枠で原案として挙げていた問題とまったく同じだった！！！！！！ 問題へのリンク 問題概要 の順列 の奇妙さを と定義する。奇妙さが であるような順列の個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこ…
マージテクを知らなくても雰囲気で通せるのかもしれない 問題へのリンク 問題概要 人の生徒がそれぞれクラス に所属している。 各生徒はそれぞれの家から出発したあと、他の生徒と合流を繰り返しながら学校へ向かう。一度合流した生徒が分かれることはない。…
「横移動 + 縦移動」で行けるところをすべて求めるのは簡単だし、「縦移動 + 横移動」で行けるところをすべて求めるのも簡単。しかし、両方の方法で行けるマスの扱いが難しい。 問題へのリンク 問題概要 のグリッドがあり、そのうちの 個のマスは壁になって…
ABC-F が緑色 diff になったのは史上初かな！？！？？？ でもセグ木が緑色はびっくり！！！ 問題へのリンク 問題概要 長さ の非負整数列 がある。これに対して以下の 個のクエリに答えよ。 タイプ 1：整数 が与えられる。 を XOR で置き換えよ。 タイプ 2：…
僕はめっちゃめんどい言い換えをして、めっちゃめんどい場合分けして無理矢理通した... 問題へのリンク 問題概要 二次元平面上の点 (0,0),(1,0),(0,1) に石がひとつずつ置かれています。 3 つの石が次の条件を満たしているとき、くの字に並んでいるといいま…
色んな解法がありそう。 問題へのリンク 問題概要 個の正の整数 が与えられる。 を満たすすべての非負整数列 に対する の総和を 1000000007 で割ったあまりを求めよ。 制約 解法 (1)：経路数への帰着 (僕の解法) 二項係数を扱う方法論として、経路数へと帰着…
こういうの最初は手で様子を掴むようにしているのだけど、どのタイミングで PC 実験開始しようか悩む。 問題へのリンク 問題概要 整数 と 4 つの文字 が与えられる (いずれも "A" または "B") すぬけ君は文字列 を持っている。 ははじめ "AB" である。すぬけ…
まさかの超典型な半分全列挙！！！(蟻本にもほぼ同じ問題あり！！) 問題へのリンク 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選んで総和をとる。その値が より大きくならない範囲内での、その値の最大値を求めよ。 制約 …
簡単なバグを埋め込んでしまった... 問題へのリンク 問題概要 長さ の "0" と "1" のみからなる 2 つの文字列 が与えられる。 に対して以下の操作を繰り返し行うことで に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。 中の "01" …
条件反射で二分探索してしまった！！！この問題めっちゃ面白くて好き！！！ 問題へのリンク editorial 問題概要 平面上に 2 直線 で囲まれた通路がある。この通路の中の の部分に 本の大きさの無視できる釘が打たれており、 本目の釘の座標は である。 高橋…
いろんな DP が考えられそう！ 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て (…
「要素を 1 個ずつ追加していくときに値がどう変化していくか」を観察する方向でずっと考えていて迷走してしまった... 問題へのリンク 問題概要 正の整数 と、 個の整数 が与えられる。 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 解法 個…
結構いろんな考え方のできる問題！ 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 自己ループを持たない すべての頂点の次数が 2 以下である 各連結成分のサイズを並べた…
これ結構好き！ 問題へのリンク 問題概要 それぞれ 枚のコインの入った 枚の袋と、 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。 (コインが入った袋が 1 つ以上存在するとき)：コインが入…
時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…
めっちゃいろんな解法がある！ 各 i に対して i 番目を抜いた部分の解を求める系 左右から累積和 戻す DP 単調性を見抜いて二分探索 問題へのリンク 問題概要 個の整数 がある。これらの整数の部分集合のうち、数の総和が 以上になるものをよい集合と呼びま…
コーナーケースがえぐい！！ 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…
こういうのは包除原理しかない！ 問題へのリンク 問題概要 人の人がいる。 人 の身長は である。以下の条件を満たすように、 組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。 どの人もちょうど一つのペアに含まれる。 どのペアも、…
フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある！ 問題へのリンク 問題概要 下図のような の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。 コマは下方…
中国剰余定理使う問題楽しいよね！ 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を満たす最小の正の整数 を求めよ。 が の倍数である 制約 考えたこと まず、 なので、問題の条件は次と同値になる。 が の倍数である ここで改めて を で置き…
早速遅延セグ木があればできる問題来た！！ AC Library の出番かと思った！！！ 問題へのリンク 問題概要 縦 マス、横 マスのグリッドがあり、はじめグリッドの中央 マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 マスには白い石が 1 個ずつ置いてあ…
こういう重たい実装を確実にこなせるように...なりたい！ 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…
