2021-12-30

トップページ

メモ

2023-12-17

ABC333 F - Bomb Game 2

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 人の人が一列に並んでいる．先頭の人を ${\frac{1}{2}}$ の確率で列から取り除き， ${\frac{1}{2}}$ の確率で列の末尾に移す．人 ${i}$ が最後の1人になる確率を求めよ．

${2\leq N\leq 3000}$

解説

${i}$ 人の列で先頭から ${j}$ 番目の人が最後に残る確率を ${P_{i,j}}$ とします．
先頭の人がどうなるかで場合分けを行います．

先頭の人が取り除かれるとき： ${1}$ 番目だった人は取り除かれ， ${j}$ 番目だった人は ${j-1}$ 番目になる．
先頭の人が末尾に移されるとき： ${1}$ 番目だった人は ${i}$ 番目になり， ${j}$ 番目だった人は ${j-1}$ 番目になる．

したがって ${P_{i,j}}$ は以下のようになります．

${P_{1,1}=1}$
${P_{i,1}=\frac{1}{2}P_{i,i} (i\geq 2)}$
${P_{i,j}=\frac{1}{2}P_{i-1,j-1}+\frac{1}{2}P_{i,j-1} (i\geq j\geq 2)}$

${P_{i,1}=\frac{1}{2}P_{i,i}}$ のせいで遷移に循環があります．
${x=P_{i,i}}$ と置くと ${P_{i,j}}$ は ${x}$ の一次式 ${ax+b}$ で表すことができるので， ${j}$ の昇順に ${a,b}$ を持ってDPを行うと ${P_{i,i}=x=ax+b}$ となるため， ${x=\frac{b}{1-a}}$ となります．今回の制約では ${(1-a)\bmod 998244353}$ が ${0}$ になることは無いため正しく求めることができます．時間計算量は ${O(N^2)}$ で，空間計算量は ${O(N)}$ です．

提出プログラム

https://atcoder.jp/contests/abc333/submissions/48609390 (見やすさのため空間計算量O(N^2)で書いてます)

感想

2023-12-16

競プロ用のツールを作ってみた

この記事は競プロ Advent Calendar 2023 16日目のために作成されました。

ランダム生成ツール
1. 使い方
グラフ可視化ツール
1. 使い方
2. 開発者募集

ランダム生成ツール

作ったものはこちらです。
https://kanpurin.github.io/RandomGenerator/

使用する場面としては、コンテスト中などで適当なランダムデータが欲しいときなどに自分でランダムケースを作成するのが面倒な場合など？
APIとかはないのでプログラムに組み込んで実験するとかはできません。机上での実験や大きいサイズの入力例などで用いてください。
サーバにデータを送って計算してるわけではないので何度も生成しても大丈夫です。

生成するデータは以下のものになっています。

数列	(下限)以上(上限)以下の整数を一様ランダムに ${N}$ 個生成(重複を許すか指定可能) ${1\leq N\leq 5\times 10^5}$ ${-10^{18}\leq}$ (下限) ${\leq}$ (上限) ${\leq 10^{18}}$
単調増加数列	(下限)以上(上限)以下の整数からなる長さ ${N}$ の単調増加数列を一様ランダムに生成 ${1\leq N\leq 3\times 10^5}$
括弧列	長さ ${2N}$ の括弧列を一様ランダムに生成 ${1\leq N\leq 10^5}$
ラベル付き木	頂点数 ${N}$ のラベル付き木を一様ランダムに生成 ${1\leq N\leq 2\times 10^5}$
単純グラフ	頂点数 ${N}$ 辺数 ${M}$ の単純グラフを一様ランダムに生成 ${1\leq N\leq 2\times 10^5}$ ${0\leq M\leq \min(2\times 10^5,N(N-1)/2)}$
単純連結グラフ	頂点数 ${N}$ 辺数 ${M}$ の単純連結グラフをランダムに生成 ${1\leq N\leq 2\times 10^5}$ ${N-1\leq M\leq \min(2\times 10^5,N(N-1)/2)}$
素数	(下限)以上(上限)以下の素数を一様ランダムに生成 ${2\leq}$ (下限) ${\leq}$ (上限) ${\leq 10^{18}}$

生成手法は以下の記事にまとめています。

kanpurin.hatenablog.com

