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

hamayanhamayan's blog

競技プログラミングにおける半環問題まとめ

競技プログラミング

半環

半環一覧

(集合,+演算子,*演算子)
1. (整数,+,*)
2. (整数,xor,and)
3. (整数,max,+)
4. (行列,+,*)

考え方と注意

  • 漸化式を上手く作れればある線形写像が独立にマージできる (セグメントツリー)
  • 漸化式をとにかく上手く作る
  • 複数のパラメタを用いて順番に更新するような問題でパラメタが更新されるようなクエリがあっても、部分的に修正、高速に計算ができる
  • セグメントツリーで計算する時に順番に注意
  1. 既存のセグメントツリーライブラリを使うのは良いが、順番通りに計算してくれていることを確認
  • 行列累乗が使える条件として利用する場合もある
    • この問題
    • この問題では行列にmax(w+a,b)を乗せるという問題
    • これはf(w)=max(w+a,b)として遷移関数を定義して解いている
    • すると、合成関数（積）はmax(w+a+c,max(d+a,b))であり、和はmax(w + max(a,c), max(b,,d))となる

以下問題集

1. (整数,+,*)

ARC 008 D. タコヤキオイシクナール

http://arc008.contest.atcoder.jp/tasks/arc008_4

2. (整数,xor,and)

ABC 009 D. 漸化式

http://abc009.contest.atcoder.jp/tasks/abc009_4

3. (整数,max,+)

「みんなのプロコン」 D. 工場

http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_d

4. (行列,+,*)

Good Bye 2016 E. New Year and Old Subsequence

http://codeforces.com/contest/750/problem/E

yukicode No.426 往復漸化式

http://yukicoder.me/problems/no/426

AC DISCO!

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d 解説

AC Dangerous Hopscotch

https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_d 解説

続きを読む

GPUプログラム検証まとめ

研究

GPUプログラム検証？

プログラム検証という研究分野がある。
検証の意味合いについては色々あるが、GPUプログラム上での検証は主にデータ競合の検知が重要となる。
そのデータ競合の検知についての最近の研究についてまとめていく。

最近の事情の俯瞰には、書籍「Advances in GPU Research and Practice」の「Formal Analysis Techniques for Reliable GPU programming: Current Solutions and Call to Action」が詳しいです。

Utah大学 (GKLEE)

http://www.parallel.utah.edu
LLVMの記号実行環境KLEEの拡張としてGPUの検証機能をもたせたGKLEEを開発。
GPUと銘打った論文は2010年から。しかしそれ以前にもMPIプログラムの検証とかをしている。
以前はPUGを開発していたが、そちらは終了して、今はGKLEEがメイン。
GKLEEで使用するSESAという静的解析ツールも作成している。
中心人物: Peng Li, Guodong Li, Ganesh Gopalakrishnan

論文

  • 2010年 A Symbolic Verifier for Cuda Programs
  • ☆2010年 PUG: A Symbolic Verifier of GPU Programs
  • 2010年 Scalable SMT-Based Verification of GPU Kernel Functions
  • ☆2012年 GKLEE: Concolic Verification and Test Generation for GPUs
  • 2012年 Parametrized Verification of GPU Kernels
  • ☆2012年 Parametric Flows: Automated Behavior Equivalencing for Symbolic Analysis of Races in CUDA Programs
  • 2013年 Formal Analysis of GPU Programs with Atomics via Conflict-Detected Delay-Bounding
  • ☆2014年 Practical Symbolic Checking of GPU Programs

インペリアル・カレッジ・ロンドン (GPUVerify)

http://multicore.doc.ic.ac.uk
検証用の言語Boogieを使って検証するGPUVerifyを開発。
中心人物: Alastair F. Donaldson

論文

  • 2011年 Symbolic Testing of OpenCL Code
  • ☆2012年 GPUVerify: a Verifier for GPU Kernels
  • 2013年 Interleaving and Lock-Step Semantics for Analysis and Verification of GPU Kernels
  • ☆2013年 Barrier Invariants: a Shared State Abstraction for the Analysis of Data-Dependent GPU Kernels
  • 2014年 KernelInterceptor: Automating GPU Kernel Verification by Intercepting Kernels and their Parameters
  • ☆2015年 The Design and Implementation of a Verification Technique for GPU Kernels

