atcoder.jp 概要 サイズNの木が与えられる。それぞれの辺に黒、白の二色のいずれかで塗る。 次のM個の条件をすべて満たす塗り方の場合の数を求めよ。 ・頂点u~頂点vを結ぶ経路の上に、必ず1つ以上の白く塗られた辺が存在する。制約: 1 min(20, (N-1)*N/2) AC…

新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのよう…

codeforces.com 概要 Xが与えられる。lcm(a, b)=Xを満たすような(a, b)の組のうち、max(a, b)を最小化せよ。制約： 1

atcoder.jp 概要 長さNの相異なるバイナリ列、S, Tを考える。C[]という長さNの配列が与えられる。Sのi(1-idx)桁目を変更するとき、C[i]*(変更直前のS xor Tの立ってるbit数)だけのコストがかかる。次のようにf(S, T)を定める。 SをTと一致させるときにかかる…

atcoder.jp 概要 N個のスライムがあり、それぞれの位置はx[i]である。次の操作をN-1回行う。 残ってるスライムのうち、一番右を除いたのを等確率で1つ選び、それを一つ右に相当するスライムのところまで移動する。そして、その2つのスライムを合体させて1つ…

atcoder.jp 概要 数直線上にN匹のカエルがいて、それぞれx_i(>0)にいる。次の操作を、カエルが残ってる限り好きな回数行える。 数直線上にいる任意のカエルがx_iにいるとき、それを選んで、(x_i)-1 or (x_i)-2に動かす。ただし、動かす先に別のカエルがいる…

有向グラフの最短距離は、 負の辺が存在しないのならば、「ダイクストラ法」 負の辺が存在するならば、「ベルマンフォード法」、「ワーシャルフロイド法」 がこれを求めるアルゴリズムとして知られていて、そのうち、「ダイクストラ法」がこの3つの中で唯一E…

atcoder.jp 概要 任意の自然数r, cを使って、(i==r && j = c)の部分を1円をかけて塗ることができる。 N*Nのグリッドが与えられて、そのうちのいくつかが既に塗られてるかもしれない。既に塗られたものに上書きにして塗ってもよい。 この時、全部塗り切るのに…

codeforces.com 概要 nが与えられる。[1, n]の区間に、n人の人が立っている。彼らの座標は、重複しうる。 それぞれの人は、その場にとどまるor座標を-1するor座標を+1することができる。x=1にいる人はx=0に、x=nにいる人は、x=n+1に行くこともできる。これら…

codeforces.com 概要 次の問題をt回解け。 長さnの数列aが与えられる。それの空でない連続部分列のうち、(最大値)-(最小値)>=(連続部分列の長さ)になってるのならば、aはよい数列とする。例えば[1, 1, 4, 5, 1, 4]は[1, 4, 5, 1]は5-1>=4を満たすので、[1, 1…

Problem - D - Codeforces 概要 ある機械を買った。その機械には長さnの、各項が相異なる自然数列が存在する。この機械は、k個の相異なる、[1, n]の数字を入れて、それをaの添え字としたとき、それのk個のaの要素のうち、小さい方から見てm番目の添え字と値…