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

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

数え上げ問題

競プロ典型 90 問 005 - Restricted Digits(★7)

きたまさ法によく似たタイプの DP ダブリング高速化! ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意!!! 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …

AtCoder ABC 213 H - Stroll (赤色, 600 点)

分割統治 FFT 面白いね!! 公式解説がとても丁寧なので、備忘録程度に 問題へのリンク 問題概要 頂点数 のが与えられます。 組の頂点対に対して、次のように無向辺を張っていきます。 組めの頂点対に対しては 長さ 1 の辺が 本 長さ 2 の辺が 本 ... 長さ …

AtCoder ABC 213 G - Connectivity 2 (橙色, 600 点)

面白かった!! より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…

AtCoder TDPC G - 辞書順

いわゆる部分列を扱う DP ですね。経路復元も含んでいて少し難しい問題です。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられます。 の部分列 (連続でなくてもよい) として考えられる文字列をすべて考えたとき、その中で辞書順で 番…

AtCoder ABC 212 H - Nim Counting (橙色, 600 点)

コンテスト中にアダマール変換を思い出せたのはよかった! 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…

AtCoder ABC 206 C - Swappable (灰色, 300 点)

包除原理の一番簡単な場合を試せる問題 問題へのリンク 問題概要 個の整数 が与えられる。以下の条件を満たす整数 の組の個数を求めよ。 制約 考えたこと まず、 という条件がないバージョンを考えてみよう。そのときは単に 個のものから 2 個選ぶ場合の数を…

AtCoder ABC 206 E - Divide Both (青色, 500 点)

約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1):約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…

AtCoder ARC 115 D - Odd Degree (黄色, 600 点)

なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …

AtCoder ARC 115 E - LEQ and NEQ (黄色, 700 点)

間に合わなかった!!!悔しい!!! 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…

AtCoder ABC 077 C - Snuke Festival (ARC 084 C) (緑色, 300 点)

lower_bound の練習に!!! あと、「3 つのものを考えるときは、真ん中を固定して考える」という考え方の典型。 問題へのリンク 問題概要 3 つの数列 (長さ ) が与えられる。各数列から要素 を選ぶ方法のうち、 を満たすものの個数を求めよ。 制約 考えたこ…

TopCoder SRM 452 DIV1 Hard - IncreasingNumber (本番 0 人)

SRM 埋めを始めたいと思う! ところでこの問題、こんなの気付かないよ...!! まあ、Petr と tourist も参加したコンテストで誰も AC してない問題なので...。 問題文へのリンク 問題概要 10 進法表記で最高次数から順に広義単調増加であるような整数を Incr…

Codeforces Round #557 (Div. 1) D. Palindrome XOR (R2400)