Twente大学 (VerCors)

http://fmt.cs.utwente.nl
検証プラットフォームVerCorsにOpenCLも検証できるようにした感じ。
Permission-Based Separation Logicを使用。

論文

  • 2013年 Specification and verification of GPGPU programs using permission-based separation logic
  • 2014年 A Case Study for GPGPU Program Verification
  • 2015年 Specification and Verification of Atomic Operations in GPGPU Programs

Linkoping University

論文

  • 2011年 Software Model Checking for GPGPU Programs Towards a Verification Tool
  • 2014年 Automated Software Testing of Memory Performance in Embedded GPUs

オハイオ州立大学（GRaceなど）

研究室のサイトは更新が止まっているようなので、筆者のサイトを追うと良い
http://web.cse.ohio-state.edu/~qin/publication.htm
http://web.cse.ohio-state.edu/~agrawal/
中心人物: Feng Qin, Gagan Agrawal

論文

  • 2010年 GRace: A Low-Overhead Mechanism for Detecting Data Races in GPU Programs
  • 2012年 GMProf: A Low-Overhead, Fine-Grained Profiling Approach for GPU Programs(検証じゃない)
  • 2014年 GMRace: Detecting Data Races in GPU Programs via a Low-Overhead Scheme

東京工業大学、増原英彦研究室

Coqを使ったsoundnessの検証
http://prg.is.titech.ac.jp/ja/news/coqpl17/
http://prg.is.titech.ac.jp/ja/projects/gpucsl/
最近発見した。

論文

  • 2016年 Proof of Soundness of concurrent Separation Logic for GPGPU in Coq
  • 2017年 CertSkel: a Verified Compiler for a Coq-embedded GPGPU DSL

京都大学、計算機ソフトウェア分野

http://www.fos.kuis.kyoto-u.ac.jp
ホーア理論を使ってGPUを検証しているみたい。

論文

  • 2016年 Automated verification of functional correctness of race-free GPU programs
  • 2017年 A Hoare Logic for GPU kernels

競技プログラミングにおける区間DP問題まとめ

競技プログラミング

区間DP

問題

ここから結構難しい

続きを読む

競技プログラミング練習問題集

競技プログラミング

他

競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん
DEGwerさんの数え上げテクニック集問題まとめ - はまやんはまやんはまやん
セグメントツリーにセグメントツリーを乗せる手法（2Dセグメントツリー） - はまやんはまやんはまやん
HackerRank Game Theory の勧め - はまやんはまやんはまやん
Educational DP Contestの勧め - はまやんはまやんはまやん
今年中に理解する！多項式、母関数、形式的べき級数の競プロでの実践的使い方 - はまやんはまやんはまやん

パソコン甲子園 プログラミング部門 解説まとめ - はまやんはまやんはまやん
日本情報オリンピック 解説まとめ - はまやんはまやんはまやん
アルゴリズム実技検定解説まとめ - はまやんはまやんはまやん


　
　

フロー

競技プログラミングにおける最小費用流問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける最大マッチング問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける最大流問題まとめ - はまやんはまやんはまやん

数学

競技プログラミングにおける数学的問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける多項式問題まとめ [母関数、形式的べき級数、線形漸化式、高速きたまさ法] - はまやんはまやんはまやん
競技プログラミングにおける包除原理問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける連立方程式問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける半環問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける確率・期待値問題 - はまやんはまやんはまやん
競技プログラミングにおける畳み込み問題まとめ（FFT,アダマール変換,メビウス変換,ゼータ変換） - はまやんはまやんはまやん
競技プログラミングにおけるXOR問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける中国剰余定理問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける線形計画問題・整数計画問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるフィボナッチ数列問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける有理数問題まとめ - はまやんはまやんはまやん

木構造

競技プログラミングにおけるLCA問題まとめ [auxiliary tree] - はまやんはまやんはまやん
競技プログラミングにおけるHL分解まとめ - はまやんはまやんはまやん
競技プログラミングにおけるオイラーツアー問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける木の同型判定問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける重心分解問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるLC木問題まとめ [Link Cut Tree, Dynamic Tree, TopTree] - はまやんはまやんはまやん

