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

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

主客転倒

AtCoder ABC 338 G - evall (橙色, 600 点)

人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した! 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…

AtCoder ABC 321 G - Electric Circuit (橙色, 600 点)

除原理! 学びの多い問題だった。Subset Convolution の方はちょっと頑張ってこの後復習する。 問題へのリンク 問題概要 頂点番号が であるグラフ がある。最初、辺は 1 本もない。 以上 以下の値からなるサイズ の 2 つの数列 と がある。 今、これら 2 つ…

AtCoder AGC 005 F - Many Easy Problems (銅色, 1900 点)

Polynomial Taylor Shift が使えた! 問題へのリンク 問題概要 頂点数 の木が与えられる。各 に対して、次の問いに答えよ。 頂点から 個の頂点を選ぶ 通りの方法それぞれについて その 個の頂点をすべて含む連結な部分グラフのサイズとして考えられる最小値…

「Polynomial Taylor Shift」に学ぶ畳み込み芸

Polynomial Taylor Shift を履修したので、簡単にまとめてみます。例によって、Yosupo Library Checker の 問題 を通します。 なお、Polynomial Taylor Shift の解法は、単なるライブラリ整備の一環とみなすというよりは、その導出過程をぜひ押さえておきた…

AtCoder AGC 062 B - Split and Insert (橙色, 700 点)

opt さん、とよさんと一緒に解いた。楽しかった! 問題へのリンク 問題概要 数列 に対して、最大 回の操作を繰り返すことで順列 を作りたい。 回目の操作では、値 ( 以上 以下) を選ぶと、コスト がかかる 値 を選んだとき、数列の末尾 を取り出して、順番を…

AtCoder ABC 283 Ex - Popcount Sum (橙色, 600 点)

floor sum と聞いて!! 問題へのリンク 問題概要 以上 以下の整数のうち、 で割って 余るものを考える。そのような整数の popcount 値の総和を求めよ。 ( ケース与えられる) 制約 考えたこと TL を見て、floor sum と知った上での考察。 「popcount の総和…

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

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

AtCoder ABC 186 D - Sum of difference (茶色, 400 点)

いろんな方法が考えられそう! 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…

Codeforces Round #687 (Div. 1) C. New Game Plus! (R2200)

すごい面白い!! 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…

AtCoder AGC 049 A - Erasing Vertices (青色, 400 点)

面白い。ただ初手で強連結成分分解 (SCC) したくなるのが罠すぎる。SCC 自体は考察過程としては悪くなさそうだけど、SCC して DP...と考えると大変。 問題へのリンク 問題概要 頂点の単純有向グラフが与えられる。以下の操作をグラフが空になるまで繰り返す…

yukicoder No.1145 Sums of Powers

形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…

AOJ 2959 Revenge of UMG (HUPC 2019 day2-H)

この問題のテスターをやってた! 今流行の NTT 系問題!!しかも分割統治 + FFT というカッコいいやつ!! 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…

HHKB プログラミングコンテスト 2020 E - Lamps (水色, 500 点)

これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。あるマスは壁 ('#') になっていて、あるマスは通路 ('.') になっている。通路マスが 個あるとして、すべての「通路マスの部分集合」 ( 通りある) に対して、以…

AOJ 3169 Pyramid Graph (HUPC 2020 day1-F)