使い方

"N M"を先頭に付ける：頂点数N、辺数Mを先頭に付けます。競プロでよく見るデータの与えられ方です。
Seed値を設定する：通常は毎回ランダムにデータが生成されますが、これをONにするとSeed値ごとに生成されるデータが決まります。
グラフを描画する：グラフを可視化します。頂点が多いときはONにしないでください。

N, Mに適切な値を入れて生成ボタンを押すと下のtextareaにデータが生成されます。
値が適切でない場合は生成ボタンがクリックできません。
textareaの右上にあるボタンをクリックするとコピーすることもできます。

Mが大きくとも生成を高速に行うため、textareaに表示するデータ量に制限を付けています。
末尾が`...`となっていますが、コピーボタンによりデータ全体をクリップボードにコピーできます。

グラフ可視化ツール

作ったものはこちらです。
https://kanpurin.github.io/GraphVisualizer/

使用する場面としては入力例として与えられたグラフがどのような形なのか見たいとき、可視化されたグラフを編集したいときなど。
グラフ可視化アプリは結構ありますが、図とテキストの相互変換アプリは知らないので作りました。図→テキストはリアルタイムに変換します。

機能としては以下のものがあります。

ネットワークグラフの可視化：テキストデータを可視化します。
ネットワークグラフの編集：可視化したグラフに頂点や辺を追加します。
二次元グラフの可視化：テキストデータを可視化します。
二次元グラフの編集：可視化したグラフに点を追加します。

使い方

詳しくはアプリに説明があるので触ってみたほうが早いです。

分かりづらい機能として「頂点固定」がありますが、描画されたグラフは物理モデルによってプルプルしながらいい感じにの見た目に収束するのですが、頂点を固定することによりその頂点は動かなくなります。
これにより物理モデルの影響を受けない直線のグラフなどが作れるようになります。

二次元グラフの可視化は格子点をクリックすると点が打てるというだけです。

開発者募集

GraphVisualizerは開発者を募集してます。バグや追加したい機能がかなりあるので手伝ってください。
「READMEに従ってローカルでGraphVisualizerを動かすことができる」ならどなたでも構いません。

GitやJavaScriptに関して全然わからないので教えあいながらやっていけると嬉しいです。
参加したい方は何か適当に機能提案やバグ報告などのIssueを立てるか、既にあるIssueにコメントするか、私のTwitterにメッセージ飛ばすか、この記事にコメントするか、この記事のURLをTwitterで投稿して「興味ある/参加したい」など言ってください。

2023-04-30

ABC299 G - Minimum Permutation

ABC データ構造競技プログラミング解説

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${1}$ 以上 ${M}$ 以下の整数からなる長さ ${N}$ の数列 ${A}$ の長さ ${M}$ 部分列であって ${1,…,M}$ が ${1}$ 回ずつ登場するもののうち，辞書順最小のものを答えよ．

${1\leq M\leq N\leq 2\times 10^5}$
${1\leq A_i\leq M}$

解説

辞書順最小と言えば，前から貪欲に置けるもののうち最も小さいものを順に並べていく方法が考えられます．今回の問題もその方針で考えていきます．

以下のサンプルを例に説明していきます．

出来るだけ小さい数字を先頭に選びたいため，まずは答えとなる部分列の先頭の数字が ${A_{10}=1}$ であるかどうかを考えてみます．
すると，以下の図の色付きの数列から答えとなる部分列を選択する必要が出てきますが， ${10,9,6}$ が色付きの部分に含まれていないため ${A_{10}}$ を部分列の先頭として選ぶことはできません．

このように，それを部分列の先頭として選ぶと，条件を満たす部分列を選ぶことができなくなるようなものは選べません．したがって，それを部分列の先頭として選んでも条件を満たす部分列を選ぶことができなくならないようなものの中でもっとも値が小さいものを貪欲に選べば良いです．

ここで， ${1}$ から ${M}$ の整数それぞれに対して一番後ろに出現するものに色を付けます．

先程の考察から， ${A_1}$ から ${A_6}$ までの中から答えの部分列の先頭要素を選ぶことになります(そうでなければ部分列がすべての数を含むことができない)．

ここでは，最小要素の ${3}$ を選び，以降の ${3}$ を選ぶことができなくします．