グラフ理論

競技プログラミングにおける無向グラフ上での特殊な数え上げ問題まとめ [スペクトルグラフ理論, 行列木定理, ケイリーの公式] - はまやんはまやんはまやん
競技プログラミングにおける無向グラフに関する（橋、関節点、サイクル基底、lowlink）問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける最短経路問題まとめ [ダイクストラ, ベルマンフォード, ワーシャルフロイド] - はまやんはまやんはまやん
競技プログラミングにおけるオイラー路問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける有向グラフに関する問題まとめ [強連結成分分解, 最小パス被覆, Dilworthの定理, トポロジカルソート] - はまやんはまやんはまやん
競技プログラミングにおける最大クリーク問題、最大独立集合問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける幅優先探索問題まとめ [BFS, 後退解析] - はまやんはまやんはまやん
競技プログラミングにおける最小全域木問題まとめ [MST, プリム, クラスカル, ブルーフカ] - はまやんはまやんはまやん

データ構造

競技プログラミングにおけるUnionFind問題まとめ [DSU] - はまやんはまやんはまやん
競技プログラミングにおけるセグメントツリー問題まとめ [セグメントツリー, BIT, 遅延評価セグメントツリー] - はまやんはまやんはまやん
競技プログラミングにおける永続データ構造問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける平衡二分木問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるSparse Table問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるWaveletMatrix問題まとめ - はまやんはまやんはまやん

動的計画法

競技プログラミングにおける動的計画法問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける区間DP問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける桁DP問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける動的計画法更新最適化まとめ（CHT, MongeDP, AlianDP, インラインDP, きたまさ法, 行列累乗） - はまやんはまやんはまやん
競技プログラミングにおける戻すDP問題 - はまやんはまやんはまやん
競技プログラミングにおける全方位木DP問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける木DP問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるbitDP問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける挿入DP問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける連結DP問題まとめ - はまやんはまやんはまやん

未分類

競技プログラミングにおける枝刈り問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるマンハッタン距離問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるしゃくとり法問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける二分探索・三分探索問題まとめ [二分法] - はまやんはまやんはまやん
競技プログラミングにおけるimos法・累積和問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける最長部分増加列問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるMo's Algorithm問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける平方分割問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける文字列アルゴリズム問題まとめ [ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm,Palindromic Tree, Manacher, Suffix Tree] - はまやんはまやんはまやん
競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法] - はまやんはまやんはまやん
競技プログラミングにおける2-SAT問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるマージテク問題まとめ - はまやんはまやんはまやん
競技プログラミングにおけるエラトステネスの篩・区間篩・調和級数計算量問題 - はまやんはまやんはまやん
競技プログラミングにおける分割統治法問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける凸包問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける構築問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける乱択アルゴリズム問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける半分全列挙問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける最近点対問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける幾何問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける構文解析問題まとめ - はまやんはまやんはまやん
競技プログラミングにおける平面走査問題まとめ - はまやんはまやんはまやん


Codeforcesのよくまとまっているやつ
宝の山

競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法]

競技プログラミング

ゲーム問題を解決する手段

  • Nim
    • 「N個の石山があり、交互に山から石を任意個取っていく。先に取れなくなったほうが負け。」
    • 各石山の個数をx[i]個とすると、勝敗は各山の個数を全てxorした値を見れば分かる。全てxorして=0なら先手は負け、!=0なら勝ち
    • Nimの派生
  • Grundy数
    • 2人でやるようなゲームではGrundy数に帰着させることでNimの原理で解ける場合がある
    • Grundy数を以下のように定める
      • 負け状態のGrundy数は0
      • ある状態のGrundy数はそこから遷移可能な状態のGrundy数の中で最小の非負整数
    • grundy数とNimにおける石の数は同じ意味
    • 高さLの完全二分木のgrundy数はL&-L
    • 規則性
      • ある周期になっている
  • 後退解析、バックトラック 参考
    • 状態の遷移先に負け状態が1つでもあれば、相手を負けにできるので勝ち状態
    • 逆に遷移先が全て勝ち状態ならば、自分は負けるしか無い
  • 特殊な勝ち負け
    • 偶奇を使う
    • 相手の行動を真似ると負けない
      • 例えば、点対称に同様に置いていくと必ず置けるから、先手が置けるなら後手が必ず置けるので、後手必勝
  • ミニマックス法
    • 自分は利得を最大化し、相手は利得を最小化する

