問題 FoxとLissがゲームをする。Foxが先手でLissが後手である。 数直線上の格子点を二人が動く。最初Foxは0の点にいて、Lissはdの点にいる。 Foxはmov1以下の整数の距離を左右どちらにも動けて、その後でrng1以下の距離にいる相手を攻撃できる。 Lissはmov2…

問題 容量300の袋にn個の物体をつめる。 i番目の物体の大きさはitem[i]である。一つの袋には大きさの和が300以下になるように好きに物体を詰められる。 全ての物体を詰めるのに必要な袋の枚数の最小値を求めよ。 制約条件 n≦50 100≦item[i]≦300

問題 数直線上を走るロボットがいる。 最初ロボットは原点にいて、commandの文字列にしたがって動く。 i番目の文字がRのときロボットは+1, Lのときロボットは-1動く。 ロボットの座標が-A未満になるときまたはBより大きくなるときには命令は無視される。 (A,…

問題 n頂点からなる有向グラフが与えられる。 整数Lに対して、このグラフ上の長さLのウォークの個数がO(L^k)で抑えられるような最小のkを求めよ。 そのようなLが存在しないとき、は-1を返せ。 制約条件 n≦50 長さlのウォークとは、グラフの頂点の列v1, v2, .…

問題 n個の箱があり、i番目の箱には最小でlow[i]個、最大でhigh[i]個のキャンディーが入っている。 全ての箱に入っているキャンディーの数を合計するとCになることがわかっている。 いま、いくつかの箱を開けて、中に入っているキャンディーの個数の合計を、…

問題 n個の店があって、i番目の店はfirst[i]日目に開店する。 i番目の店はred[i]個の赤い玉、green[i]個の緑の玉、blue[i]個の青い玉を持っていて、 first[i]日目から連続して、一日に一つずつを売り、全ての玉を売ったら閉店する。 同じ日に３つ以上の店が…

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

問題 N個の都市があり、n本の双方向に通行可能な道路で結ばれている。 i番目の道路はA[i]とB[i]を結んでいて、長さがD[i]である。 0番の都市からN-1番の都市へ、長さがちょうどTになるように道を通っていくことが出来るかを判別せよ。 制約条件 n, N≦50 D[i]…

問題 アメーバに、n個のえさを順に与える。 i番目のえさがアメーバと同じ大きさのとき必ず、かつそのときに限りアメーバはi番目のえさを食べる。 食べなかったえさはそのときすぐに捨てられる。 えさを食べるとアメーバは大きさが倍になる。 最初アメーバの…

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

問題 n頂点からなる無向木が与えられる。 各辺には重要か重要でないかと、初期状態でオンかオフかが与えられる。 木の二頂点を選び、その頂点を結ぶ最短パス上にある辺全てのオンオフを入れ替えるという操作を繰り返し、 重要な辺全てをオンであるようにした…

問題 環状にn個の駅がある。 i番目の駅は、距離がrange[i]以下の、前と後ろの駅全てに対して直通の電車が走っている。 startCity番の駅からendCity番の駅まで、最低何本の電車に乗ればいけるか求めよ。 制約条件 n≦50 range[i]≦50

問題 n個の言語をマスターしたい。 最初はすべてレベル0で、9になったらマスター。 m個の講習を受けることができて、i番目の講習は、 言語a[i]のレベルがb[i]以上のときに、言語c[i]のレベルをd[i]まで上げることができて、e[i]の時間がかかる。 全ての言語…

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

問題 n人の人がいて、isFriend[i][j]が'Y'であるときi, jは友達同士である。 （i, jが友達のときj, iも友達である） 友達同士の所持金の差はd以下である。 このとき、n人の中で、所持金の最大値と最小値の差は、最大でいくらになるか。 最大値が存在しないと…

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

問題 n項からなる数列aがある。 これに対してn項からなる数列P={P[0], P[1], ...,P[n-1]}で表される操作を行うと、 a[0] := a[0] * P[0] + a[1] * P[n-1] + a[2] * P[n-2] + … a[1] := a[0] * P[1] + a[1] * P[0] + a[2] * P[n-1] + … …のように変化する。 …

問題 二つの長さ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

問題 R, G, Bどれかの色をしたボールがn個あり、i個目の色はS[i]である。 このボールをテーブルの上に1番目から順に一列に並べていく。 i番目のボールを置くとき、これまで並べたボールの両端または好きな隙間に入れることができる。 新しいボールの左側にあ…

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

問題 ダイアル式のロックがある。 現在表示されている数字はsで、これをtにしたい。 一回の操作では、それぞれの数字を+1または-1することができて、9を+1すると0, 0を-1すると9になる。 また、連続している位置にある数字は同じ回転ならいくつでも同時に操…

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

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

問題 全ての頂点が格子点であるような、単純多角形で、周の長さがLであるものを考える。 これらのうち、頂点数が最も少ないものであって、それが複数あるときは 最も長い辺と短い辺の長さの差が最小であるものを求めよ。 答えには最も長い辺と短い辺の長さの…

evima先生作問。 問題 自然数A, Bが与えられる。 最初X = 1で、Xに次の操作を繰り返し適用してX = A^Bとしたい。 操作の適用回数の最小値を求めよ。 １回の操作では以下のうちどれかを適用できる。 好きな素数pを選んでX = p*Xとする Xの好きな約数dを選んで…

問題 空間上の点の集合がsubcubeであるとは、それらの点が、ある立方体の頂点の部分集合になっていることを言う。 n個の点が与えられる。 この点の部分集合のうち、subcubeであるようなものの個数を求めよ。 制約条件 n≦50 座標の絶対値≦100万

問題 世の中にはM種類の名前がある。 n個の大学があって、i番目の大学にはcount[i]人の生徒がパーティに参加する。 i番目の大学の人の名前は、一人目がfirst[i], 二人目以降は(前の人の名前) * mul[i] + add[i] mod Mという風に生成する。 パーティでは、同…

問題 A, Bが数当てゲームをする。 Aは1以上10億以下の数を思い浮かべ、Bがそれに対して質問する。 Bの質問は一つの数字の形式で、それに対して、Aは(自分の思い浮かべた数) - (Bの言った数)の絶対値を答える。 Bの質問とそれに対するそれぞれのAの答えが与え…

問題 長さ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} に対し…

問題 自然数N, Kが与えられる。 {1, 2, ..., 2*N}の集合を互いに素なN個ずつの集合A, Bにわける。 A, Bの要素を小さい順に並べたとき、どのiについても|A[i] - B[i]| ≧ KとなるようなA, Bの選び方は何通りあるか、mod 10^9 + 7で求めよ。 制約条件 N≦50 K≦10