二項係数
てんぷらたんのこれを思い出した！！！ yukicoder.me 問題へのリンク 問題概要 要素からなる非負整数 であって 要素を大きい順に並べたとき、 番目と 番目とが等しい という条件を満たすものの個数を で割ったあまりを求めよ。 制約 考えたこと まず、 以上 …
木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…
二項係数が吹き荒れる！！！！！！！！！ そして、重複組み合わせに関する理解がすごく問われる問題！！！！！！！ 問題へのリンク 問題概要 個のボールがあって、そのうちの 個が青で、残りの 個が赤である。同じ色のボールは互いに区別できない。 各 に対…
すごく典型的な「二乗の木 DP」！！！！！ そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…
何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…
当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける！！！ というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^; 問題へのリンク 問題概要 個の正の整数値のペア が与えられる。 の値を 109 + 7 で割ったあまりを…
すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…
かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…
スターリング数っぽい数え上げの練習 問題へのリンク 問題概要 組の夫婦がいて、合計で 人がいる。 人をいくつかのグループにわける方法のうち、各グループに夫婦が 組以上いるような場合の数を で割ったあまりを求めよ。 制約 考えたこと ひとまずグループ…
部分点がなければ CE 2 完でも赤パフォ出たのに... それはともかく、この手の包除で絶対に解けるという安定感をもって解けるようになりたい！ 問題へのリンク 問題概要 ラーメンに 種類のトッピングを自由に組み合わせて乗せることができます。トッピングの…
こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…
今なら解ける！！！ 問題へのリンク 問題概要 人を何チームかに分けたい (チーム同士は区別しない)。 人目の人は 人以下のチームに入るようにする必要がある。そのようなチームの分け方は何通りあるか、 で割ったあまりを求めよ。 制約 考えたこと もし無制…
楽しい！！！好き！！！ 問題へのリンク 問題概要 頂点のグラフを作って各頂点に赤黒に色をつけたい。そのような 通りの方法のうち、以下の条件を満たすような方法が何通りあるか で割ったあまりを求めよ。 どの赤い頂点も、なんらかの黒い頂点とつながって…
面白い！！！！！！！！！ 問題へのリンク 問題概要 長さ の整数列 であって、 を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 まずは変数変換 まずは数列 の差分に注目してみることにする。 とする ( とする)。そうすると、条件は () とい…
700 点は絶対落とさないようにしたい！！！ 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間があ…
これは単に二項係数知っているかを問う感じ...？ この頃と今とでは、多少問題傾向も違う気がする。 問題へのリンク 問題概要 個の数値が与えられる。このうち 個以上 個以下を選ぶときのその平均値の最大値を求めよ。 また最大を達成する選び方が何通りある…
21:01 発の磐越西線 (会津若松 -> 郡山) に乗りながらのコンテスト参戦だった。 元々コンテスト出ないで問題だけ読んで考察だけ楽しむつもりが、この F がスラッと解けたので思わず提出してしまった。この段階ではまだ電波状態が大丈夫だった...のと、やはり…
すごく面白そうだし、これ考えたかった 問題へのリンク 問題概要 × の binary 行列 が与えられる。 行集合の部分集合 通り 列集合の部分集合 通り の組であって、 の各要素のうち、行と列がともに該当する部分集合に含まれるようなものの総和が奇数となって…
経路数に帰着して頑張って二項係数計算するところは面白かった！ そのあとの任意 mod の二項係数処理は、今の AtCoder ではあまり出なさそうかな。 問題へのリンク 問題概要 個の座標 についての以下の値 を積算した値を で割ったあまりを求めよ。 原点から…
このシンプル設定でこの深み...すごい！！！ や は順列や組合せを表すものとする。 問題へのリンク 問題概要 長方形の紙があって、水平方向の切れ線が 箇所、垂直方向の切れ線が 箇所ある。 箇所の切れ線から 箇所選んで順に切って行く 通りの方法それぞれに…
挿入 DP。。。TDPC O - 文字列を複雑にした問題。アイディアはシンプルだけど詳細詰めが重たい。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 が 個 が 個 ... が 個 を合わせた 個の数を並べる方法のうち、どの隣り合う箇所も数値の差が 以上…
これがインフレ！？ABC 110 D - Factorization に瓜二つ 問題へのリンク 問題概要 整数 を 個の整数の積として表す方法が何通りあるかを、1000000007 で割ったあまりを求めよ。 制約 考えたこと ほとんど、ABC 110 D - Factorization と一緒。 だが、マイナ…
素因数分解 & 重複組合せ を勉強できる、すごく教育的問題だった！！！ 問題へのリンク 問題概要 整数 が与えられる。 を満たす整数の組 () が何通りあるか、1000000007 で割った余りで求めよ。 制約 解法 素因数分解っぽいテーマの問題。こういうのは「まず…
いろんな解法がありそうなんな 問題へのリンク 問題概要 整数 が与えられる。各 に対して、 どの に対しても を満たす整数組 の個数を で割った余りを求めよ ( 面サイコロを 個振るという設定)。 制約 解法 1: 漸化式を立ててそれを展開 (本番で通した解法) …
slack 勉強会で 600 点の DP として話題になってやってみたん。 DP 自体は素朴だけど、計算量解析含めると 700 点でもいい気はする。 Grouping 問題へのリンク 問題概要 (ARC 067 E) 人をグループ分けしたい。 人は互いに区別される。 どのグループの人数も …
解けたけどもっとちゃんと整理しないとなん 問題へのリンク 問題概要 N 個の整数 a_1, a_2, ..., a_N が与えられる (0 <= a_i <= 9)。これを並び替えて順につないでできる整数 (leading zero は除く) として考えられるものの総和を 109 + 7 で割った余りで求…
1. 典型的な二項係数の求め方 競プロをしていると、「 mod 」を計算する場面にしばしば出くわします。最近では、 であることが多いですね。 mod の計算方法は、時と場合によって色んな方法が考えられますが、すぐ下で紹介する方法が最も頻繁に使用されていま…
最初迷走したけど、順位表見ると上位陣が 5 分とかで解いていて、「いくらなんでもこの方針で 5 分はない、きっとなにか簡潔な視点があるはず」と思えて思い付けたのがよかった。 問題へのリンク 問題概要 N 個のマスを赤、緑、青、無の 4 色に塗り分ける。 …
SRM 埋めを始めたいと思う！ ところでこの問題、こんなの気付かないよ...！！ まあ、Petr と tourist も参加したコンテストで誰も AC してない問題なので...。 問題文へのリンク 問題概要 10 進法表記で最高次数から順に広義単調増加であるような整数を Incr…
素朴な DP でもできるけど、実はカタラン数！ 問題へのリンク editorials 問題概要 正の整数 が与えられる。以下の条件を満たす数列 (数列のサイズ は 以上の範囲で自由に選んでよい) の個数を求めよ。 各 に対して、 である である たとえば、 のとき、 の …
