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

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

hamayanhamayan's blog

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

基礎: 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はその頂点を根とした木全体についての性質を表すdp 基本的にDFSを2回回すことで全方位木を作る。 具体的には1回目のDFSで普通の木DPを作り…

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

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

MultiplyAddPuzzle [SRM 707 : Div1 Med]

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

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

たくさんの数式 / Many Formulas [ARC 061, ABC 045 C]

問題 http://arc061.contest.atcoder.jp/tasks/arc061_a'1'~'9'から成る文字列Sがある。 この文字列に'+'を入れて正しい数式を作る。 全ての考えられる入れて作られる数式に対して和を取り、その総和を答えよ。1

しろくろチョコレート [yukicoder 421]

問題 http://yukicoder.me/problems/no/421N行M列の板チョコが与えられる この板チョコは黒チョコと白チョコが交互に市松模様状に並んでいる 以下のようにチョコを食べる1. 任意の位置からチョコを1つ選んで食べる -> 幸福度1 2. 任意の位置から黒チョコと白…

Teleporter [AGC 004 : D]

問題 http://agc004.contest.atcoder.jp/tasks/agc004_d町1~Nがある。 町1は首都。 どの町にもテレポータが1つあり、町iから町a[i]へテレポートできる。 どの町から出発してもテレポートをちょうどK回すると首都につけるようにテレポートの行き先を変える。…

AND Grid [AGC 004 : C]

問題 http://agc004.contest.atcoder.jp/tasks/agc004_c縦H横Wの透明な方眼紙が2つある。 片方は赤色で、もう片方は青色で、どちらも連結な状態で塗られている。 これら2つの重ね合わせるとどちらも塗られている所が紫色になる。 重ねあわせて紫色になってい…

Colorful Slimes [AGC 004 : B]

問題 http://agc004.contest.atcoder.jp/tasks/agc004_bN色のスライムがいる。 この時、2種類の操作を選んで行う。 飼っていない色iのスライムを選んで飼う。a[i]秒かかる 全ての飼っているスライムの色iが色i+1になる。x秒かかる 2 1

Similarity of Subtrees [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : E]

問題 http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_eS(T,d)をある木Tの深さdであるノードの個数とする。 木Tと木T'が類似しているとは、全てのdにおいてS(T,d)=S(T',d)であること。この時、ある木が与えられる。 この木の部分木のうち、類…

Parentheses [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : D]

問題 http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_d「(」と「)」から構成された文字列があり、以下の条件を満たす文字列を答えよ A回隣接する文字をスワップすると括弧の対応が取れた文字列が作れる B( 複数回答があれば、その中で文字列…

Help the Princess! [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : B]

問題 http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_b縦H,横Wの地図がある。 @ : 姫の初期位置 $ : 兵士の初期位置 % : ゴール . : 通路 # : 壁 各ステップ、姫と兵士は隣接する通路に1マスだけ進むかその場にとどまるか選択できる。 姫と…

Best Matched Pair [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : A]

問題 http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_aN個の数列がある。 これから2つ選んで積をとる。 その中で、文字列として見た時に、連続で増加している積の中で最大のものは? 連続で増加している例))2, 23, 56789 連続で増加してい…

高橋くんとホテル / Tak and Hotels [ARC 060 : E]

問題 http://arc060.contest.atcoder.jp/tasks/arc060_cN軒のホテルがある。 i軒目のホテルはx[i]の位置にある。 以下の条件を満たして移動する。 1日の移動距離はL以下 1日の終わりには必ずホテルにいる この時、Q個の以下のクエリが与えられる。 a[i]番目…

Chris and Magic Square [Codeforces 369 : Div2 B]

問題 http://codeforces.com/contest/711/problem/Bn×nの魔法陣がある。 魔法陣の数は自然数だが、1つだけ0になっており不完全である。 0に何を入れれば魔法陣として完成するか。 完成が不可能なら-1を出力せよ1

Directed Roads [Codeforces 369 : Div2 D]

問題 http://codeforces.com/contest/711/problem/Dn頂点の有向グラフがある。 全ての頂点から1本ずつ有向辺が出ている。 有向辺をひっくり返す組合せは2^n通りあるが、このうち、ループが無い組合せは何通り? 10^9+7を法として答えよ。2

Coloring Trees [Codeforces 369 : Div2 C]

問題 http://codeforces.com/contest/711/problem/Cn本の木がある。 これらの木をm種類の色で塗る。 木iは色C[i]で塗られているが、一部(C[i]=0のもの)は色が塗られていない。 塗られていない木に色を塗っていくのだが、木iに色jを塗るときはp[i][j]のインク…

Bus to Udayland [Codeforces 369 : Div2 A]

