かんプリンの学習記録

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

ABC207 D - Congruence Points

解説 競技プログラミング ABC

計算量は良くないですがすぐ思いつくので．あと，誤差におびえずに済む．

問題はこちら

問題概要

二次元平面上の頂点集合{S}と{T}が与えられる{|S|=|T|=N}．{S}のすべて頂点{(x_i,y_i)}に対して同様に，原点中心の回転と平行移動を行って{T}と一致させられるか判定せよ．

{1\leq N\leq 100\\ |x_i|,|y_i|\leq 10}

解説

実際に回転とか平行移動をしてしまうと，座標が小数になってしまうので判定が難しそう．

問題は{S}のある点を{T}のある点に対応させることができるか．つまり，点の相対的な位置のみが重要となる．

  • {N=1}のとき，もちろんYes
  • {N=2}のとき，{S,T}の{2}頂点間の距離が一致するときYes，そうでないときNo

以降{3\leq N}のときについて考える．

{S_1,S_2}と対応する{T}の点を全探索する．{S_1}を{T_i}，{S_2}を{T_j}と対応させる({2}頂点間の距離は一致)，{T_k}と{S_3}が対応するためには「{S_1}と{S_3}の距離{=}{T_i}と{T_k}の距離」と「{S_2}と{S_3}の距離{=}{T_j}と{T_k}の距離」が成り立つ必要がある．

f:id:kanpurin:20210626221402p:plain:w300

ただし，この条件が成り立つだけではダメで，例えば以下のような物(上図の{T}を反転させたもの)との区別ができない(以下の例はNo)．

f:id:kanpurin:20210626221740p:plain:w300

区別するためには点がある方向が分かるようなもの(外積など)を調べればよい．これが{S_3}と{T_k}で一致していれば{S_3}と{T_k}は対応することになる．{S}のすべての点に対してのこの値({S_1,S_2}からの距離と，上記の情報をもつ値)の集合と{T}のすべての点に対してのこの値の集合が一致していればYesとなる．すべての{T_i,T_j}について調べるので{O(N^2)}，値の計算に{O(N)}かかる．以下の提出プログラムでは実装をサボってソートして集合の比較しているので{O(N\log N)}余計にかかってるので全体で{O(N^3\log N)}．

補足
なんで頂点の距離だけでいいのかというと，中学数学とかでやった三角形の合同条件，「３組の辺がそれぞれ等しい」ってやつにより，距離が決まると(反転を無視して)位置が決まるから．
行う操作が回転と平行移動だけなので点の相対的な距離が変化しないってのもポイント．

提出プログラム

https://atcoder.jp/contests/abc207/submissions/23782969

感想

解法はすぐ思いつくけど実装でてこずる．

この難度をDに置かれると初心者の人がキツい．このレベルのdiffの崖は許されなさそう．

yukicoder No.555 世界史のレポート

yukicoder 競技プログラミング 解説 典型 グラフ 動的計画法

問題はこちら

問題概要

最初紙に{1}文字書いてある．コピーとペーストを行うことにより，紙に{N}文字以上書いてあるようにしたい．コピーには{C}，ペーストには{V}のコストがかかる．最小でいくらのコストがかかるか．

{2\leq N\leq 50000\\ 1\leq C,V\leq 1000}

解説

連続でコピーする必要はない．「1回のコピーと{k}回のペースト」を複数回行う．{i}文字書かれていたときにこの操作を行うとコスト{C+Vk}で{(k+1)i}文字書かれた状態にできる．{i}文字書かれているというのをグラフ上の頂点{i}に，前述の操作を{i}から{(k+1)i}へコスト{C+Vk}の有向辺に対応させる．{(k+1)i}が{N}を超える場合は{N}とする．辺の数は調和級数を用いて{N\log N}になる．ダイクストラ法を用いて頂点{1}から頂点{N}までのコストの最小値を求めればよい．計算量は{O(N\log^2 N)}となるが，このグラフはDAGなので単純なDPで解ける．計算量は{N\log N}．

提出プログラム

https://yukicoder.me/submissions/669107 ダイクストラ

感想

こんな感じでグラフの最短路問題に落とし込むやつ好き

yukicoder No.612 Move on grid

ABC 典型 解説 競技プログラミング 数え上げ 形式的冪級数

形式的冪級数を用いた解法です．

問題はこちら

問題概要

{3}次元グリッド上の{(0,0,0)}からマンハッタン距離が{1}の格子点に移動することを{T}回繰り返すしたあと{(x,y,z)}にいるとして，{d\leq ax+by+cz\leq e}となる確率に{6^T}をかけた値を求めよ．各格子点への移動確率は{\frac{1}{6}}であるとする．

