問題 n個の町がn^2本の道でつながっている。 車がm個あり、それぞれの車で町iからjまで行くのにかかるコストが与えられる。 ここでr回のレースをする。 i回目のレースではsiからtiまで移動する。 この際、車をki回まで乗り換えてよい。 車は任意の町で、時間…

問題 n桁の正整数であって、 0, 1, 2... ,9の数字がそれぞれa[0], a[1], ..., a[9]回以上現れるようなものはいくつあるか、求めよ。 leading zeroは許されない。 制約条件 n≦100

問題 nxnのそれぞれのマスに数字a[i][j]が書かれたグリッドがある。 Aさんがグリッドの左上から右下まで、右か下だけに移動しながら移動する Bさんがグリッドの右下から左上まで、左か上だけに移動しながら移動する このとき、「二人の少なくともどちらかが…

問題 数列a[i]が与えられる。 数列の連続する部分列(a[i], a[i+1], ... a[j])のうち、 同一の値をk個以上含むものの個数を求めよ。 制約条件 n≦4*10^5

問題 n種類のコインを投げて、出た面を順番に記録する。 i番目のコインが表の確率はp[i]である。このとき、連続する○の大きさの二乗の総和 （たとえば○○×○××だったら、2^2 + 1^2 = 5）の期待値を求めよ。 制約条件 n≦10^5 0≦p≦1

問題 辺に文字列のついた根付き木が与えられる。 この木から文字列を以下のようにして作ることができる。 始点の(枝，枝の文字の何番目か）、終点の（枝，枝の文字の何番目か）を選ぶ。 必ず始点のほうが根に近いほうを選ぶものとする。 始点枝から終点の枝…

問題 n行m列のグリッドが与えられる。各マスは'.'または'#'である。 #のマスが連結であるとは、「どの二つの#のマスも、辺を共有するような'#'を経由してたどり着ける」ことを言う。 #が一つだけのグリッド、#が一つもないグリッドは連結であることに注意す…