次の要素は，先程選んだ要素(青)の直後の要素から「まだ選んでない数それぞれに対して一番後ろに出現するもの(橙)」のうち一番先頭にある要素までの中から選びます．

これを繰り返していくことで辞書順最小の部分列を作ることができます．

必要な操作は

「まだ選んでない数それぞれに対して一番後ろに出現するもの」のうち一番先頭にある要素を求める
区間内のまだ使用していない値のうち最小要素を求める
選んだ要素と同じ値をもつ要素を使用不可にする

です．最初の操作はstd::setを用いれば可能，2番目の操作はSegment Treeを用いれば可能，最後の操作はSegment Treeで使用した要素を ${\infty}$ とすればよいです．

提出プログラム

https://atcoder.jp/contests/abc299/submissions/41075676

感想

2023-04-09

yukicoder No.2264 Gear Coloring

yukicoder 典型式変形数え上げ競技プログラミング解説

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

歯車が ${N}$ 個あり，歯車 ${i}$ は ${A_i}$ 枚の歯を持つ．歯車 ${i}$ と歯車 ${i+1}$ が噛み合っている．これらの歯車の歯に ${M}$ 色の色を塗る方法は何通りあるか．ただし，回転によって一致する色の塗り方を同一視する．

${1\leq N\leq 10^3}$
${1\leq M < 998244353}$
${3\leq A_i < 998244353}$
${\operatorname{lcm}(A_1, A_2, \dots, A_N) < 998244353}$

解説

ポリアの数え上げ定理(バーンサイドの補題)より， ${L=\operatorname{lcm}(A_1, A_2, \dots, A_N)}$ として

${\displaystyle\frac{\sum_{d=1}^{L}M^{\sum_{i=1}^{N}\gcd(d,A_i)}}{L}}$
が答えとなります．
${1\leq d\leq L}$ に対して ${\gcd(d,L)}$ が同じとなる ${d}$ は ${\sum_{i=1}^{N}\gcd(d,A_i)}$ が同じ値になるのでまとめることができて，

${\displaystyle\frac{\sum_{d|L}M^{\sum_{i=1}^{N}\gcd(d,A_i)}\times\phi(L/d)}{L}}$

となり，高速に求めることができます．

提出プログラム

https://yukicoder.me/problems/no/2264/submissions

感想

何を使うかは問題文から明らかですが，まとめることに気付くのが難しい？

2023-02-20

ランダム生成まとめ

メモ用なので適当に書く．

1以上M以下の整数からなる長さNの数列
1. 重複あり
2. 重複なし
N個からM個選ぶ組み合わせ
1以上M以下の整数からなる長さNの単調増加数列
総和がMとなる非負整数からなる長さNの数列
括弧列
二分木
ラベル付き木
次数列を持つグラフ
個数上限付き01列
N頂点M辺の連結グラフ
重複上限Kの数列
ラベル無し根付き木
ラベル無し木
N以下の素数
全域木
ライブラリ

1以上M以下の整数からなる長さNの数列

長さ ${N}$ ， ${1\leq A_i\leq M}$ である数列 ${A}$ を一様ランダムに生成する．

重複あり

数列の要素に重複があってもよい場合を考える．
各要素の生成確率を ${\dfrac{1}{M}}$ としてもよい．

重複なし

数列の要素が互いに異なる場合を考える．
前から順にまだ使ってない数を等確率で使う．

N個からM個選ぶ組み合わせ

1以上M以下の整数からなる長さNの数列と同じように選ぶ，順番は無視．

1以上M以下の整数からなる長さNの単調増加数列

N個からM個選ぶ組み合わせと同じ．

総和がMとなる非負整数からなる長さNの数列

${M}$ 個の"〇"と ${N-1}$ 個の"|"を並べるやつ．
${N+M-1}$ 個の"〇"から"|"にする ${N-1}$ 個を選ぶと考えるとN個からM個選ぶ組み合わせと同じ．

括弧列

バランスのとれた括弧列の一様ランダムな生成．いわゆる構成比法で生成する．

括弧列は，以下の図の右下から左上への経路と対応するため経路をランダムに生成することを考える．

毎回，上か右を選択して移動するが，どのような確率で選択すればよいか．
それは，「上に行った場合の残りの経路数」と「右に行った場合の残りの経路数」の比率で遷移の確率が決まる．

