はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける包除原理問題まとめ

包除原理

 

  • 数え上げをする時の定理 ここが詳しい ここの包除原理の欄も詳しい
  • 基本は状態系包除原理
  • 状態系包除原理を個数に注目して個数系包除原理にするテクがある(抽象化による状態圧縮)
    • n(AorBorC) = n(A) + n(B) + n(C) - n(A&B) - n(B&C) - n(C&A) + n(A&B&C)
    • もし、「dp[i] := i個の&で表現できる組み合わせ数」が高速に計算できれば、
    • n(AorBorC) = dp[1] - dp[2] + dp[3]
    • 事前計算が高速にできれば包除原理計算部分をO(2^N)からO(N)に削減できる
    • 問題によっては「dp[i] := &でつながれている個数の偶奇がiであるときの組み合わせ数」のように更に状態を圧縮出来る場合もある これ
  • 順列の組み合わせ数は、組合せの組み合わせ数と包除原理から求めるテクがある 問題1 問題2
  • 約数系包除原理というのもある(まだ完全に理解できてないかも)
    • drkenさんの記事のまとめ DEGwerさんの数え上げテクニック集 に記述がある
    • 上の包除原理とは少し異なる
    • DEGwerさんの資料抜粋
      • あるパラメタがkの倍数である場合
        • dp[k]を確定する時に重複して数えているkの倍数を引く
        • dp[k] = (kに対する何らかの計算)- Σ{lはkの倍数}dp[l]
        • 計算量はエラトステネスの篩と同じ形になるのでO(NlogN)
        • 計算はkを大きい順からやっていく。k以上から倍数の数を引いていくことで丁度kを求める感じ
      • あるパラメタがkの約数である
        • dp[k]を確定する時に重複して数えているkの約数を引く
        • dp[k] = (kに対する何らかの計算)- Σ{lはkの約数}dp[l]
        • 計算量はO(Nf(N))、f(x)はxの約数の個数(約数の個数は10^9で10^3くらい)
        • 計算はkを小さい順からやっていく。これも、k以下から約数の数を引いていくことで丁度kを求める感じ
    • 包除原理に見られる(-1)^kは出てこない
  • 状態系包除原理においてメビウス関数を使って(-1)^k部分を決定するテクがある
    • n(2) + n(3) + n(5) - n(6) - n(10) - n(15) + n(30)みたいな計算の+,-,0を決定できる
    • 具体的には
      • 0 : 平方数が因数に含まれる(包除原理での計算外としてみなせる)
      • -1 : 素因数の個数が奇数
      • 1 : 素因数の個数が偶数
    • メビウス関数ってO(NlogN)以外の高速な計算法ある?
続きを読む

Codeforces Round #409 Div1 問題と解説

http://codeforces.com/contest/800

問題

A. Voltage Keepsake

N個のデバイスがあり、1秒にA[i]エネルギー使い、元々B[i]エネルギー分充電されている。
毎秒Pエネルギー充電できる充電器が1つだけある。
全てのデバイスを同時に使用する時、充電器を適切に使いまわすことで最大何秒全て稼働させられるか。
無限に動かせるなら"-1"

B. Volatile Kite

N頂点の凸包がある。
全ての頂点を最大長さD分だけ任意の場所へ動かせるとする。
どのように動かしても凸包となる長さDの最大値を求めよ。

C. Vulnerable Kerbals

N個の禁止リストと整数Mがある。
以下のルールを満たす数列Aを求めよ。
1. 全ての要素は[0,M-1]
2. 接頭積列の全ての要素は独立
3. 接頭積列に禁止リストの要素は含まれない
4. 上記のルールを満たすなかで要素数最大
※ 接頭積列(prefix product) : 俺の造語なので注意。B[i] = A[0] * A[1] * ... * A[i]が一般項となる列

D. Varying Kibibits

N個の数列Tがある。

関数f(L)がある。
この関数は数列Lに対して、以下のルールである数を返す。
1. 数列L内の全ての数の桁数が最大のものと等しくなるように先頭に0をつける。
2. i番目の文字が数列Lの全てのi番目の文字の最小となるように文字列を作る。
3. 2.で作った文字列を数に変換して出力

