問題 長さnの数列a[i]が与えられる。 aの任意の空でない区間[l, r]で、a[i]の符号を好きに反転してよい。 このようにして[l, r]内の総和が0になるようにする方法は何通りあるか。 制約条件 n≦1000 -1000≦a[i]≦1000 a[i]の総和≦10000

問題 幅w高さhのグリッドを、白黒に塗る。 左上および右下のマスは黒であり、左上から右下へ隣接する（辺を共有する）黒い正方形をたどっていけるような塗り方は何通りあるかmod 10^9 + 7で求めよ。 制約条件 w≦6 h≦100

問題 文字列sが与えられる。 sの（必ずしも連続しない）部分文字列でK番目のものを求めよ。 部分文字列は、文字列が同じならどこから切り出したかは区別しない。 K番目が存在しない場合はEelと出力せよ。 制約条件 sは英小文字からなる sの長さ≦10^6

問題 n頂点からなる木が与えられる。 この木を、辺を一本ずつ書いていく。書いている途中の辺は全て連結であるようにしたい。 辺を書く順番は何通りあるかmod 10^9 + 7で求めよ。 制約条件 n≦1000

問題 H階建ての家がある。各階は全て同じ構造をしていて、r部屋からなり、 g[i][j] = 1のとき部屋iから部屋jへ行くことができる。 また、h階の部屋iからはh-1階の部屋iへ降りることができる。（登れない） H階の部屋1から1階の部屋1まで、同じ部屋を２度通ら…

問題 nxnの小正方形が並んだ正方形がある。大きな正方形の外側は黒い。 この正方形に対して以下の操作をk回行う。 一辺の長さが3以上の奇数の正方形であって、内部が全部白で、外側は黒いものを選ぶ 辺の長さをLとしたとき、内部の小正方形で(L + 1) / 2行目…

問題 長さnの数列a[i]が与えられる。 この数列に区間[L, R]に一様に1を足すという操作を何回でも行うことができる。 ただし、一度使ったLは二度とLとして使うことができず、一度使ったRは二度とRとして使うことができない。 （[1, 1]で操作をしたら、[1, 2]…

問題 一直線上にn個の目標があり、i番目の座標はxi. xの位置にボールを投げると、1/3の確率でx-1, x, x+1のどれかに飛ぶ。 最適な戦略を取った時、全ての目標を倒すまでのボールを投げる回数の期待値はいくつか。 前に投げたボールの結果を見て、ボールを投…

問題 0, 1からなるn個の文字列wiが与えられる。 wiを並べて書いた文字列で、長さがLであるものはいくつあるか。 出来る文字列が同じならば、wiの並べ方は区別しないものとする。 制約条件 答えはmod 10^9 + 7で求める n≦510 wi ≦8 L≦100

問題 N頂点からなる木に、交わらないK本のパスを書く書きかたは何通りあるか。mod 10^9 + 7で求めよ。 パスを書く順序は区別しない。 制約条件 N≦1000 K≦50

問題 英小文字からなる文字列で、 aをちょうどfreq[1]個 bをちょうどfreq[2]個… zをちょうどfreq[26]個含み、同じ文字が隣り合わないものはいくつあるか、 mod 10^9 + 7で求めよ。 制約条件 freq[i]≦10

問題 0, 1のみからなる長さの同じ二つの文字列s, tが与えられる。 s, tに長さが等しく、sからのハミング距離がd1で、tからのハミング距離がd2であるような文字列はいくつあるか。 mod 10^9 + 7で求めよ。 制約条件 s ≦10^5

問題 N頂点からなる木A, Bがそれぞれ与えられる。 A, Bを次のようにしてつなぐ。 長さNの順列を等確率にランダムで一つ取り、これをP[i]とする。 Aのi番目の頂点とBのP[i]番目の頂点を辺で結ぶ。 こうしてできたグラフに、長さがちょうどkの単純閉路がいくつ…

問題 一列にN個のセルがある。それぞれのセルには高々1匹の狼が入る。 更に、M個の制約条件があり、 L[i]からR[i]番目（両端含む）のセルには合計で狼が2匹以下しかいないことがわかっている。 このとき、狼の入り方の場合の数をmod 10^9 + 7で求めよ。 制約…

問題 10^9行W列のグリッドがある。各セルには英小文字が書かれている。 このグリッドを（i0, j0）を左上として高さh, 幅wの長方形の一部を切り出したところ、 fragmentsで表される長方形が得られた。 グリッド全体は、長さx（1≦x≦W）の文字列を、繰り返し埋…

