2017-01-15

MovingTokens [SRM 705 : Div1 Med]

競技プログラミング

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14471

N個のトークンが1つずつ入ったビンがある。
N*Mの行列Aがあり、以下の操作がある。

0 <= i <= M-1 を1つ選び、j番目のビンの中身を全てA[j][i]に全てのビンで同時に移す

この操作を無限回最適な順番で行う時、中身があるビンの個数の最小値は？

1 <= N, M <= 50

2016-11-14

競技プログラミングにおける確率・期待値問題

競技プログラミング

確率・期待値DP

「dp[i] := ～となる確率・期待値」でDPする
とても良い資料
期待値DPの優良資料
使える知識
- 期待値の線形性
- 「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」(出典)
  - ARC085A HSI
  - ABC194D Journey
- Nターンあったら、各ターンは別々に期待値が計算できたりする（これって線形性？）問題
- 【テク1】2つのものを1つにまとめる計算をどんどんしていくと、最終的に1つになって、それが答え

問題

数学

yukicoder No.813 ユキちゃんの冒険

恐らくアドホック

yukicoder No.475 最終日 - Writerの怠慢解説

ある部分を全探索して求める

yukicoder No.574 正多面体サイコロ解説

確率DP

再帰関数系(木DP？)

期待値DP

期待値の線形性

クエリ系？

CF New Year Santa Network

未解決

2016-10-21

競技プログラミングにおけるエラトステネスの篩・区間篩・調和級数計算量問題

競技プログラミング

uwiさんの最強まとめ

エラトステネスの篩

本来は素数列挙のためのアルゴリズム解説
rep(i,1,N) for(j=i;j<=N;j+=i) というループ構造はO(NlogN)で行えるという所を応用して問題を解く
以下の問題はエラトステネスの篩以外にも上のループ構造のお陰で計算量がO(NlogN)に落ちる問題も入れてある

区間篩

「R<=10^12, R-L<=10^6という制約がヒント」
[L,R]の区間の素数判定をする手法である
[L,R]の区間の素因数分解もできる

調和級数的計算量

エラトステネスの篩がO(NlogN)で計算できるというような計算量の考え方を調和級数的計算量みたいに表現したりもする
つまるところは「rep(i,1,N) for(j=i;j<=N;j+=i) というループ構造はO(NlogN)で行えるという所を応用して問題を解く」

問題

素数列挙
- ACPC 素数解説
- yukicoder No.843 Triple Primes 解説

約数列挙
- HUPC2019B 自身の 2 倍解説

エラトステネスの篩的計算量（調和級数計算量）で解ける
区間篩
- CC Chef and Divisor Tree 解説
- JAG Prime-Factor Prime 解説

2016-10-18

競技プログラミングにおける無向グラフに関する（橋、関節点、サイクル基底、lowlink）問題まとめ

競技プログラミング

無向グラフへの取り組み

二重辺連結成分分解と橋
- 橋とはその辺をなくすと連結でなくなる辺のこと
- 二重辺連結成分とは橋を含まない頂点集合のこと
- 無向グラフを二重辺連結成分に分解するよく分かる解説
- 各成分内では、任意の3頂点を取ってきた時にa->b->cとなる辺素パス（同じ辺を2回使わない）が存在する
- 各成分を縮約して1つの頂点とすると、無向グラフは木に変換される
二重頂点連結成分分解と関節点
- vertex biconnected components
- 関節点とはその頂点をなくすと連結でなくなる辺のこと
- 二重頂点連結成分とはこの分かりやすいイメージのように成分分解すること
- ある頂点が複数の成分に属する場合がある(関節点は複数の成分に属する)
- 全ての単純サイクルが奇数長だけであるグラフは、すべての二重頂点連結成分が橋または単純サイクルをなすcactus graphになる解説と問題
- In a biconnected graph with n ≥ 3 points, for any three different vertices a, b, c, there is a simple path to from a to b going through c.
- これも各成分を縮約すると、木となるが、Block-Cut Treeと言うらしい
- lowlink(参考)を知っていると良い(lowlinkを知ってると良い問題その2)
サイクル基底
- cycle basis, 無向グラフのサイクルについての理論
- 日本語で競プロ向けに書いてあるのはKUPC2012のKの解説
- 無向グラフを好きなルートで回って特定の所に行く時の最適化で使える
- dfsを1回することでサイクル基底が得られる。xorの場合は、ガウスの消去法を使うことでサイクル基底の個数を更に減らすことができる
サイクルの偶奇による分類
- 偶数長サイクルだけのグラフは二部グラフである
- 奇数長サイクルだけのグラフはcactusといい、全ての二重頂点連結成分は橋かサイクルになる解説と問題
  - cactusグラフでは辺を共有する閉路は存在しない（つまり、閉路の全列挙が現実的な時間でできる）問題
dfs木
- 無向グラフをdfs順で回っていって使った辺のみで構築した木
- 後退辺をうまく使いながら処理していく
スペクトルグラフ理論
エルデシュガライの定理
- 参考
木を最小パスで被覆する問題に対する解法
- 参考
- 「辺の重複あり」適切に葉同士で繋ぐ
- 「辺の重複無し」奇数次の点に適当に辺を張ってオイラー閉路作って切っていく
全ての辺について端点のどちらかを選択する。このときに、2つ以上の辺に選択されている頂点が存在しないようにせよ
- 連結成分において、（辺の数）≦（頂点の数）であればよい
- 問題1 問題2