例) f(10,9)
1. 10, 09
2. 1番目は1と0なので0、2番目は0と9なので0より00という文字列が作られる
3. よって f(10,9)=0

関数G(x)がある。
G(x)はf(S)=xとなる全ての空集合でないTの部分集合Sについて要素の総和を二乗して足した数mod(10^9+7)にxを掛けた数である。

G(0) xor G(1) xor ... xor G(999999)を答えよ

以下、解説

続きを読む

並列プロセス概観

並列プロセスの形式的解析

この辺を見ると大体つかめる
https://ja.wikipedia.org/wiki/並行性
https://ja.wikipedia.org/wiki/プロセス計算

並列的相互作用と通信

  • 共有メモリ通信
  • メッセージパッシング通信

メッセージパッシング通信

  • Erlang, Occamなどでプログラミングは記述される
  • メッセージパッシングを分析し、理解するための数学的理論が存在

1. アクターモデル
2. 各種プロセス代数
3. ペトリネット

プロセス代数・プロセス計算

プロセス間の相互作用、通信、同期を抽象的に、かつ形式的に表現する。
これによりプロセス間の等価性(双模倣性)についての形式的推論が可能になる。
形式としてはCSP,CCS,π-calculusなどがある。
※ CCS : Calculus of Communicating Systems
※ CSP : Communicating Sequential Processes
この辺がプロセス代数の発端でここから、色んな派生が生まれて、総括してプロセス代数と呼ばれる。

疑問点

  • プロセス代数はメッセージパッシング通信をする並列プロセス向けの代数学のように見える。GPUはどちらかというと共有メモリ通信であり、セマフォのような構造を使って排他処理的なことをしているのだが、代数としてプロセス代数を使ってもよいのだろうか。

Google Code Jam 2017 Round 1A 問題と解説

https://code.google.com/codejam/contest/5304486/dashboard

A. Alphabet Cake

R*Cのマスがある。
各マスは?かA~Zで塗られている。
A~Zは最多"1つ"だけ書かれている。
残りの?のマスを全ての文字の領域が長方形になるようにA~Zを塗れ。

B. Ratatouille

(キレた)

C. Play the Dragon

自分の体力Hd攻撃力Ad, 敵の体力Hk攻撃力Akである。
自分が先攻で以下の行動ができる。

1. 攻撃 : 攻撃力分だけ相手の体力を減らす
2. バフ : 攻撃力を+Bする
3. 回復 : 体力をHdにする
4. デバグ : 相手の攻撃力を-Dする

最短何ターンで勝てるか。勝てないならIMPOSSIBLE

以下、解説

続きを読む

競技プログラミングにおける平方分割問題まとめ

平方分割

  • Square Root Decomposition
  • 区間に対するクエリに対して高速に処理できる
  • ここが詳しい
  • 区間でのクエリであるが、ソートして平方分割して、各バケットでクエリに入る要素だけ抜き出す平方分割もある
    • こういう問題
    • 1.添字と共に昇順ソート 2.バケット毎に添え字ソート 3.各クエリについて全てのバケットのans[L][R]を取得してマージ
    • 出現頻度を扱う場合は平方分割が多いイメージ
  • クエリの平方分割
    • Q個のクエリを分けて解く手法 資料
  • 取得クエリだけで更新クエリが無い場合はバケットの間の処理は事前計算することで、処理をより軽くすることができる場合がある この解説

競技プログラミングにおけるHL分解まとめ

HL分解

問題

競技プログラミングにおけるオイラーツアー問題まとめ

オイラーツアー

  • 木をDFSしたときの順番で頂点を記録する手法
    • pre-order : 頂点に到着したら記録
    • post-order : 頂点から離れるときに記録
  • 用途
    • 根付き木のある頂点からの部分木に対するクエリを処理
    • ある頂点がある頂点の部分木に含まれるかを高速に判定する
    • 上手くオイラーツアーを作るとパスのコストの総和が取れる
  • 木をBFSしたときの順番で頂点を記録するBFS Euler Tourというのもある
    • オイラーツアーのbfs-order
    • 用途としては、ある頂点から一定の距離にある頂点に対して区間操作を行える

問題

オイラーツアーっぽくやる問題