問題 n個の水滴滴下装置が直線上に並んでいる。 i番目の装置は0.5 + iメートルのところに設置されていて、毎秒intensity[i]滴の水滴を落とす。 ここに長さLメートルのスポンジをM枚おいて、スポンジに水滴をたらす。 スポンジは左端をちょうどxメートル（xは…

問題 n人が参加するプログラミングコンテストで、部屋の割り当てがある。 部屋の数はR = n / 20（小数点以下切り上げ）で、 次のように割り当てられる。 n人をレート順にソートする。 大きい順にR人ずつ取り、各人をR個の部屋にランダムに割り当てる。 （二…

問題 長さ2^nの数列a[i]がある。 これに以下のクエリがm個来るので処理せよ。i番目のクエリでは、0≦qi≦nなる整数qiが来る。 数列を2^qi個ずつに区切り、それぞれを反転させた後、同じ順に結合した数列を新しいa[i]とする。 クエリ毎に、操作後のa[i]における…

問題 一列にカードが並んでいて、i番目のカードの色はC[i]で与えられ、R, G, B, Wのどれか。 整数Mが与えられるとき、Wのカードに以下の条件を満たすようにR, G, Bの色を塗る塗り方は何通りあるか、mod 10^9+7で求めよ。 条件： 適当な整数Dをきめたとき、R,…

問題 h行w列の行列があって、(i, j)にはp[i][j]の数字が書かれている。 この行列の一つのセルを、p[i][j]に比例する確率で選ぶことを繰り返す。 全ての行と列について、その行、列に属するセルが一度以上選ばれる状態になったら、 操作を終了する。 操作が終…

問題 n個の遺跡があって、i番目の遺跡は種類kind[i]のものであり深さdepth[i]に埋まっている。 掘削機で遺跡を発掘することができる。 掘削機は掘る深さが一番最初にだけ自由に設定できて（途中で変更はできない）、 Dの深さでi掘ったとき、D≧depth[i]ならそ…

問題 n本のビルがあって、i番目のビルは色がC[i], 高さがiである。 このビルを一列に並べたとき、前から見て色の境界がL-1個であるような並べ方の総数を求めよ。 制約条件 n≦2500 L≦2500

問題 二つの長さnの順列A, Bに対してmagic(A, B)を、 max(A[0], B[0]) + max(A[1], B[1]) + … + max(A[n-1], B[n-1])と定義する。 magic(A, B)がk以上になるような長さnの順列A, Bは何通りあるか、求めよ。 制約条件 n≦50 k≦2500

問題 座標平面上にn個の滑車と2本の釘がある。 i番目の滑車は((i+1) * d, 0)の位置にあり、釘は(0, 0)および((n + 1) * d, 0)にある。 滑車の半径はrで、どの二つの滑車も接触しないことが保証されている。 原点の釘からもう一方の釘へ、ロープをたるまない…

問題 文字列sの回文度とは、sの空でない連続する部分文字列のうち、回文であるものの個数を言う。 英小文字と'?'からなる文字列sが与えられる。 文字列中の'?'は等確率でa-zに変化する。このとき、sの回文度の期待値を求めよ。 制約条件 sの長さ≦5000

問題 長さnの順列p[i]が与えられる。 p[i]よりも辞書順で前にある全ての順列について、転置の総数の和をmod 10^9 + 7で求めよ。 制約条件 n≦10^6とか

問題 n個の数aiが与えられる。 m = a1 * a2 * ... * anとする。 mをn個の数の積b1 * b2 * ... * bnとしてあらわす方法は何通りあるかmod 10^9 + 7で答えよ。 制約条件 n≦500 ai≦10^9

問題 集合Sがperfectであるとは、任意の（同一でもよい）a, b∈Sについて、 (a xor b)∈Sとなることを言うものとする。 全ての要素がk以下であるようなSの選び方は何通りあるか、 mod 10^9 + 7で求めよ。 制約条件 k≦10^9

evima先生作問。 問題 n人の人がいて、それぞれの名前が与えられる。 i番目の人の名前はj番目の人のprefixであるというグラフを作る。 このグラフの頂点に以下の制約を満たすように0〜n-1の番号を振りたい。 m個のinfoが与えられて、info1[i]番の頂点はinfo2…

問題 長さnの順列Pが与えられる。（整数1〜nの順番を並べ替えたもの） これに対して、次のような操作を高々K回行うことができる。 二つの数(i, j)を選ぶ。i≦k≦jなる全てのkについて、P[k]をmax{P[k]|i≦k≦j}で置き換える。 P = {1, 7, 2, 3, 6, 4, 5} に対し…