これを用いて，上を選択する確率を求めると，

${\dfrac{(N-M)(N+1)}{(N-M+1)(N+M)}}$

となる．ただし， ${N}$ は現在地から右上の点までの上方向の遷移回数で， ${M}$ は現在地から右上の点までの右方向の遷移回数．

初期値は，長さ ${2n}$ の括弧列を生成するとして， ${N=n,M=n}$ であり，
上を選ぶと ${N\leftarrow N-1}$ ，右を選ぶと ${M\leftarrow M-1}$ となる．

二分木

括弧列を ${(X)Y}$ として再帰させれば1対1対応が取れる．

ラベル付き木

prufer列と対応が取れるので1以上M以下の整数からなる長さNの数列を使う．

次数列を持つグラフ

与えられた次数列を持つグラフを一様ランダムに生成する．
Fast uniform generation of random graphs with given degree sequences

個数上限付き01列

${0}$ の数が ${A}$ 個以下， ${1}$ の数が ${B}$ 個以下の長さ ${N}$ の01列をできるだけ一様なランダム生成する．また，以下の条件を満たす．

${N\leq A+B}$
${0\leq A,B\leq N}$

${0}$ の個数を ${x(N-B\leq x\leq A)}$ と決めるとN個からM個選ぶ組み合わせとして生成できる．

${0}$ の個数が ${x}$ となる確率は，

${\displaystyle\frac{\binom{N}{x}}{\sum_{i=N-B}^{A}\binom{N}{i}}}$
となる．

${N}$ が小さければそのまま， ${N}$ が大きければラプラスの定理を用いることで計算できる．
境界は ${50}$ とかでいいかも．

N頂点M辺の連結グラフ

すぐに思いつく方法として， ${N}$ 頂点の木をランダム生成した後，辺の数が ${M}$ になるまでランダムに辺を追加するというものがある．しかしこれだと，全域木の数に無視できないほどの差があるため一様ランダムな生成とは言えない．

${N}$ 頂点 ${M}$ 辺の連結グラフを生成する方法はいくつかある．

生成検査法

${\binom{n}{2}}$ の辺から ${M}$ 本選んでグラフを作る．作ったグラフが連結なら終了．そうでなければまた生成を行う．

この方法は一様ランダムに生成できるが， ${N}$ と ${M}$ が近い場合，連結となる確率が低いため生成回数が増大する恐れがある．

全域木法

${N}$ 頂点の木を生成する[ラベル付き木の生成]．この木に ${M-N+1}$ 本の辺を追加する．

この方法は高速に生成できるが，一様ランダムにはならない．

構成比法

特定の性質を持つグラフの数に応じた確率を用いることで，比較的速く(それでもまだ遅い)，一様ランダムに生成できる．

構成比近似法

構成比法では構成比の計算に時間がかかっていた．構成比近似法では構成比の近似値を用いることで高速な生成が可能になる．ほぼ一様ランダムになる．
構成比近似法

重複上限Kの数列

${1}$ 以上 ${M}$ 以下の整数からなる長さ ${N}$ の数列であって，同じ数が出現する回数が ${K}$ 回以下であるものをランダム生成したい．

${N,M,K}$ が小さかったり， ${N << MK}$ かつ ${K}$ がある程度大きかったりすると生成検査法で高速に一様ランダムに生成できる．

${N=MK}$ のときは ${1}$ から ${M}$ まで順に，空いているところから ${K}$ 箇所選んで決めていく方法で一様ランダム生成できる．

${K=1}$ は使ってない整数から一つ選んで前から埋めていけばよい．

生成検査法で ${1}$ 回で条件を満たす確率は， ${1}$ 年が ${M}$ 日であり， ${N}$ 人のうち同じ誕生日の ${K+1}$ 人組が存在しない確率と同じ．(誕生日のパラドックス)

ラベル無し根付き木

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=b169f11a617bab9395da9f880ce677ca520b2348
https://www2.math.upenn.edu/~wilf/website/CombinatorialAlgorithms.pdf

ラベル無し木

https://www2.math.upenn.edu/~wilf/website/Free%20trees.pdf
木の総数の近似

N以下の素数