問題 http://codeforces.com/contest/711/problem/An行4列のバスの座席表がある。 'O'が空席、'X'が予約済み。 横に2つ並んで席が取れるか出力せよ。 なお、4列だが(2列)(道)(2列)であり、道をまたがっていると並んでいると言わない。 取れるなら、そこを'+'…

天下一魔力発電 [天下一プログラマーコンテスト2016 予選B : B]

問題 http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_b'('と')'から成る文字列Sがある。 カーソルは文字列の先頭から始まる。 以下の3つの処理が行えるとき、文字列Sを括弧の対応が取れた状態にする最小手数を答えよ。1. カーソルを…

チューリップバブル [yukicoder 417]

問題 http://yukicoder.me/problems/no/417頂点0~N-1から成る木がある 頂点iでU[i]の税収が得られる 各辺を通るときはC[i][j]時間かかる 頂点0からスタートして、辺を通って頂点を周り、頂点0に戻ってくる 全体にかかる時間がM時間以下での最大の税収を答え…

桁和 / Digit Sum [ABC 044, ARC 060 : D]

問題 http://arc060.contest.atcoder.jp/tasks/arc060_bf(b,n)がある n < b のとき f(b,n) = n n ≧ b のとき f(b,n) = f(b, floor(n / b)) + (n mod b) この関数はnをb進数表記したときの各桁の総和を返す関数とも言える f(B,N)=Sとなる2以上の最小のBを答…

高橋君とカード / Tak and Cards [ABC 044, ARC 060 : C]

問題 http://arc060.contest.atcoder.jp/tasks/arc060_aN枚の数が書かれたカードがある。 ここから1枚以上のカード選んで数の平均がAとなる組合せは何通り?1 1 1

旅行会社 [yukicoder 416]

問題 http://yukicoder.me/problems/no/416N頂点、M辺の無向グラフがある。 これからQ回のイベントを順に処理する。 1つのイベントで頂点Ciと頂点Diを結ぶ辺が壊される。この時、何回目のイベントで頂点1から頂点iまでが連結じゃなくなったかを出力せよ。 た…

BBuBBBlesort! [AGC 003 : C]

問題 http://agc003.contest.atcoder.jp/tasks/agc003_cN要素の数列がある。 これを2種の方法で要素を入れ替えて昇順ソートする 操作1 : 隣り合う2つの要素を選んで入れ替える 操作2 : 1つ飛ばしの2つの要素を選んで入れ替える 操作2の回数は何回でもいい。 …

Pythagorean Triples [Codeforces 368 : Div2 C]

問題 http://codeforces.com/contest/707/problem/C三辺が自然数の直角三角形の斜辺ではない辺の長さxがある。 この直角三角形の他の二辺を求めよ。1

Vasiliy's Multiset [Codeforces 367 : Div2 D]

問題 http://codeforces.com/contest/706/problem/D多重集合Aがあり、0が入っている。 これに対して、q個の以下のクエリを処理せよ。1. "+ x" Aにxを入れる 2. "- x" Aからxを消す 3. "? x" Aから1つ選んだ要素yについて、xとyのXORの最大値を出力1 1

Hard problem [Codeforces 367 : Div2 C]

問題 http://codeforces.com/contest/706/problem/Cn個の文字列が順に与えられる。 n個の文字列が辞書順昇順となるようにしたい。 各文字列はコストciで反転させることができる。 辞書順昇順とするための最小コストを求めよ。 辞書順昇順とできないなら"-1"…

DivisibleSetDiv1 [SRM 697 : Easy]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14362n要素の配列bが与えられる この時、以下の条件を満たすn要素の配列aが存在するか判定せよ 全ての要素はバラバラ(distinct)である 全ての要素は1より大きい a[i]^b[i]はp[i]で割り切…

キャンディーとN人の子供 [ARC059 : E]

問題 http://arc059.contest.atcoder.jp/tasks/arc059_c(複雑なのでリンク先を見ましょう) (結構分かりにくい)1

アンバランス [ARC059 : D]

問題 http://arc059.contest.atcoder.jp/tasks/arc059_b文字列tの連続する部分文字列のうち、アンバランスな文字列があるか判定する。 あるなら、その部分文字列を(要素番号で)示せアンバランスな文字列とは以下の条件を満たす文字列 長さが2以上 文字のう…

昇順昇順ソート [yukicoder 411]

問題 http://yukicoder.me/problems/no/411正の整数 N, K がある。 1~Nが1つずつあるN個の数列はN!通りあるが、その中で以下の条件を満たす組合せを数える 数列の先頭がK 数列について Ai > Ai+1 となるiがただ1つだけある 2 1