かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC199 D - RGB Coloring 2

問題はこちら

問題概要

{N}頂点{M}辺の単純無向グラフの各頂点を赤,緑,青で塗り分ける方法で隣接する頂点が異なる色で塗られているようなものは何通りあるか.

{1\leq N \leq 20\\
0 \leq M \leq \frac{N(N-1)}{2}}

問題概要2

グラフ理論っぽく書かれていますが,同じ箱に入れてはいけないようなボールの組がいくつか与えられるので区別できる{N}個のボールを区別できる{3}つの箱にいれる方法の数を求める問題です.

解説

重要な考え方として,複雑な問題をいきなり解くのではなく単純な問題から考えるようにするとうまくいくことがあります.

今回の問題で言うと,{3}色に塗り分ける問題をいきなり解くのではなくて赤と緑の{2}色に塗り分ける問題を考えます.ある頂点を赤で塗ると,その頂点と隣接する頂点は青に塗られます.これを繰り返していくと{1}つの連結成分につき,最初の頂点を赤に塗るか青に塗るかの{2}通りになります.ただし,グラフに奇閉路が存在する場合は{2}色に塗ることはできません.以上から,奇閉路が存在すれば{0}通り,存在しなければ連結成分数を{C}として{2^C}が答えになります.

では,{3}色の場合を考えます.青に塗る頂点を決めれば,残りの頂点を{2}色に塗る問題になります.青に塗る頂点は{O(2^N)}の全探索をすればいいです.計算量は{O( (N+M)2^N)}です.

他にもsubset convolutionを使った解があるらしい(未履修) 勉強しました

別解

結局,頂点を{3}つの独立集合に分ける問題です.全頂点集合を{S}として

{\displaystyle\sum_{R\subseteq S,G\subseteq S\backslash R}f(R)×f(G)×f(S\backslash (R\cup G) )}

が答えです.ここで{f(S)}とは,頂点集合{S}が独立集合なら{1}そうでないなら{0}となる関数です.

このような畳み込みをSubsetConvolutionといい,{O(N^22^N)}で解けることが知られています.参考

SubsetConvolutionを知っていたらそれにしか見えませんね.

提出プログラム

https://atcoder.jp/contests/abc199/submissions/22047215 スパゲッティ
https://atcoder.jp/contests/abc199/submissions/22138032 SubsetConvolution

感想

D問題にしては難しい.考察の沼にハマると抜け出せなさそう.
簡単な問題から考えるのは重要.

AtCoder エイシング プログラミング コンテスト 2020 F - Two Snuke

問題はこちら

問題概要

  • {0\leq s_1 < s_2}
  • {0\leq n_1 < n_2}
  • {0\leq u_1 < u_2}
  • {0\leq k_1 < k_2}
  • {0\leq e_1 < e_2}
  • {s_1+s_2+n_1+n_2+u_1+u_2+k_1+k_2+e_1+e_2\leq N}

を満たす整数{s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2}の組全てについて
{(s_2-s_1)(n_2-n_1)(u_2-u_1)(k_2-k_1)(e_2-e_1)}の総和を求めよ.

{1\leq N \leq 10^9}

解説


形式的冪級数で解きます.{k=s_1+s_2}とすると{1\leq s_2-s_1=k-2s_1}
よって{\displaystyle 0\leq s_1\leq \frac{k-1}{2}}

{\displaystyle f=\sum_{k=0}^{\infty}\sum_{s_1=0}^{\left\lfloor\frac{k-1}{2}\right\rfloor}(k-2s_1)x^k}として{\displaystyle[x^N]\frac{f^5}{1-x}}が答え.

{k}を偶奇{k=2i, k=2i+1}で分けると
{\displaystyle\sum_{k=0}^{\infty}\sum_{s_1=0}^{\left\lfloor\frac{k-1}{2}\right\rfloor}(k-2s_1)x^k\\
\displaystyle =\sum_{i=0}^{\infty}\sum_{s_1=0}^{i-1}(2i-2s_1)x^{2i}+\sum_{i=0}^{\infty}\sum_{s_1=0}^{i}(2i+1-2s_1)x^{2i+1}\\
\displaystyle =\sum_{i=0}^{\infty}i(i+1)x^{2i}+\sum_{i=0}^{\infty}(i+1)^2x^{2i+1}\\
\displaystyle =\frac{2x^2}{(1-x^2)^3}+\frac{x(1+x^2)}{(1-x^2)^3}\\
\displaystyle = \frac{x}{(1-x)^3(1+x)}}

したがって{\displaystyle[x^{N-5}]\frac{1}{(1-x)^{16}(1+x)^5}}

Bostan–Moriのアルゴリズムを用いたり,線形漸化式に直して行列累乗したりすると{O(\log{N})}

ライブラリとか除くと実装はこれだけ

int main() {
    int t;cin >> t;
    while(t--) {
        ll n;cin >> n;
        FormalPowerSeries<MOD,true> f({1});
        for (int i = 0; i < 16; i++) f *= {1,-1};
        for (int i = 0; i < 5; i++) f *= {1,1};
        cout << Bostan_Mori({1},f,n-5) << endl;
    }
    return 0;
}

