二項係数
差分更新系の教育的問題かな 問題へのリンク 問題概要 長さ の数列が与えらえる。各 index k に対して、 数列から k 番目の要素を除いたものについて その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず) その 2 つの要素の選び方が等しい という…
答えが 0, 1, 2 の三通りしかないとなれば、mod で絞るのをやりたくなる！ 受験数学では定番のテクニックだ！！！ 問題へのリンク 問題概要 長さ の、1, 2, 3 のみからなる数列が与えられる。この数列に対して、 隣接する要素の差を書き出す という操作を、…
面白かった 問題へのリンク 問題概要 の盤面の各マスを T, M, N, P の四色に塗る方法のうち、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 どの T マスと M マスについても、M マスは T マスから見て strict に右にあるか、s…
DP しなくても間に合うけど、桁 DP 的な考え方が役に立つ！ 問題へのリンク 問題概要 100 桁以下の整数 が与えられる。 以上 以下の整数であって、十進法表記で 0 以外の数値がちょうど 個であるようなものが何個あるのかを求めよ。 制約 の桁数 考えたこと …
すっごく色んな方法がありそう！！！ 問題へのリンク 問題概要 正の整数 が与えられる。, を満たすすべての整数 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと とりあえず二項係数の計算自体は、適切に前処理をしておけば、 で…
座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 [tex \lbrack L_{i}, R_{i} \rbrack] が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制…
こういう系の「個別要素に分解して考える」という問題が三連発だ！！！！！ これもあれも！ drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…
面白かった 問題へのリンク 問題概要 長さ の整数列 が与えられる。 長さ の 0 と 1 からなる文字列 に対して定まる関数 は次のようになっている。 は、次のようにして文字列 を文字列 に一致させるのに必要な最小コストとする。 回目の操作で、 の文字 を選…
これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…
これも会社のバチャでやった！！！ 我今カタラン数を語らんとす 問題へのリンク 問題概要 を 個ずつの 2 組にわける。それぞれの組の値を と とする。 このとき、各 に対して or が与えられて のとき のとき を満たすようなものが何通りあるかを求めよ。 制…
てんぷらたんのこれを思い出した！！！ yukicoder.me 問題へのリンク 問題概要 要素からなる非負整数 であって 要素を大きい順に並べたとき、 番目と 番目とが等しい という条件を満たすものの個数を で割ったあまりを求めよ。 制約 考えたこと まず、 以上 …
木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…
二項係数が吹き荒れる！！！！！！！！！ そして、重複組み合わせに関する理解がすごく問われる問題！！！！！！！ 問題へのリンク 問題概要 個のボールがあって、そのうちの 個が青で、残りの 個が赤である。同じ色のボールは互いに区別できない。 各 に対…
すごく典型的な「二乗の木 DP」！！！！！ そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…
何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…
当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける！！！ というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^; 問題へのリンク 問題概要 個の正の整数値のペア が与えられる。 の値を 109 + 7 で割ったあまりを…
すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…
かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…
スターリング数っぽい数え上げの練習 問題へのリンク 問題概要 組の夫婦がいて、合計で 人がいる。 人をいくつかのグループにわける方法のうち、各グループに夫婦が 組以上いるような場合の数を で割ったあまりを求めよ。 制約 考えたこと ひとまずグループ…
部分点がなければ CE 2 完でも赤パフォ出たのに... それはともかく、この手の包除で絶対に解けるという安定感をもって解けるようになりたい！ 問題へのリンク 問題概要 ラーメンに 種類のトッピングを自由に組み合わせて乗せることができます。トッピングの…
こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…
今なら解ける！！！ 問題へのリンク 問題概要 人を何チームかに分けたい (チーム同士は区別しない)。 人目の人は 人以下のチームに入るようにする必要がある。そのようなチームの分け方は何通りあるか、 で割ったあまりを求めよ。 制約 考えたこと もし無制…
楽しい！！！好き！！！ 問題へのリンク 問題概要 頂点のグラフを作って各頂点に赤黒に色をつけたい。そのような 通りの方法のうち、以下の条件を満たすような方法が何通りあるか で割ったあまりを求めよ。 どの赤い頂点も、なんらかの黒い頂点とつながって…
面白い！！！！！！！！！ 問題へのリンク 問題概要 長さ の整数列 であって、 を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 まずは変数変換 まずは数列 の差分に注目してみることにする。 とする ( とする)。そうすると、条件は () とい…
700 点は絶対落とさないのん！！！ 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間がある。 これ…
これは単に二項係数知っているかを問う感じ...？ この頃と今とでは、多少問題傾向も違う気がする。 問題へのリンク 問題概要 個の数値が与えられる。このうち 個以上 個以下を選ぶときのその平均値の最大値を求めよ。 また最大を達成する選び方が何通りある…
21:01 発の磐越西線 (会津若松 -> 郡山) に乗りながらのコンテスト参戦だった。 元々コンテスト出ないで問題だけ読んで考察だけ楽しむつもりが、この F がスラッと解けたので思わず提出してしまった。この段階ではまだ電波状態が大丈夫だった...のと、やはり…
すごく面白そうだし、これ考えたかった 問題へのリンク 問題概要 × の binary 行列 が与えられる。 行集合の部分集合 通り 列集合の部分集合 通り の組であって、 の各要素のうち、行と列がともに該当する部分集合に含まれるようなものの総和が奇数となって…
経路数に帰着して頑張って二項係数計算するところは面白かった！ そのあとの任意 mod の二項係数処理は、今の AtCoder ではあまり出なさそうかな。 問題へのリンク 問題概要 個の座標 についての以下の値 を積算した値を で割ったあまりを求めよ。 原点から…
このシンプル設定でこの深み...すごい！！！ や は順列や組合せを表すものとする。 問題へのリンク 問題概要 長方形の紙があって、水平方向の切れ線が 箇所、垂直方向の切れ線が 箇所ある。 箇所の切れ線から 箇所選んで順に切って行く 通りの方法それぞれに…