問題

HackerRank Game Theory

【発展的話題】Misere Nim

最後に石を取ると負けとしたNimのこと。よく分かる解説。
http://sigma425.hatenablog.com/entry/2014/12/07/132702
http://winjii.hatenablog.com/entry/2016/05/29/143653
簡単には、

  • 積まれている石の数が2以上のものがあれば普通のNim
  • 全部1の場合は山の偶奇によって勝敗が分かる

実装

int N; cin >> N;
int g = 0, ma = 0;
rep(j, 0, N) {
	int s; cin >> s;
	g ^= s;
	ma = max(ma, s);
}

if (ma == 1) {
	if (N % 2) printf("Second\n");
	else printf("First\n");
} else {
	if (g != 0) printf("First\n");
	else printf("Second\n");
}

Misera Nim問題

競技プログラミングにおける動的計画法問題まとめ

競技プログラミング

動的計画法をまとめたもの

入門者向け

  • まずは「最大最小系」「yes/no系」「組み合わせ系」
  • 基礎はこことか、こことか、こことかで勉強しよう
  • ループで書くか、再帰関数かというのがあるが、こっちの方が書きやすいとかがあったりするので、どちらも書けるようになるのがオススメ

入門問題

最大最小系
dp[] := その条件下での最大値・最小値

yes/no系
dp[] := その条件下でのtrue/false

組み合わせ系
dp[] := その条件下での組合せ数

より強くなるために

テク一覧

1. オートマトン上でDPする手法がある
2. 選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする
3. 状態が全部必要ないので状態数が削減できる
4. 正しい括弧列(dyck列)の数え上げはカタラン数を関連がある 必要な問題 解説
5. dp[L][R][sm]をやる時は答えを更新していくことでdp[L][sm]だけで済む場合がある
6. 隣り合う要素の更新を入れることで最近だけの更新を考えるだけで良くなる
7. 尺取り法を応用した更新最適化がある
8. メモリが少ない場合での復元には再帰を使うテクがある
9. 区間を添え字として持つDPがある
10. 【箱根DP】2つの順列の対応付けを行う典型
11. 文字列の部分列の個数を添え字に持つ典型
12. 縦と横は独立に計算できるため、O(WHN)をO(WN+HN+WH)にできる
13. 添字が負数になる場合は添字+baseをして、0をbaseにして使う
14. 境界線をうまく決めることで状態をまとめていく chokudaiさんの解説放送からの知見
15. 負の数を経由することで最適解が得られることがあるような問題は、最大最小の両方を保持しながらDPしていく
16. 配列を使い回すことでメモリ使用量を節約する（500^3は256MBに乗らない）
17. 遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる
18. 全体で遷移数がそんなに多くないことを見抜く
19. 配るDPを貰うDPに直して、データ構造で更新最適化
20. 【編集距離】編集距離の計算は、2つの文字列の添字を持つDPでできる

中難易度問題（工事中）

以下DPの問題(適当に分類、結構難しいのも含まれる)

最大最小系

yes/no系

組み合わせ系

雪の足跡 [yukicoder 340]

競技プログラミング

問題

https://yukicoder.me/problems/no/340

W×Hの盤面があり、N人の人がそこを通る。
i番目の人はM[i]回移動していて、移動先はB[i][j]->B[i][j + 1]である。
移動元と移動先はw + h * Wで表記されていて、距離が1とは限らない。

その移動後に(0,0)から(W - 1, H - 1)へN人が移動した方向と同じ方向に移れるとしたときの最短距離を求めよ。

1 <= W, H <= 10^3
0 <= N, M[i] <= 10^3
0 <= B[i][j] < W * H

続きを読む