読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

RUPC 2017 day1 解説

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp17Day1以下、解説

競技プログラミングにおける動的計画法更新最適化まとめ

動的計画法更新最適化? 動的計画法で更新式を立ててみると、データ構造などを上手く使うことで計算量が落とせる場合がある。 参考 http://codeforces.com/blog/entry/8219 http://codeforces.com/blog/entry/47932 SegmentTree dp[i][j] = dp[i-1][0] + dp[…

Week of Code 30 問題と解説

問題 Candy Replenishing Robot https://www.hackerrank.com/contests/w30/challenges/candy-replenishing-robot カップ内のボールの数をb個とする。最初はb=N。 これについて以下の操作をT回する。1. C[i]個のボールを取り除く。つまり、b=b-C[i](各操作で…

Codechef March Cook-Off 2017 問題と解説

https://www.codechef.com/COOK80 問題 Safe Robot https://www.codechef.com/COOK80/problems/ROBOTG 縦N横Mのマスがある。 ロボットはLRUDから構成された命令に従って移動する。 全ての命令の過程でマス目からはみ出ないロボットの初期マスが存在するか。 …

CSAcademy Round #21 問題と解説

https://csacademy.com/contest/round-21/ 問題 Min Coin Payment https://csacademy.com/contest/round-21/#task/min-coin-payment 無限の1,5,50ドルがある。 これを使ってKドルを最小個数で作れ。 Prime Distance https://csacademy.com/contest/round-21/…

競技プログラミングにおける戻すDP問題

戻すDPとは https://yukicoder.me/wiki/polynomial_techniques http://sigma425.hatenablog.com/entry/2015/07/31/121439 問題 ARC 028 D. 注文の多い高橋商店 http://arc028.contest.atcoder.jp/tasks/arc028_4 yukicoder No.155 生放送とBGM http://yukico…

Codeforces Round #405 問題と解説

http://codeforces.com/contest/790 http://codeforces.com/contest/791 A. Bear and Big Brother http://codeforces.com/contest/791/problem/A 2つの数A,Bがある。 一回の操作でAは3倍、Bは2倍される。 最小何回の操作でA > Bとなるか。 B. Bear and Frien…

AtCoder Beginner Contest 056 / AtCoder Beginner Contest 070 解説

http://abc056.contest.atcoder.jp http://arc070.contest.atcoder.jp以下、解説

Codeforces New Entry Crawlerをリリースしました

Codeforces New Entry Crawlerとは? Codeforces New Entry Crawler https://codeforces-new-entry-crawler.herokuapp.comCodeforcesの新着記事をクロールして表形式・RSSで出力する。 最近、Codeforcesのブログ記事を追うのにはまっていて、RSSで最新エント…

Codeforces Round #404 問題と解説

http://codeforces.com/contest/785 A. Anton and Polyhedrons http://codeforces.com/contest/785/problem/A "Tetrahedron"なら4面体, "Cube"なら6面体, "Octahedron"なら8面体, "Dodecahedron"なら12面体, "Icosahedron"なら20面体である。 N個の上の5つの…

競技プログラミングにおける連立方程式問題まとめ

連立方程式を使った解法について 一次連立方程式を解く ガウスの消去法, 反復法(誤差に注意)のどちらでも解ける 反復法で10^4ループぐらいすれば十分な精度が得られそう?(初期値も適当で大丈夫そう。誤差10^-9以内でもACできた) 漸化式を作った時にDP更…

モデル検査とその手法

モデル検査 システムがある性質を満たすかを形式的に検証すること。 システムはプログラムとか仕様でもいい。 ある性質は活性とか、単にこういう値にならないとか。以下、よく使われる手法。 帰納法 論文 2011年 Software Verification Using k-Induction

AtCoder Grand Contest 011 解説

http://agc011.contest.atcoder.jp以下、解説

Battle Conference U30 解説

http://bcu30.contest.atcoder.jp以下、解説

yukicoder contest-158 解説 (yukicoder No.490 491 492 493)

http://yukicoder.me/contests/159解説です。

Codeforces Round #403 問題と解説

http://codeforces.com/contest/782 A. Andryusha and Socks http://codeforces.com/contest/782/problem/A 1~N番のN組の靴下がある。 左右合わせて2N個の靴下をある順番で受け取る。 もう片方の靴下を受け取るまで机の上にもう片方の靴下を置いておき、も…

HackerRank Game Theory の勧め

HackerRank Game Theory https://www.hackerrank.com/5-days-of-game-theory Typical DP Contestというのがありますが、それのゲーム理論版 ゲームの勝敗判定をする問題を解く選択肢 必勝法・貪欲法(必勝の条件・法則がある) バックトラッキング(遷移先に…

