補集合を考える
一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！ その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！ 問題へのリンク 問題概要 頂点数 、辺数 の単…
面白かった！！ より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
包除原理の一番簡単な場合を試せる問題 問題へのリンク 問題概要 個の整数 が与えられる。以下の条件を満たす整数 の組の個数を求めよ。 制約 考えたこと まず、 という条件がないバージョンを考えてみよう。そのときは単に 個のものから 2 個選ぶ場合の数を…
約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1)：約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
むずかしかった！！！ でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった！！ 問題へのリンク 問題概要 整数 が与えられる。 1 以上 以下の整数のうち、 2 以上の整数 を用いて と表せないものはいくつ…
lower_bound の練習に！！！ あと、「3 つのものを考えるときは、真ん中を固定して考える」という考え方の典型。 問題へのリンク 問題概要 3 つの数列 (長さ ) が与えられる。各数列から要素 を選ぶ方法のうち、 を満たすものの個数を求めよ。 制約 考えたこ…
すごく面白かった！ 問題へのリンク editorial スコア: 191.85 / 500.00 問題概要 "I" と "O" のみからなる文字列 が IOI 文字列であるとは、ある正の整数 が存在して = "I" = "O" = "I" が成立することと定義する (1-indexed)。 いま、"I", "O", "?" のみか…
これの応用問題って感じだった！！ drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…
ハニカムつらい 問題へのリンク editorial 問題概要 下図で表されるようなハニカム状のグリッドが与えられる (図は問題文より)。 黒色マスは建物があるマスを表している。赤太線は、「外側」から見て見える外壁を表している。 このような のマップが与えられ…
面白かった！！ 問題へのリンク 問題概要 すぬけくんは長さ の文字列 を持っている。最初、 のすべての文字は 0 である。 すぬけくんは，以下の 2 種類の操作を好きな順序で好きな回数行うことができます． の連続する 文字を選んで，それらをすべて 0 にす…
こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
これ、「重なるものを数える」という風に考えれば、縦方向と横方向を独立に考えれば良いことに気付けるかが結構ポイントっぽい 問題へのリンク 問題概要 整数 が与えられます。 辺の長さが の白い正方形を座標平面の に 4 頂点が重なるように置きます。 次に…
戻す DP を履修して行く！！！ 問題へのリンク 問題概要 個の正の整数 と正の整数 が与えられる。以下の 個のクエリに答えよ。 整数 が与えられる 以下の条件を満たす 0 以上の整数の組 () の個数を 1000000007 で割ったあまりを求めよ 制約 考えたこと この…
むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、…
二項係数を使いこなすっ！！！ 問題へのリンク 問題概要 種類の花束から何個か選ぶ方法のうち、それが 個でも 個でもないようなものが何通りあるかを 1000000007 で割ったあまりを求めよ。 制約 考えたこと 結局、 個のものからいくつか選ぶ方法 ( 通りある)…
落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…
これが青パフォ！！！！！ 時代の進化を感じるところ！！！ 問題へのリンク 問題概要 のマス目が与えられる。左上から右下へ進む最短経路のうち、 下から マス以内、かつ 左から マス以内 の範囲内には来ないようなものの個数を、1000000007 で割ったあまり…
発想は AtCoder ABC 125 C - GCD on Blackboard (300 点) AtCoder ARC 074 D - 3N Numbers (500 点) とかに似てる。 問題へのリンク 問題概要 長さ の o と x で構成された文字列 が与えられる。 の index から 個選ぶ方法のうち 選んだ index はすべて o で…
とても教育的な Union-Find！！！ 問題へのリンク 問題概要 人がいて、 組の友達関係と、 組のブロック関係がある (いずれも双方向的)。 各人について、 直接的な友達関係ではない ブロック関係でもない 友達の友達の...とたどっていくと到着できる ような人…
面白かった 問題へのリンク 問題概要 の盤面の各マスを T, M, N, P の四色に塗る方法のうち、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 どの T マスと M マスについても、M マスは T マスから見て strict に右にあるか、s…
面白かった 問題へのリンク 問題概要 文字列 が good であるとは、 の連続部分文字列であって回文であるような区間をすべてとってきたときに、それらによって が被覆されることをいう。たとえば "aaba" は、"aa" と "aba" によって被覆されるので good であ…
こういう系の「個別要素に分解して考える」という問題が三連発だ！！！！！ これもあれも！ drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…
全方位木 DP の練習も兼ねて 問題へのリンク 問題概要 頂点数 のツリーが与えられる。ツリーの各頂点 に対して、 から出発して全頂点を訪れるまでに通る辺の本数の最小値を求めよ。 制約 解法 1： 全方位木 DP 1 つの根についての答えなら普通の木 DP で求め…
てんぷらたんのこれを思い出した！！！ yukicoder.me 問題へのリンク 問題概要 要素からなる非負整数 であって 要素を大きい順に並べたとき、 番目と 番目とが等しい という条件を満たすものの個数を で割ったあまりを求めよ。 制約 考えたこと まず、 以上 …
ちょっと視点を変える感じ。 「反対側とか補集合とか余事象とか考えてみると解ける」という感じの問題は、300 点あたりからよく出てくる 問題へのリンク 問題概要 人がいてそれぞれ ポイントずつもっている。 これから ラウンドのクイズがあって、 ラウンド…
順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…
操作をいい感じに言い換える感じ 問題へのリンク 問題概要 個の要素 が与えられる。これに対し、以下の操作を好きなだけ行える。 隣り合う 2 要素をともに -1 倍する 操作後の数列の値の和として考えられる最大値を求めよ。 制約 考えたこと こういう「操作…
お 見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で…