ゴリ (prd さん) と一緒に出て楽しかったコンテスト。 そして「グラフのサイクル・パスの列挙」に関する問題は北大セットの定番というイメージになってきた。 問題へのリンク 問題概要 下図のような 角錐が与えられる (底面が 角形で "頂点" の頂点番号を 0 …

ACL Contest 1 E - Shuffle Window (橙色, 900 点)

コンテスト中に まで導いておきながら、最後詰めきれなかったのは反省。 問題へのリンク 問題概要 の順列 と、2 以上の整数 が与えられる。 に対して順に以下の操作を行う。 をランダムシャッフルする 回の操作後に得られる順列の転倒数の期待値を、mod 9982…

AOJ 3180 GCDMST (HUPC 2020 day3-I)

中盤枠という感じで作られた 問題へのリンク 問題概要 の番号を振られた 個の頂点があります。 最初、これらを繋ぐ辺はありません。 あなたはいくつかの辺を追加してこのグラフを連結にしたいと思いました。 頂点 と を繋ぐ辺を追加するには のコストがかか…

AtCoder ABC 169 F - Knapsack for All Subsets (青色, 600 点)

どこかでめっちゃ似たのを解いたことあると思ったらコレだった! drken1215.hatenablog.com 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 個の整数 の空でない部分集合 は 通りあるが、そのそれぞれについて、 = の部分集合のう…

AtCoder ABC 159 F - Knapsack for All Segments (青色, 600 点)

ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…

Codeforces CodeCraft-20 (Div. 2) F. Battalion Strength (R2800)

実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…

Codeforces Round #617 (Div. 3) F. Berland Beauty (R2100)

面白かった!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺に対して、以下の条件を満たすように 1 以上 1000000 以下の整数値を割り振りたい。 条件は 個ある 番目の条件は、2 頂点 と整数値 が指定されて、 を結ぶパス上の辺の値の最小値が…

Educational Codeforces Round 74 E. Keyboard Purchase (R2200)

こういうのを素早く処理できるようになりたい 問題へのリンク 問題概要 長さ の 種類の文字からなる文字列 が与えられる。いま、 種類の文字の順列 として考えられる 通りの並びのうち最適なものを求めたい。 順列のスコアは、 上のすべての連続する 2 文字…

AOJ 2630 Dictionary (JAG 夏合宿 2014 day2-B) (550 点)

最初は「え!? i 行目の文字列情報がないと i+1 行目以降のことを考えられなくない?」となってしまって、途方に暮れてしまった 問題へのリンク 問題概要 個の文字列 があって、それぞれいくつかの文字は '?' で隠されている (したのは の例) '?' 全体をア…

Codeforces Round #614 (Div. 1) C. Xenon's Attack on the Gangs (R2300)

面白かった!!!こういうのを確実に通せるようにならないと!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺を のラベルをつける方法のうち、 の値の最大値を求めよ。ただし は、2 頂点 を結ぶパスに含まれる辺の値の集合を考えたときに、そ…

AtCoder ABC 151 E - Max-Min Sums (水色, 500 点)

こういう系の「個別要素に分解して考える」という問題が三連発だ!!!!! これもあれも! drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…

AtCoder ABC 150 E - Change a Little Bit (青色, 500 点)

面白かった 問題へのリンク 問題概要 長さ の整数列 が与えられる。 長さ の 0 と 1 からなる文字列 に対して定まる関数 は次のようになっている。 は、次のようにして文字列 を文字列 に一致させるのに必要な最小コストとする。 回目の操作で、 の文字 を選…

第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes (青色, 600 点)

期待値の線形性的な。 問題へのリンク 問題概要 体のスライムがそれぞれ の位置にいる (これらは単調増加)。 以下の 通りのスライム合体過程それぞれについて、スライムの移動距離の総和を考える。その総和距離の総和を求めよ。1000000007 で割ったあまりで…

AtCoder ABC 143 F - Distinct Numbers (黄色, 600 点)

かなり辛いことを頑張ったけど、本当はすごく明快な問題だった!! 問題へのリンク 問題概要 個の整数 がある。各 に対して、以下の答えを求めよ。 残っている整数から、どの 2 つも互いに異なる 個の整数を選んで抜き取ることを繰り返したい 抜き取れる回数…

AtCoder ABC 127 E - Cell Distance (青色, 500 点)

何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…

AtCoder ABC 129 F - Takahashi's Basics in Education and Learning (橙色, 600 点)

重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…

Codeforces 553 DIV2 E. Number of Components (R2100)

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