2017-03-10

Codeforces Round #403 問題と解説

A. Andryusha and Socks

http://codeforces.com/contest/782/problem/A
1～N番のN組の靴下がある。
左右合わせて2N個の靴下をある順番で受け取る。
もう片方の靴下を受け取るまで机の上にもう片方の靴下を置いておき、もう片方が来たらどちらも片付ける。
机の上に最大何個の靴下が置かれることになるか。

B. The Meeting Place Cannot Be Changed

http://codeforces.com/contest/782/problem/B
N人いる。
それぞれ位置X[i]で歩く速さはV[i] m/秒である。
どこか一箇所に集まる時に最短何秒かかるか。

C. Andrysha and Colored Balloons

http://codeforces.com/contest/782/problem/C
N頂点の木がある。
各頂点に色をつけるが、a - b - cと連結している場合はa,b,cは違う色で塗る必要がある。
つまり、2頂点先までで同じ色があるとダメ。
必要な色数の最小数と、その場合の塗り方を答えよ。

D. Innokenty and a Foodball League

http://codeforces.com/contest/782/problem/D
N個のクラブ名（三文字）と町の名前の組がある。
以下のルールで全ての組に対して三文字の名前を決めることができるかを判定せよ。
できるならば、そのパターンを示せ。
1. 「全てクラブ名にする」か「クラブ名の先頭2文字と町の名前の先頭1文字を合わせる」
2. クラブ名が同じ他のクラブが存在する場合は「全てクラブ名にする」ことで命名ができない

E. Underground Lab

http://codeforces.com/contest/782/problem/E
N頂点M辺の無向グラフがある。
長さfloor(2N/K)以下のパスをK本用意することで全ての頂点を通るようにする。
そのパスの構成を答えよ。

F. Axel and Marston in Bitland

http://codeforces.com/contest/782/problem/F
N頂点M辺の有向グラフがあり、辺には0か1が書かれている。
これに対しPとBから成るパターン文字列を考える。

S[0] = P
S[i] = S[i - 1] + inv(S[i - 1])
inv関数はPとBを反転させる関数
つまり、S = {P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP}

Pは0にBは1に対応している。
頂点1からスタートしてパターン文字列に沿って頂点を移動していく時、移動できる距離の最大値を答えよ。
もし、移動距離が10^18を越える場合は-1と出力せよ。

2017-03-10

HackerRank Game Theory の勧め

競技プログラミング

HackerRank Game Theory

https://www.hackerrank.com/5-days-of-game-theory
Typical DP Contestというのがありますが、それのゲーム理論版

ゲームの勝敗判定をする問題を解く選択肢

必勝法・貪欲法（必勝の条件・法則がある）
バックトラッキング（遷移先に負け状態が1つでもあれば勝ち状態）
Nim/Grundy数

hamayanhamayan.hatenablog.jp

問題

Game of Stones

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-game-of-stones
T個のクエリがある。N個の山があり、そこから2,3,5個のいずれかを取る。
取れなくなったら負け。初手が勝ちならFirst, 後手が勝ちならSecond

Tower Breakers

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers
T個のクエリがある。N個、数Mがある。各数をその数の約数のどれかに変換する操作をする。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

