確率・期待値DP 「dp[i] := ～となる確率・期待値」でDPする とても良い資料 期待値DPの優良資料 使える知識 期待値の線形性 「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」(出典) ARC085A HSI ABC194D Journey Nターン…

uwiさんの最強まとめ エラトステネスの篩 本来は素数列挙のためのアルゴリズム 解説 rep(i,1,N) for(j=i;j 以下の問題はエラトステネスの篩以外にも上のループ構造のお陰で計算量がO(NlogN)に落ちる問題も入れてある 区間篩 「R [L,R]の区間の素数判定をする…

無向グラフへの取り組み 二重辺連結成分分解と橋 橋とはその辺をなくすと連結でなくなる辺のこと 二重辺連結成分とは橋を含まない頂点集合のこと 無向グラフを二重辺連結成分に分解する よく分かる解説 各成分内では、任意の3頂点を取ってきた時にa->b->cと…

オイラー路 無向・有向グラフ上で一筆書きをするパスのこと 存在条件があり、dfsで構築可能 参考1 参考2 問題 有向オイラー路 CF288 Tanya and Password 解説 CSA Matching Substrings 有向オイラー閉路 AOJ Kobutanukitsuneko 解説 無向オイラー路 yukicode…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題 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を答…

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

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

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