競技プログラミングにおけるセグメントツリー問題まとめ

へのリンク http://codeforces.com/blog/entry/22616 覚書ついでに。

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

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

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

易しい確率問題 中難易度の確率問題 yukicoder No.475 最終日 - Writerの怠慢 http://yukicoder.me/problems/no/475 確率DP 難しい確率問題

GPUプログラム検証まとめ

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

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

区間DP dp[L][R] := 区間[L,R]についての何か 簡単な入門問題があまりなかったですね 問題 IPCP国内予選2016 D. ダルマ落とし http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp Typical DP Contest I. イウィ http://tdpc.contest.at…

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

競技プログラミングにおける動的計画法更新最適化まとめ - はまやんはまやんはまやん 競技プログラミングにおける戻すDP問題 - はまやんはまやんはまやん 競技プログラミングにおける連立方程式問題まとめ - はまやんはまやんはまやん 競技プログラミングに…

競技プログラミングにおけるNim/Grundy数問題まとめ

Nim/Grundy 本質を理解して無くても使うだけなら大丈夫。 どちらが勝つかを判定するような問題で使える。 HackerRankのGame Theoryも練習としていい。 hamayanhamayan.hatenablog.jp Nim N個の石山があり、交互に山から石を任意個取っていく。 先に取れなく…

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

入門: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021246 基礎: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021329 桁DP dp[i][j][k] := i桁目までである条件jで、境界上にあるかの真偽kの何か Typical DP Contest E. 数 http://tdp…

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

入門: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021246 応用: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021423 木DP 木の頂点についてDPを作る dp[i] := 頂点iの部分木についての何か ABC 036 D. 塗り絵 http://abc036.contest.…

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

基礎: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021329 応用: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021423動的計画法は結構練習しないと難しいです。 動的計画法がよく使われる条件は以下の通りです。 数え上げ(mod 10^9+7)…

雪の足跡 [yukicoder 340]

問題 https://yukicoder.me/problems/no/340W×Hの盤面があり、N人の人がそこを通る。 i番目の人はM[i]回移動していて、移動先はB[i][j]->B[i][j + 1]である。 移動元と移動先はw + h * Wで表記されていて、距離が1とは限らない。その移動後に(0,0)から(W - 1…

競技プログラミングにおけるAho-Corasick問題まとめ

Aho-Corasick法とは Trie木の拡張 このページで概念を理解した http://algoogle.hadrori.jp/algorithm/aho-corasick.html 木を構築するアルゴリズムは正直理解してない ei1333さんのブログでもこれと同様の記事がある http://ei1333.hateblo.jp/entry/2017/0…

競技プログラミングにおける2-SAT問題まとめ

2-SATとは しっかりした定義ではなく競技プログラミングで使う定義では、「x ∧ y」の選言の充足判定をすること。 http://naoyat.hatenablog.jp/entry/2013/07/13/220034 http://codeforces.com/blog/entry/16205 この辺りが詳しい。 2-SATを特にはSCCを使う…

PalindromicSubseq [SRM 708 : Div1 Med]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14526N文字の文字列Sがある。 X[i] := Sの部分文字列のうちS[i]を含み、回文となる組合せ Y[i] = i * X[i] % (10^9 + 7) Y[1] xor Y[2] xor ... xor Y[N]を答えよ。1

競技プログラミングにおけるマージテク問題まとめ

間違っていたら指摘して頂けると助かります。 マージテクとは? 集合をまとめる時に大きい方に小さい方を移動させることでマージさせることです。 小さい方にしっかりまとめることで処理時間とメモリを節約できて、間に合うというやつです。 マージにかかる…

競技プログラミングにおける全方位木DP問題まとめ

誰かに聞いたわけじゃないので、間違っていたら指摘して頂けると助かります。 全方位木DPとは? 全方角木DPとも言ったりするが、一般に木DPはその頂点を根としたサブツリーについての性質を表すdpを書く。 しかし、全方位木DPはその頂点を根とした木全体につ…

競技プログラミングにおける木の同型判定問題まとめ

この前のコドフォで木の同型判定に関連した問題が出ており、この辺りの理解が微妙だったのと、rng_58さんがハッシュアルゴリズムを提唱してたりして、色々あったので、色々まとめました。 木の同型判定について 木についてDFSでハッシュを求め、その比較によ…

MultiplyAddPuzzle [SRM 707 : Div1 Med]

問題 ある数sについて以下の手順をしてある数tにしたい。1. +aする 2. *bする最小のステップ数は?0

有名アプリ会社2社へのインターンとインディーズゲームアプリ開発で得た経験と成果のまとめ

