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

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

数え上げ問題

AtCoder ABC 133 E - Virus Tree 2 (500 点)

木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…

AtCoder ARC 074 E - RGB Sequence (800 点)

わかってる...!わかってるんだ!!!この問題が超ド典型だってことくらい!!!!!!!! でも典型だからって、そんなパッと解けるわけじゃない。すごく苦手なんだこういうの。。。 問題へのリンク 問題概要 マスを RGB の三色で塗り分ける 通りの方法のう…

AtCoder ABC 132 D - Blue and Red Balls (400 点)

二項係数が吹き荒れる!!!!!!!!! そして、重複組み合わせに関する理解がすごく問われる問題!!!!!!! 問題へのリンク 問題概要 個のボールがあって、そのうちの 個が青で、残りの 個が赤である。同じ色のボールは互いに区別できない。 各 に対…

AtCoder ABC 132 F - Small Products (600 点)

こういう風にルートが出てくるの、こどふぉだとよく見るね。 ありがちなのが、長さ の線分を整数長ごとに分割するとき、分割の中に登場する長さの種類は 通りしかないとか、そういう形でよく出てくる。 問題へのリンク 問題概要 整数 が与えれる。 長さ の正…

AtCoder ABC 131 C - Anti-Division (300 点)

「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では (B 以下の整数のうちの〜を満たすものの個数) から (A-1 以下の整数のうちの〜を満たすものの個数) を引く とすると、すごくやりやすい!!!!! このテクニックは大昔の topcode…

AtCoder ABC 130 E - Common Subsequence (500 点)

共通部分列に関する問題!!!!! 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…

AtCoder ARC 101 E - Ribbons on Tree (900 点)

すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…

diverta 2019_2 E - Balanced Piles (800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…

AtCoder ABC 129 E - Sum Equals Xor (500 点)

まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…

AtCoder ABC 129 C - Typical Stairs (300 点)

いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …

AtCoder ARC 062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer (900 点)

大変だった ^^; 問題へのリンク 問題概要 全部で 色の色がある。 下図のような 枚の正方形があって、それぞれ のラベルがついていて、各正方形の四隅にはいずれかの色が塗られている。 枚の中から 6 枚を選んで正方形を作る。ただしどの頂点についても、そこ…

AtCoder AGC 001 E - BBQ Hard (1400 点)

当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける!!! というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^; 問題へのリンク 問題概要 個の正の整数値のペア が与えられる。 の値を 109 + 7 で割ったあまりを…

AtCoder AGC 002 F - Leftmost Ball (1600 点)

すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…

diverta 2019 F - Edge Ordering (1200 点)

こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …

diverta 2019 E - XOR Partitioning (800 点)

時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…

AtCoder AGC E - Go around a Circle (1500 点)

本番これを間に合わせられなかったのが悔しい 問題へのリンク 問題概要 円周を 等分して、それぞれの弧を赤か青に塗る方法のうち、 'R' と 'B' のみからなる長さ の文字列 が与えられて 円周上のどの端点から出発しても弧を順番に左右どちらかに 回たどって…

Codeforces 558 DIV2 C2. Power Transmission (Hard Edition) (R2000)

有理数使った 問題へのリンク 問題概要 二次元平面上に 個の点がある。これらの任意のペアを結んでできり直線たちを考える (異なるペアが同一の直線を生成するときは、一つの直線とみなす)。 これらの直線たちの交点が何点生じるかを求めよ。 制約 考えたこ…

AtCoder ABC 122 D - We Like AGC (400 点)

こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…

Codeforces 553 DIV2 E. Number of Components (R2100)

面白かった。 「全体についての総和についての総和」を「個別の要素についての総和を各要素について総和」とするテク 区間の連結成分の個数は、各隙間に左端が入り込むかを数える という典型テクが詰まった問題。 問題へのリンク 問題概要 要素からなる数列 …

Codeforces 315 DIV1 B. Symmetric and Transitive (R2100)

ベル数の練習に 問題へのリンク 問題概要 (超意訳) 個の区別できる要素から何個か選んで残りを捨てて ( 個以上捨てなければならない)、選んだ要素を何個かのグループに分ける方法が何通りあるか求めよ。 制約 考えたこと 個選ぶとすると選び方は 通りあり、…

Tenka1 2019 F - Banned X (800 点)

かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…

Tenka1 2019 D - Three Colors (600 点)

見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で割…

yukicoder No.140 みんなで旅行

スターリング数っぽい数え上げの練習 問題へのリンク 問題概要 組の夫婦がいて、合計で 人がいる。 人をいくつかのグループにわける方法のうち、各グループに夫婦が 組以上いるような場合の数を で割ったあまりを求めよ。 制約 考えたこと ひとまずグループ…

AtCoder ARC 096 E - Everything on It (900 点)

部分点がなければ CE 2 完でも赤パフォ出たのに... それはともかく、この手の包除で絶対に解けるという安定感をもって解けるようになりたい! 問題へのリンク 問題概要 ラーメンに 種類のトッピングを自由に組み合わせて乗せることができます。トッピングの…

yukicoder No.391 CODING WAR

写像12相の 玉は区別する 箱も区別する 各箱の玉は 1 個以上 という場合の問題!!! 問題へのリンク 問題概要 個の互いに区別できる玉を、 個の互いに区別できる箱に入れる。 ただし、どの箱についても玉が 1 個以上入るようにするな方法が何通りあるか、10…

Codeforces 551 DIV2 F - Serval and Bonus Problem (R2800)

こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…

AtCoder ABC 114 C - 755 (300 点)

現代の AtCoder では少ない、再帰関数を用いると良い感じに書ける全探索問題。 すごく教育的な問題!!!!! 問題へのリンク 問題概要 10 進法表記で各桁の値が 7 と 5 と 3 のみで、かつ 7, 5, 3 がすべて一度以上は登場するような数を「753 数」と呼ぶこ…

エクサウィザーズ 2019 D - Modulo Operations (600 点)

楽しい問題だった!!! 問題へのリンク 問題概要 すぬけ君は黒板と 個の整数からなる集合 を持っています。すぬけ君は黒板に整数 を書いたのち、以下の操作を 回行います。 から要素を 1 つ選んで取り除く。 その後、現在黒板に書かれた数を 、 から取り除…

MUJIN 2018 F - チーム分け (600 点)

今なら解ける!!! 問題へのリンク 問題概要 人を何チームかに分けたい (チーム同士は区別しない)。 人目の人は 人以下のチームに入るようにする必要がある。そのようなチームの分け方は何通りあるか、 で割ったあまりを求めよ。 制約 考えたこと もし無制…

Codeforces #548 Div. 2 D - Steps to One (R2300)

これだった!!! drken1215.hatenablog.com もちろん高速ゼータ変換はいらなくて、愚直な包除原理で間に合う。 問題概要 整数 が与えられる。空の vector があって 以上 以下の整数の中から一様ランダムに 1 つ選び、 それを vector に push する このとき …