面白かった。重み付き Union-Find を使った。 問題へのリンク 問題概要 0 と 1 と ? のみからなる長さ の文字列 が与えられる。先頭の文字が 1 であることが保証されている。 以下の条件を満たす整数の組 () の個数を求めよ。 はともに回文数である (11 や 1…

AtCoder ABC 134 F - Permutation Oddness (橙色, 600 点)

この問題、実は、北大合宿 HUPC の有志コン枠で原案として挙げていた問題とまったく同じだった!!!!!! 問題へのリンク 問題概要 の順列 の奇妙さを と定義する。奇妙さが であるような順列の個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこ…

JOI 予選 2010 E - 通勤経路 (AOJ 0547, 難易度 6)

JOI 難易度 6 の中では難しい方だと思った! 問題へのリンク editorial 問題概要 のグリッドの左下マス から右上マス へと至る最短経路 (上または右にのみ移動可能) のうち、以下の条件を満たすものの個数を 100000 で割ったあまりを求めよ。 曲がってから、…

JOI 春合宿 2007 day2-2 Fermat (難易度 7)

これ FFT を使えば でもできるね。実際は で間に合う。 ジャッジページ 問題文 問題概要 正の素数 と、正の整数 が与えられる。 は 以上 以下の整数 を満たすような の組の個数を求めよ。 制約 は素数 考えたこと まずは次のように集計処理をしよう。このよ…

AtCoder TDPC A - コンテスト

部分和問題とほとんど一緒なのだけど、意外と詰まるかもしれない。 問題へのリンク 問題概要 個の正の整数 の中からいくつか選んで総和をとる。作ることのできる整数が何通りあるか求めよ。 制約 考えたこと この問題とよく似た部分和問題とは次のような問題…

JOI 春合宿 2010 day1-3 Stairs (難易度 6)

区間分割していく DP を普通にやると になる (オレンジの出荷もそう)。それを累積和を用いて高速化する。 ジャッジページへのリンク 問題文へのリンク 類題とか drken1215.hatenablog.com 問題概要 (意訳) 個の正の整数 が与えられる。これらをいくつかの連…

JOI 春合宿 2011 day1-1 Banner (難易度 6)

面白かった。単純にやると なので、そこから計算量オーダーを 1 つ落とすことを考える。 ジャッジページへのリンク 問題文へのリンク 問題概要 のグリッドが与えられる。各マスには 0, 1, 2 のうちのいずれかの値が描かれている。 これらの 個のマスのうちの…

AtCoder ARC 109 E - 1D Reversi Builder (橙色, 700 点)

これを本番間に合わせられたなかったのは辛かった... あと、数え上げパートがあんなにスマートにはできなかった。無限に から落とせなかった... 問題へのリンク 問題概要 黒石さんと白石さんは、一列に並んだ 個のマスからなる盤面を使って遊んでいます。 マ…

AtCoder ABC 185 C - Duodecim Ferra (灰色, 300 点)

二項係数!! オーバーフローがこわくて、漸化式で二項係数求めるやつをやった。でももっと簡単にできた。 問題へのリンク 問題概要 長さ の鉄の棒が東西方向に横たわっています。 この棒を 11 箇所で切断して、12 本に分割します。このとき分割後の各棒の長…

AOJ 3211 Symmetric Nbase Number (OUPC 2020 C)

初手実験に走れたのは割とよかった。そういう戦い方もできるようになってきた。 問題へのリンク editorial 問題概要 正の整数 を 先頭に 0 を含まないように 進数表現したときの各位の数を、小さい位から順に要素とした数列を とする。次のような感じ。 正の…

AOJ 3210 Guriko on Line (OUPC 2020 B)

最初与えられる文字列が高橋くんの手だと勘違いして、サンプル 2 が無限にわからないとなっていました。 clar でお騒がせいたしました...ありがとうございます。 問題へのリンク editorial 問題概要 高橋くんと青木くんがジャンケンを 回行う。青木くんの出…

Codeforces Global Round 12 H1. Multithreading (Easy Version) (R2900)

ぷよぷよみたいに 2 つ揃うと消えるような対象物の数え上げ問題。これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) "B", "W", "?" のみからなる長さ の文字列が与えられる ( は偶数)。"?" に "B", "W" を割り当てる方法のうち、"B…

AtCoder ARC 110 E - Shorten ABC (赤色, 800 点)

コンテスト中に間に合わなかった。あと、僕の考察は XOR の言葉ではなかったけど、よく考えたら XOR と等価だった。 問題へのリンク 問題概要 "A", "B", "C" のみからなる長さ の文字列 が与えられる。この文字列に以下の操作を好きな順序で好きな回数だけ行…

AtCoder ARC 110 D - Binomial Coefficient is Fun (黄色, 600 点)

色んな解法がありそう。 問題へのリンク 問題概要 個の正の整数 が与えられる。 を満たすすべての非負整数列 に対する の総和を 1000000007 で割ったあまりを求めよ。 制約 解法 (1):経路数への帰着 (僕の解法) 二項係数を扱う方法論として、経路数へと帰着…

JOI 春合宿 2007 day3-1 anagram (難易度 6)

桁DPとは違うけど、桁DP的な発想で解けた ジャッジページへのリンク 問題概要 長さ の文字列 が与えられる。 の各文字を並び替えてできる文字列をすべて考えたとき、 はその中で辞書順で何番目の文字列に相当するのかを求めよ。 制約 の文字はすべて英大文字…

JOI 予選 2014 D - 部活のスケジュール表 (AOJ 0595, 難易度 6)

J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それ…

AtCoder ARC 108 D - AB (青色, 600 点)

こういうの最初は手で様子を掴むようにしているのだけど、どのタイミングで PC 実験開始しようか悩む。 問題へのリンク 問題概要 整数 と 4 つの文字 が与えられる (いずれも "A" または "B") すぬけ君は文字列 を持っている。 ははじめ "AB" である。すぬけ…

AtCoder AGC 049 D - Convex Sequence (橙色, 1000 点)

最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった! 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…

AtCoder ABC 183 E - Queen on Grid (水色, 500 点)

三乗の解法はすぐに出てくるので、それを上手に高速化する! 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…