A Chessboard Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-1-a-chessboard-game
T個のクエリがある。15*15のマスに1つ駒がある。
この駒は、(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動できる。
移動できなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Nim Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-nim-game
T個のクエリがある。各クエリは、N個の石の個数がS[i]の石の山がある。
順番に石が残っている山から1つ以上の石を取り除く操作をする。
取り除く石がなくなったら負け。先手が勝ちならFirst, 後手が勝ちならSecond

Misera Nim

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/misere-nim
T個のクエリがある。各クエリは、N個の石の個数がS[i]の石の山がある。
順番に石が残っている山から1つ以上の石を取り除く操作をする。
最後に石を取り除いた方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Nimble Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/nimble
T個のクエリがある。0～N-1個の番号がついた箱にC[i]個の石が入っている。
順番に1以上の番号の箱から石を1つ取り出し、それよりも小さい番号の箱に入れる。
操作が行えなくなった方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Poker Nim

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-poker-nim
T個のクエリがある。N個の石の個数がS[i]の石の山がある。
順番に「石を増やす」か「石を減らす」かする。
ただし「石を増やす」はK回しか行えない。
操作ができなくなった方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Tower Breakers, Revisited!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-2
T個のクエリがある。N個の数列があり、各要素はM[i]。
各数をその数の約数のどれかに変換する操作をする。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

Tower Breakers, Again!!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-3
T個のクエリがある。N個の数列があり、各要素はM[i]。
ある数Xを選び、それをY個の数Zに分ける(Y*Z = X, Y > 1)。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

A Chessboard Game, Again!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-chessboard-game
T個のクエリがある。15*15のマスにk個の駒がある。
この駒は(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動できる。
移動できる駒がなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Digits Square Board

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/digits-square-board
T個のクエリがある。N*Nの板にA[y][x]の数が書いてある。
合成数が1つでも書いてある板を選び、縦横どちらかに割る。
割れなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Fun Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/fun-game
T個のクエリがある。長さNの数列A[i],B[i]がある。
0<= i＜Nとあるiを1つ選ぶと、自分はA[i], 相手はB[i]得られる。
各iは1度しか選べない時、初手が勝ちならFirst, 後手が勝ちならSecond, 同点ならTie

Powers Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/powers-of-two-game
T個のクエリがある。*2^1*2^2*2^3*...*2^nというアスタリスクと2の累乗から成る列がある。
順番に*を+か-かに変える処理を行う。
全て変換後の計算結果が17の倍数なら後手Secondの勝ち、そうでないなら先手Firstの勝ち

Deforestation

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/deforestation
T個のクエリがある。N頂点の根が1の木がある。
互いに辺を1つ選び、その辺で繋がっている子の部分木を削除する。
部分木を消せなくなったら負け。先手が勝ちならFirst, 後手が勝ちならSecond

2017-03-08

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

競技プログラミング

半環

参考1 参考2

半環一覧

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

考え方と注意

漸化式を上手く作れればある線形写像が独立にマージできる (セグメントツリー)
漸化式をとにかく上手く作る
複数のパラメタを用いて順番に更新するような問題でパラメタが更新されるようなクエリがあっても、部分的に修正、高速に計算ができる
セグメントツリーで計算する時に順番に注意

既存のセグメントツリーライブラリを使うのは良いが、順番通りに計算してくれていることを確認

行列累乗が使える条件として利用する場合もある
- この問題
- この問題では行列に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. (行列,+,*)

2017-03-07

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

2017-02-27

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

競技プログラミング

区間DP

dp[L][R] := 区間[L,R]についての何か
簡単な入門問題があまりなかった
発展的だが、Monge性を利用して更新高速化できる場合がある
区間DPのよくある方針としてdp[L][R]をdp[L+1][R]とdp[L][R-1]を使って更新する方針がある
【テク1】中心が決まっていて、左右に遷移区間を伸ばす場合は、左と右の遷移を別々にカウントして、掛け合わせることでO(N)分節約可能

問題

EDPC Slimes 解説
CC Algebra Score 解説
LC Minimum Cost Tree From Leaf Values
CF XOR-pyramid
CF Presents in Bankopolis
AOJ ダルマ落とし
AtCoder イウィ
AOJ 力持ち解説
AOJ ケーキの切り分け2
yukicoder No.484 収穫
AGC020 Encoding Subsets 解説区間DPっぽい感じだがもうちょっと状態数が増える
AOJ 塗り箸 (Chopsticks)
CF505 Disjoint Triangles 解説
CF538 Flood Fill 解説
区間DPで回文を扱う問題が結構ある
【テク1】CGR4 F1 Short Colorful Strip

ここから結構難しい

2017-02-27

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

競技プログラミング

他

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

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

フロー

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

数学

木構造

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

グラフ理論

データ構造

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

動的計画法

未分類

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

2017-02-27

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

競技プログラミング

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

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

問題

HackerRank Game Theory

Nim
Grundy数
後退解析、バックトラック
偶奇を用いた勝ち負け
相手の真似をする必勝法
- HUPC2019 Day2 C 串刺し (Skewering) 解説
- WUPC2020 K Rectangle Game 解説
ミニマックス法

【発展的話題】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");
}

A. Andryusha and Socks

B. The Meeting Place Cannot Be Changed

C. Andrysha and Colored Balloons

D. Innokenty and a Foodball League

E. Underground Lab

F. Axel and Marston in Bitland

HackerRank Game Theory

ゲームの勝敗判定をする問題を解く選択肢

問題

Game of Stones

Tower Breakers

A Chessboard Game

Nim Game

Misera Nim

Nimble Game

Poker Nim

Tower Breakers, Revisited!

Tower Breakers, Again!!

A Chessboard Game, Again!

Digits Square Board

Fun Game

Powers Game

Deforestation

半環

半環一覧

考え方と注意

1. (整数,+,*)

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

2. (整数,xor,and)

ABC 009 D. 漸化式

3. (整数,max,+)

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

4. (行列,+,*)

Good Bye 2016 E. New Year and Old Subsequence

yukicode No.426 往復漸化式

AC DISCO!

AC Dangerous Hopscotch

GPUプログラム検証？

Utah大学 (GKLEE)

論文

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

論文

Twente大学 (VerCors)

論文

Linkoping University

論文

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

論文

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

論文

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

論文

区間DP

問題

他

フロー

数学

データ構造

未分類

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

問題

【発展的話題】Misere Nim

Misera Nim問題