問題 1234からなる長さnの文字列で、 1, 2, 3, 4のうちどれか一つ以上が、 文字列の先頭からh以内に現れ、 直前の同じ数字から常にh以内にもう一度現れ n - h番目以降に現れている ようなものの数を求めよ。 制約条件 n≦1000 h≦min(30, n)

問題 R, G, Bの色の石が2列に並んでいる。 ひとつ目の列は文字列sで表され、もうひとつの列はtで表される。 リスがsの最初の石に乗っていて、ネコがtの最初の石に乗っている。 この状態から、以下の動作を好きなだけ繰り返すことができる。 R, G, Bのどれか…

問題 文字列の集合Sが与えられる。 先手はこのうちひとつの文字列を選ぶ。これをxとする。 また、先手はアルファベットに好きな順に優先順位をつける。 後手は、Sのうちx以外の文字列を好きに並べ替える。 並べ替えたあと、xがSのなかで、他のどの文字列より…

問題 n個のボールがあり、それぞれには値v[i]と色c[i]がつけられている。 今、n個のボールから順番を保存したまま何個かのボールを抜き出して列を作る。 この列に対して、 列の最初以外かつ、直前のボールと同じ色のボールが来るたびにa * v[i]点 それ以外の…

問題 日本語なので本文参照（http://arc011.contest.atcoder.jp/tasks/arc011_4） 座標平面上で、n本の直線a[i]x + b[i]y + c[i] = 0および、 m個の点の座標と、ある整数Rが与えられる。 座標平面上の点(x, y)（|x|, |y|≦R）に対して、 最も近い直線との距離…

問題 各成分が'('または')'であるnxmの行列が、monotonusであるとは、 (1, 1)から右または下に動いて(n, m)へ辿り着いたときにできる括弧文字列が、 どのような動き方をしたとしても対応していることを言う。 monotonusであるような行列を、c[i][j]にしたが…

問題 二次元平面上の格子点を考える。 格子の座標を(x, y)が悪い点であるとは、与えられた整数a, bに対して x + y ≡ 0 (mod 2a)または x - y ≡ 0 (mod 2b)のいずれかを満たすことを言う。 (x1, y1)から(x2, y2)へ、隣り合う格子点通って移動したい。 このと…

問題 長さnの文字列sと整数i, jに対して、次の関数を定義する。 f(s, i, j) = s[i+1...j-1] + r(s[j...n]) + r(s[0...i]) ただし、+は文字列の結合を、r(s)は文字列の反転を表すものとする。 二つの文字列a, bが与えられる。 f(a, i, j) = bを満たすi, jのう…

問題 nxm行列aijが与えられる。 関数x, yを f(x, y) = Σ[i=1 to n]Σ[j=1 to m]a[i][j] * max(0, k - abs(i - x) - abs(j - y)) と定義する。 k≦x≦n - k + 1 k≦y≦m - k + 1 を満たし、f(x, y)を最小にするようなx, yの組を求めよ。 答えが複数ある場合どれを…

問題 n頂点m辺からなる無向グラフが与えられる。 また、整数kが与えられる。 グラフは、すべての頂点の次数がk以上である。 このグラフの長さk+1以上の閉路をどれかひとつ出力せよ。 答えが存在することは保証されている。 制約条件 n≦10^5 m≦10^5

問題 円周上に1〜nの数が並んでいる。 隣り合う数同士および、二つ隣の数同士が弧で結ばれている。 今、弧がどの数字とどの数字を結んでいるかが与えられる。 このとき、円周上に元の数字がどのような順で並んでいたかを復元せよ。 答えが複数ある場合はどれ…

問題 n個の都市が円上0, 1, 2, ..., n - 1, 0という順に並んでいる。 最初0の都市にいて、 1日目には1個隣の都市のどちらかに、 2日目には2個隣の都市のどちらかに、 ... とm日間移動を繰り返す。 m日の移動が終わった後に都市0にいるような移動ルートは何通…

問題 滑り台とは、座標平面上のn個の支点と、m本のパスであって、 パスは、異なる二つの支点をつないだ線分である。 滑り台のパスは交差していてはならない。 今、支点の数nと、支点と支点をつなぐパスm本が与えられる。 このパスのうち、いくつかを取り除い…