{1\leq T\leq 500\\ |a|,|b|,|c|\leq 20\\ (a,b,c)\neq (0,0,0)\\ -10000\leq d\leq e\leq 10000}

解説

問題は結局，最初{P=0}として，{S=\{\pm a,\pm b,\pm c\}}のいずれかを{P}に加算することを{T}回繰り返したとき{d\leq P\leq e}になるような{S}の要素の選び方の数が答えとなる．

{f=(x^a+x^{-a}+x^b+x^{-b}+x^c+x^{-c})^T}の{x^d}から{x^e}までの係数の和が答え．負の次数があるので非負の次数に変換する．

{M=\max(|a|,|b|,|c|)}として，{f=(x^{M+a}+x^{M-a}+x^{M+b}+x^{M-b}+x^{M+c}+x^{M-c})^T}の{x^{d+MT}}から{x^{e+MT}}までの係数の和が答えとなる．ここで，{P}は{-MT}未満になることはないので{d\leftarrow\max(d,-MT)}としてよい．計算量は{O(MT\log(MT))}．定数倍重め．

提出プログラム

https://yukicoder.me/submissions/669021

感想

yukicoder No.1554 array_and_me

yukicoder 典型 競技プログラミング 解説

問題はこちら

問題概要

長さ{N}の正整数列{A}が与えられる．{P_i=\frac{A_i}{\sum_{i=1}^{N}A_i}}として{\displaystyle\underset{z_1+z_2+\cdots z_N=K}{\max}\frac{K!}{z_1!z_2!\cdots z_N!}P_1^{z_1}P_2^{z_2}\cdots P_N^{z_N}}を求めよ．

{1\leq N,K\leq 10^5\\ 1\leq A_i\leq 10^3}

解説

{\displaystyle\underset{z_1+z_2+\cdots z_N=K}{\max}\frac{K!}{z_1!z_2!\cdots z_N!}P_1^{z_1}P_2^{z_2}\cdots P_N^{z_N}\\ =\displaystyle\underset{z_1+z_2+\cdots z_N=K}{\max}K!\prod_{i=1}^{N}\frac{P_i^{z_i}}{z_i!}\\ =\displaystyle\underset{z_1+z_2+\cdots z_N=K}{\max}K!\prod_{i=1}^{N}\prod_{j=1}^{z_i}\frac{P_i}{j}}
できるだけ大きな{\displaystyle\frac{P_i}{j}}を使いたい．{\displaystyle\frac{P_i}{j} > \frac{P_i}{j+1}}であるから，貪欲で大丈夫．{\displaystyle\frac{P_i}{x}}と{\displaystyle\frac{P_j}{y}}の比較は{A_i y}と{A_j x}を比較すればよい．もしくは，二分探索でも解ける．

基本的には，https://atcoder.jp/contests/joisc2008/tasks/joisc2008_fractionやhttps://yukicoder.me/problems/no/68やhttps://yukicoder.me/problems/no/210と同じ．

{1\leq k\leq K}を満たす全ての{k}について求めよ，とかでも解けます．

提出プログラム

https://yukicoder.me/submissions/668688

感想

ABC206 E - Divide Both

ABC 典型 数え上げ 競技プログラミング 解説 数論

問題はこちら

問題概要

整数{L,R(L\leq R)}が与えられるので，以下の条件を満たす整数組{(x,y)}の数を求めよ．

  • {L\leq x,y\leq R}
  • {g}を{x,y}の最大公約数とすると，以下が成立する．
    • {g\neq 1}かつ{\frac{x}{g}\neq 1}かつ{\frac{y}{g}\neq 1}

{1\leq L\leq R\leq 10^6}

解説

{x=1}または{y=1}のときは条件を満たさないので，以下{L\leftarrow\max(2,L)}とする．

各{g(2\leq g\leq R)}に対して，条件を満たすような{(x,y)}の数を求める．つまり，{\gcd(x,y)=g}となるような{(x,y)}のうち，{x,y}がともに{g}より大きい{g}の倍数かつであるようなものの数を求めたい．
{\gcd(x,y)=g}となるような{(x,y)}の数は{\displaystyle \sum_{g=2}^{R}\sum_{\gcd(x,y)=g}f(x)f(y)}となる．
ここで，{f(x)}は{L\leq x\leq R}となるなら{1}，そうでないなら{0}となる関数である．これは，{\gcd}による畳み込みとなっているので高速に求めることができる．

この値から{x,y}のどちらかが{g}に等しいような{(x,y)}の数を引く．{x=g}となる{(x,y)}の数は{\displaystyle\sum_{g=L}^{R}\sum_{g|y}f(y)}となるが，これも約数のゼータ変換を用いて高速に計算でき，対称性から{y}についても同じ値となる．ここから引きすぎた{\displaystyle\sum_{g=L}^{R}f(g)=R-L+1}を足せば答えとなる．