提出プログラム

https://atcoder.jp/contests/aising2020/submissions/21850352

感想

形式的冪級数おそるべし.

yukicoder No.1478 Simple Sugoroku

問題はこちら

問題概要

{N}マスのマス目がある.以下の操作のうち{1}つを選び,マス{1}からマス{N}まで移動するときの操作回数の最小値を求めよ.

  • 操作{1}:マス{i}にいるときマス{N}に移動する.
  • 操作{2}:ワープマスにいるときランダムにワープマスに移動する.

ワープマスは{M}マスある({B_1,B_2,\cdots,B_M}がワープマス).

{1\leq N \leq 10^9\\
1\leq M\leq \min{(N,10^5)}}

解説


ワープマス以外のマスは操作が決まっているので圧縮します.

{N=6, M=3}のケース赤丸がワープマス.矢印が操作回数.
最左のワープマスより左のマスと最右のワープマスより右のマスの操作回数はあとでまとめて足します.
f:id:kanpurin:20210416224351p:plain

{dp[i]}を「マス{B_i}からマス{B_M}に移動するまでの最小の操作回数の期待値」とすると遷移の式は以下の様になります.

  • {dp[M]=0}
  • {\displaystyle dp[i]=\min{(dp[i+1]+B_{i+1}-B_{i},\frac{\sum_{k=1}^{M}dp[k]}{M}+1)}}

このままでは遷移がループしてるので,ある{X}を決めて

  • {dp[M]=0}
  • {\displaystyle dp[i]=\min{(dp[i+1]+B_{i+1}-B_{i},X+1)}}

を計算したときの{\displaystyle\frac{\sum_{k=1}^{M}dp[k]}{M}} (上の式により計算された値)が{X}より大きいなら真の{\displaystyle\frac{\sum_{k=1}^{M}dp[k]}{M}}の値は{X}より大きくなります.小さい場合も同様なので二分探索すればいいです.

二分探索の回数は適当に見積もって{\displaystyle 10^9×\frac{1}{2^n}\leq 10^{-4}}を満たせばいいので{50}回くらいすればいいです.

提出プログラム

https://yukicoder.me/submissions/648918

感想

この問題はすぐ解けたけど期待値問題苦手なので解説書きました.

GCJ 2021 Round 1A Prime Time

問題はこちら

問題概要

素数が書かれたカードが複数ある.そのカードを{A}のカードに書かれた数の総和と{B}のカードに書かれた数の総積が等しくなるように2つのグループ{A,B}に分けたとき,{A}の総和({B}の総積)として考えられる最大の値を求めよ.

入力

  • 素数{P}{2\leq P \leq 499}
  • 素数{P_i}{N_i}個ある.
  • 与えられる素数の数{M\leq 95}
  • {2\leq \sum_{i}N_i \leq 10} (Test Set 1)
  • {2\leq \sum_{i}N_i \leq 100} (Test Set 2)
  • {2\leq \sum_{i}N_i \leq 10^{15}} (Test Set 3)

解説


以下{A}の総和({B}の総積)を{K}とする.

Test Set 1は{A}にいれる数をDFSとかで全探索でできるのはすぐわかる.

Test Set 2はそうもいかないが,カードの総和は{100×500}以下であることに注目すると,{K}を決めると素因数分解の一意性から{A,B}に分けられるかの判定ができる.Osa_kとかで素因数分解すれば高速に解ける.

Test Set 3はカードの総和が大きくなるので工夫がいる.{B}に入るカードの数が少ないことから,{B}の総積ではなく総和を探索する.{B}の総和を決めると{K}がきまるのでTest Set 2と同様に解ける.{B}の総和は{10000}もないので高速.

提出プログラム

感想

全探索じゃなくずっとDPで考えてたのが敗因

ABC198 F - Cube

そもそも回転の列挙が難しい.

以下,厳密性を欠くので注意.

問題はこちら

問題概要

正六面体の{6}つの面に正整数を書き込んだとき,正整数の和が{S}となるような物の数を求めよ.ただし,正六面体を回転して一致する書き込み方は区別しない.

{6\leq S \leq 10^{18}}

解説


和が{S}となるようなものはまだしも,回転一致を区別しないのは難しそう.回転一致を除去した数え上げは蟻本とかに書いてあったように「ポリアの数え上げ定理」とか言うのを用いればよさそう.

以下の資料がわかりやすかったので参考にしました.

http://dopal.cs.uec.ac.jp/okamotoy/lect/2014/dme/lect07.pdf

回転して一致するものを区別しない場合の書き込み方の数は「回転の仕方」それぞれの「その回転で変化しないような書き込み方の数」の総和を「回転の仕方」の数で割ったものとなる(コーシー・フロベニウスの定理[バーンサイド補題]).

「回転の仕方」をすべて見つける必要がある.まず適当に思いつく回転を列挙してみて,それらの回転を何回か行ったものすべて「回転の仕方」の一つとなっている.