${N}$ 以下の素数を一様ランダムに生成する
ミラーラビンを使った生成検査法
素数定理から比較的早く生成できることがわかる

全域木

与えられたグラフの全域木を一様ランダムに生成する．
http://jakub.tarnawski.org/slides_soda_2015.pdf ${O(M^{4/3})}$

ライブラリ

github.com

rand_lab_free_trees()	ラベル付き木の一様ランダム生成
rand_lab_rooted_trees()	ラベル付け根付き木の一様ランダム生成
rand_ulab_free_trees()	ラベル無し木の一様ランダム生成
rand_ulab_rooted_trees()	ラベル無し根付き木の一様ランダム生成

2023-02-06

ABC287 G - Balance Update Query

データ構造競技プログラミング解説 ABC

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 種類のカードがあり，最初， ${i}$ 種類目のカードの得点は ${a_i}$ ，枚数は ${b_i}$ 枚である．以下の形式の ${Q}$ 個のクエリを順に処理せよ．

${x}$ 種類目のカードの得点を ${y}$ に変更
${x}$ 種類目のカードの枚数を ${y}$ に変更
${x}$ 枚のカードを選ぶときの得点の総和の最大値を求める．

${1\leq N,Q\leq 2×10^5}$
${1\leq a_i\leq 10^9}$
${1\leq b_i\leq 10^4}$

解説

各ノードに部分木の得点の総和とカードの枚数の総和を持つBinary Trieを作ると，各クエリ ${O(\log{a_{\max}})}$ で処理することができます．

サンプル1を例に挙げて説明します．

初期状態のBinaryTrieは以下のようになります．

最初のクエリでは， ${x=4}$ 枚使った最大の総得点を求めます．
根の右の子の枚数が ${5}$ であることから左の子のカードを使うことはありません．したがって，右の部分木について答えればよいです．
そのさらに右の子を見ると，枚数が ${3}$ 枚なので右の子のカードはすべて使い， ${x\leftarrow x-3}$ として左の子に遷移して再帰的に求めていけばよいです．

2番目のクエリや4番目のクエリのような更新では，更新前の得点や枚数を各ノードから引き，更新後の得点や枚数を足していけばよいです．

提出プログラム

https://atcoder.jp/contests/abc287/submissions/38668500

感想

2023-01-20

ABC285 E - Work or Rest

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

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

曜日 ${1,\dots ,N}$ からなる一週間の各曜日に「平日」か「休日」のどちらかを割り当てる．このとき，曜日 ${i}$ の生産量は以下のように表される．

曜日 ${i}$ が「休日」である場合は ${0}$
曜日 ${i}$ が「平日」のとき，直前の休日が ${x}$ 日前，直後の休日が ${y}$ 日後である場合は ${A_{\min(x,y)}}$

一週間当たりの生産量の最大値を求めよ．

${1\leq N\leq 5000}$
${1\leq A_i\leq 10^9}$

解説

曜日 ${1}$ の前日は曜日 ${N}$ ，というように前後に繋がっているので「平日」「休日」の割り当てを決めた際にrotateをしても答えは変わりません．

つまり，曜日 ${1}$ は必ず休日としてもよいです．

次に，初日が休日で，その後平日が続くようなブロックに分解してみます．

休日 ${1}$ 日＋平日 ${d-1}$ 日の全 ${d(\geq 1)}$ 日からなるブロックの生産量は公式解説の ${B_{d-1}}$ と等しいです．これを ${v_d}$ とします．

すると，この問題は

品物 ${i}$ の重みを ${i}$
品物 ${i}$ の価値を ${v_i}$
品物の重みの合計の上限を ${N}$

としたときの個数制限なしナップサック問題となります．

よって，この問題を時間計算量 ${O(N^2)}$ で解くことができます．

提出プログラム

https://atcoder.jp/contests/abc285/submissions/38167895 C++
https://atcoder.jp/contests/abc285/submissions/38169128 Python

N = int(input())
A = list(map(int,input().split()))
V = [0] * (N+1)
DP = [0] * (N+1)
for i in range(2,N+1):
    V[i] = V[i-1] + A[i//2-1]
    for j in range(i,N+1):
        DP[j] = max(DP[j], DP[j-i] + V[i])
print(DP[N])

感想

ナップサック問題の少し難しい版の問題でした．