殴り書きであるが、Unityを使ったゲーム開発で使えそうな知識をメモしておく。 成果物 グルーヴこねくしょん http://denbaku.com/gc/index.htmlグルーヴこねくしょん - 運と戦略の音楽ゲームKeita Imaiゲーム無料企画自体は4月から。 グルーブをつなげて、よ…

Facebook Hacker Cup 2017 Round 2 解説

問題はこっち http://hamayanhamayan.hatenablog.jp/entry/2017/01/23/014337

Facebook Hacker Cup 2017 Round 2 問題

読解に苦しむ日本人のための記事。 なんでこんなに問題が読みにくいし、長いのか。 解説はこっち http://hamayanhamayan.hatenablog.jp/entry/2017/01/23/014451

PolandBall and Gifts [Codeforces 8VC Venture Cup 2017 - Elimination Round : F]

問題 http://codeforces.com/contest/755/problem/FN人がプレゼントを持っていて、iさんがP[i]さんに渡す。 このうち、K人がプレゼントを忘れてくる。 忘れてくる任意の組合せのうち、以下のルールによりプレゼントが貰えない人数の最大・最小を答えよ。以下…

MovingTokens [SRM 705 : Div1 Med]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14471N個のトークンが1つずつ入ったビンがある。 N*Mの行列Aがあり、以下の操作がある。0 M-1 を1つ選び、j番目のビンの中身を全てA[j][i]に全てのビンで同時に移すこの操作を無限回最適な…

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

この前出たんで調べてまとめた。 結構やったので、大体わかってきたぞ やり次第逐一更新する。 再帰関数系 Codeforces Round #362 (Div. 2) D. Puzzle http://codeforces.com/contest/697/problem/D Codeforces Beta Round #62 D. Half-decay tree http://co…

競技プログラミングにおけるエラトステネスの篩問題

思いついたので、まとめました エラトステネスの篩はWikipediaが動画付きで分かりやすいです https://ja.wikipedia.org/wiki/エラトステネスの篩 本来は素数判定のアルゴリズムですが、エラトステネスっぽい感じ(主観)な問題があったので、それのまとめで…

競技プログラミングにおける二重辺連結成分分解問題まとめ

また、この前のコドフォで二重辺連結成分分解問題が出たので、勉強のためにまとめた 二重辺連結成分分解については、ARC039のDの解説である以下のスライドが詳しい http://www.slideshare.net/chokudai/arc039 Codeforces #377 F. Tourist Reform http://cod…

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

この前のコドフォでオイラー路問題が出たので、勉強のためにまとめた。 有向オイラー路 Codeforces #288 D. Tanya and Password http://codeforces.com/contest/508/problem/D 解説サイト http://kmjp.hatenablog.jp/entry/2015/01/28/0930 有向オイラー閉路…

小数から逃げる夢 [yukicoder 428]

問題 http://yukicoder.me/problems/no/428D = 0.123456789101112… 小数点以下が1から100まで順番に現れる小数Dがある。 これをN倍したものを出力せよ1

CupShuffle [yukicoder 429]

問題 http://yukicoder.me/problems/no/429N個のコップがあり、K回2つのコップを入れ替える作業を行うがが、 X回目の作業で入れ替えたコップの位置だけ分からないので、答えよ。入れ替え作業の流れは以下の通り。 最初、位置iにはコップiがある i回目の交換…

文字列検索 [yukicoder 430]

問題 http://yukicoder.me/problems/no/430文字列Sがある。 M個の文字列C[i]がある。 文字列Sの部分文字列としてC[i]が何通りあるかをM個の文字列全て調べて、その総和を答える。1 1 1

FromToDivisible [SRM 699 : Div1 Med]

問題 1~Nの番号がついているグラフがある。 ここでM組のa[i]とb[i]が与えられる。 「XからYへの辺がある」⇔「Xがa[i]の倍数かつYがb[i]の倍数」で辺がある。 このとき、始点Sから始点Tまでの最短距離は? もし到達不可能なら-12 1

Sonya and Queries [Codeforces 371 : Div1 A, Div2 C]

問題 http://codeforces.com/contest/713/problem/At個のクエリを処理する。1. + a : 自然数aをmultisetに入れる 2. - a : 自然数aをmultisetから1つ消す 3. ? s : 文字列sのパターンに当てはまる自然数aがmultisetに何個あるか出力する文字列sのパターンと…

すぬけ君の塗り絵 / Snuke's Coloring [ARC 061, ABC 045 : D]

問題 http://arc061.contest.atcoder.jp/tasks/arc061_bH行W列のマスがある。 そのうち、Nマスが黒で、他は白で塗られている。 この時、マスの中に完全に含まれる全ての3*3の連続するマス目の中の黒いマスの個数を数える。 各整数j(0 3 0