問題 長さnの数列a[i], b[i]が与えられる。 長さnmの対応の取れた括弧の列を書く。i番目に開き括弧を書くときコストa[i % n]が、 i番目に閉じ括弧を書くときコストb[i % n]がかかる。 長さnmの括弧の列を書く最小のコストを求めよ。 制約条件 n≦20 m≦10^7

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

問題 n枚のクッキーをd日間かけて食べる。 一日に食べてよい枚数はx枚未満。このとき、クッキーの食べ方は何通りあるか。 二つの食べ方が異なるとは、どこかの日で、二つの食べ方で食べたクッキーの枚数が異なることを言う。 制約条件 n≦2000 d≦10^20

問題 数列aiをai = 1(i ≦ K) ai = ai-1 + ai-2 + ... + ai-K (i > K) と定義するとき、aNをmod 10^9 + 7で求めよ。 制約条件 K≦1000 N≦10^9

問題 nxn行列が与えられる。 この行列から以下の条件を満たすようにいくつか要素を選ぶ。 ・それぞれの行の中に選んだ要素が奇数個ある ・それぞれの列の中に選んだ要素が奇数個ある ・選んだ要素の積が平方数である 要素の選び方は何通りあるか、mod 10^9 +…

問題 nxnのグリッドがあって、最初(sx, sy)にいる。 最初の速度は(dx, dy)で、速度(dx, dy)で移動すると、 x' = (x + dx - 1) mod n + 1 y' = (y + dy - 1) mod n + 1に移動する。 移動の前に、今いるグリッドを(x, y)とすると、dx, dyがともに(今のターン数…

問題 'a', 'b', 'c'からなる同じ長さの文字列word1, word2が与えられる。 word1の文字一つ選び、 aならbに bならcに cならaに変えるという操作を行う。 aをbに変える操作はcosts[0]が、 bをcに変える操作はcosts[1]が、 cをaに変える操作はcosts[2]がかかる…

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

問題 m個のアルファベットからなる長さnのDNAの総数を求めよ。 ただし禁止パターンがk個あり、 禁止パターンは2文字の連続するアルファベットにより指定される。 （この順にアルファベットが出るDNAはだめだが、逆順に出るものはOK） 制約条件 n≦10^15 m≦52 …

行列カテゴリを新たに作った。 問題 マーブルを操作する機械がグリッド上に並んでいる。 layout[i][j]が数字kであるとき、(i,j)のマスにはk番の機械があることを意味する。 機械は、機械ごとに定められた動作actions[i]を繰り返す。 actions[i]の最後までき…

問題 頂点が黒または白のいずれかに塗られている無向グラフで次のようなゲームを行う。 最初は白のターン 白のターンのとき、黒の頂点にかかれている数字を、隣接する白の頂点にかかれている数字の和にする。白の頂点にかかれている数字はそのままにする。 …