{\displaystyle \sum_{g=2}^{R}\sum_{\gcd(x,y)=g}f(x)f(y)-2\sum_{g=L}^{R}\sum_{g|y}f(y)+R-L+1}

以下の記事が参考になる．

{\gcd}による畳み込みやゼータ変換についての記事
qiita.com

提出プログラム

https://atcoder.jp/contests/abc206/submissions/23606820

感想

gcd畳み込みを使う問題たのしい．{g=R}となるようなことはないけど面倒なので入れた．

ABC205 D - Kth Excluded

ABC 競技プログラミング 解説

問題はこちら

問題概要

長さ{N}の正整数列{A}が与えられる．以下の{Q}個のクエリに答えよ．

  • 正整数{K}が与えられる．{A}のいずれとも異なる正整数のうち，小さい方から数えて{K}番目のものを求めよ．

{1\leq N,Q\leq 10^5\\ 1\leq A_1< A_2 < \cdots < A_N \leq 10^{18}\\ 0\leq K_i\leq 10^{18}}

解説

クエリを先読みすることで二分探索を用いずに解きます．

まず，{K_i}を昇順にソートします．{A_i}の昇順に，{A_i}以下の{A}に含まれない正整数の数{S}を管理します．例えば，{A=(3,5,6,7)}だと{S}は順に{2\rightarrow 3\rightarrow 3\rightarrow 3}となっていきます．
{K_i\leq S}となるとき，{K_i}番目の正整数はその地点より左側に存在することになるので処理を行うことができます．例として，{A=(3,5,6,7),K=(2,3)}だと，{S=2}となる時点で{K_1\leq S}となっているので{K=2}は{0}と{A_1}の間(両端は含まない)にあることが分かり，{S=3}となる時点では{K_2\leq S}となっているので{K=3}は{A_1}と{A_2}の間にあることが分かります．
実装では{A_0=0}とした方が楽です．詳しくは以下のプログラムを参照してください．計算量は{O(N+Q\log{Q})}となります．

提出プログラム

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

int main() {
    int n,q;cin >> n >> q;
    vector<ll> a(n),k(q),ans(q);
    vector<int> id(q); // id[i]:=昇順i番目のクエリの番号
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> k[i];
    iota(id.begin(), id.end(),0);
    sort(id.begin(), id.end(),[&](int a,int b){return k[a]<k[b];});
    int t = 0;
    ll sum = 0,pre = 0;// sum:Aにない正整数の数 pre:ひとつ前のA_i
    for (int i = 0; i < n; i++) {
        // K <= S となるKをすべて処理
        while(t < q && k[id[t]] <= sum+a[i]-pre-1) {
            ans[id[t]] = k[id[t]]-sum+pre;
            t++;
        }
        // 値の更新
        sum += a[i]-pre-1;
        pre = a[i];
    }
    for (int i = t; i < q; i++) ans[id[i]] = k[id[i]]-sum+pre;
    for (int i = 0; i < q; i++) cout << ans[i] << endl;
    return 0;
}

感想

ABC205 E - White and Black Balls

ABC 数え上げ 競技プログラミング 解説

問題はこちら

問題概要

白いボール{N}個と黒いボール{M}個を一列に並べるとき，各{i(1\leq i\leq N+M)}について左から{i}個のボールのうち白いものの個数を{w_i}，黒いものの個数を{b_i}とおいたとき，すべての{i}について{w_i\leq b_i +K}が成り立つような並べ方の数を求めよ．

{1\leq N,M\leq 10^6\\ 1\leq N+M\\ 0\leq K\leq N}

解説

結局問題は，左からボールを，白のボールの数が黒のボールの数{+K}より大きくならないように置いていく方法の数を数える必要があります．

これは以下のようなグリッド上で左上から右下までの最短経路の数と等しいです．ただし，左に行くというのは白のボールを置くこと，右に行くというのは黒のボールを置くことに対応します．×のところは通れません．

{N=4,M=3,K=2}の例

f:id:kanpurin:20210613222004p:plain:w400

これはかなり難しそうですが，階段状の最短経路についていろいろ調べるとこんなのが出てきます．これを用いると，「青丸から赤丸への最短経路数」から「青丸から緑丸への最短経路数」を引いたものが答えとなります．

f:id:kanpurin:20210613223742p:plain:w400

答えは{\displaystyle\binom{N+M}{N}-\binom{N+M}{N-K-1}}．ただし，{N>M+K}ならそもそも到達できないので{0}

kanpurin.hatenablog.com

提出プログラム

https://atcoder.jp/contests/abc205/submissions/23442405

感想

検索なしだと思いつかなかった．実際はカタラン数っぽかったのでカタラン数で検索してたら導出見つけました．