例として正六面体(立方体)の回転を考える.

f:id:kanpurin:20210414232421p:plain:w150

例えば,{1}の方向と{2}の方向の回転のみで{3}の方向の回転が行える.このようにして正六面体の回転は{1}の方向と{2}の方向の回転ですべての回転を表せる.({+}恒等変換も回転と考える)

結局,「回転の仕方」が分からない場合は次のようにする.
①思いつく回転を列挙する.
②列挙した回転から他の回転を求める.「回転の仕方」の数は有限なのでちゃんと止まる(有限じゃないならそもそもこの方針じゃ解けない).

これが面倒な時は「回転の仕方」の数は上の資料{14}枚目のスライドに書かれてるようなやり方で求められるので,地道に見つけていけばいい.

「回転の仕方」が見つけられた後は,「その回転で変化しないような書き込み方の数」を見つける必要がある.
例えば,上の図の{1}の方向への{90}度回転では{4}つの面に書き込まれた数が同じで他2つはなんでもいいので{a+b+4c=S}となる非負整数{a,b,c}の組の数を求める必要がある.

{[x^S] (x+x^2+x^3+\cdots)(x+x^2+x^3+\cdots)(x^4+x^8+x^{12}+\cdots)\\
\displaystyle=[x^S] \frac{x}{1-x}\cdot\frac{x}{1-x}\cdot\frac{x^4}{1-x^4}=[x^{S-6}] \frac{1}{(1-x)^2(1-x^4)}}

Bostan–Moriのアルゴリズムを用いたり,線形漸化式に直して行列累乗したりすると{O(\log{S})}

  • 高校数学で解く

{a+b+4c=S}

{c}を決めると高校数学でよく見るアレになる.

{\displaystyle \sum_{c=1}^{\left\lfloor\frac{S-2}{4}\right\rfloor}S-4c-1=\left\lfloor\frac{S-2}{4}\right\rfloor(S-2\left\lfloor\frac{S-2}{4}\right\rfloor -3)}

全部の回転がこんな感じになるので{O(1)}

提出プログラム

https://atcoder.jp/contests/abc198/submissions/21762228

感想

新しい知識を得るのは楽しい.

ABC198 C - Compass Walking

問題はこちら

問題概要

{1}歩でちょうど距離{R}歩けるとき,原点から{(X,Y)}まで最短何歩で行けるか.

{1\leq R \leq 10^5\\
0\leq X,Y\leq 10^5}

解説


{D^2=X^2+Y^2}とします.

{K}歩歩くとすると{KR < D}なら到達できないことがわかりますが,{KR \geq D}なら到達できるでしょうか?

到達できそうですが{D < R}のときには注意が必要で,図に書いてみるとわかるように{2}歩かかります.

以上から,{D < R}のとき{2}歩,{D \geq R}のとき{\displaystyle K\geq \frac{D}{R}}を満たす最小の{K}が答え.

{K}を求めるのに,{D}が小数のままなのは誤差が怖いので両辺2乗して{\displaystyle K^2\geq \frac{D^2}{R^2}}を満たす最小の{K}を求めます.これは二分探索などを用いると高速に求めることができます.解の上限や判定を適当に決めてしまうとオーバーフローするので注意.

二分探索の実装が面倒なら{K}{1}からいい感じの上限まで全探索する.これもオーバーフローに注意.

雑な上限評価:{\displaystyle\frac{D^2}{R^2}\leq\left\lceil\frac{D^2}{R^2}\right\rceil\leq K^2\leq \left(\left\lceil\frac{D}{R}\right\rceil +1\right)^2\leq 141423^2}

提出プログラム

https://atcoder.jp/contests/abc198/submissions/21700151

感想

今回は小数にビビらずにいってもAC取れる.

yukicoder No.1471 Sort Queries

Mo's algorithmを用いた方法を説明します.

問題はこちら

問題概要

英小文字からなら長さ{N}の文字列{S}について「{L_i}文字目から{R_i}文字目までからなる部分文字列を任意に並べ替えたものの中で辞書順最小である文字列の{X_i}文字目を出力せよ」という{Q}個のクエリに答えよ.

{1\leq N,Q \leq 10^4}

解説


Mo's algorithmについては以下の記事を見てください.
kanpurin.hatenablog.com

  • 更新クエリがない
  • {[l,r)}の答え(状態)から{[l±1,r),[l,r±1)}の答え(状態)が高速に計算できる.
  • オフラインで処理できる.

今回の問題はこれを満たしているのでMo's algorithmが使える.

{[l,r)}の各文字の個数を持っておけばよい.区間の伸縮も{O(1)}で計算できる.計算量はアルファベットサイズを{\sigma}として{O(N\sqrt{Q}+\sigma Q)}

個数の保持にBITを用いれば,{O((N\sqrt{Q}+Q)\log{\sigma}+\sigma)}となり,{\sigma\leq 10^5}でも解ける.

提出プログラム

https://yukicoder.me/submissions/647146

感想

Mo's algorithmの復習になる.