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

hamayanhamayan's blog

Codeforces Round #403 問題と解説

http://codeforces.com/contest/782

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と出力せよ。

続きを読む

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

続きを読む

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

半環

競技プログラミング的な解釈だと
https://www.slideshare.net/chokudai/abc009/86
が神がかって分かりやすい。
pekempeyさんの解説もお金取って良いんじゃないかレベルで神がかってる
http://pekempey.hatenablog.com/entry/2017/03/07/023127

半環一覧

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

考え方と注意

  • 漸化式を上手く作れればある線形写像が独立にマージできる (セグメントツリー)
  • 漸化式をとにかく上手く作る
  • 複数のパラメタを用いて順番に更新するような問題でパラメタが更新されるようなクエリがあっても、部分的に修正、高速に計算ができる
  • セグメントツリーで計算する時に順番に注意
  1. 交換則が成り立ってないかも
  2. 既存のセグメントツリーライブラリを使うのは良いが、順番通りに計算してくれていることを確認
  3. こんなバグわかんねぇよ(3時間は溶けた)

以下問題集

1. (整数,+,*)

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

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

2. (整数,xor,and)

3. (整数,max,+)

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

続きを読む

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

易しい確率問題

中難易度の確率問題

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

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

確率DP

難しい確率問題

続きを読む

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

dp[L][R] := 区間[L,R]についての何か
簡単な入門問題があまりなかったですね

問題

Codeforces Tinkoff Challenge - Elimination Round D. Presents in Bankopolis

http://codeforces.com/contest/793/problem/D

Typical DP Contest I. イウィ

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi

yukicoder No.484 収穫

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

[難] CODE FESTIVAL 2015 決勝 G. スタンプラリー

http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_g

続きを読む

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

競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん