問題 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の数字のみからなる文字列が与えられる。 この数字の連続する部分文字列（ただしleading zeroがあってはならない）で、 回文かつ3の倍数であるものの個数を求めよ。 制約条件 n≦1000000

問題 長さNの配列があり、次のようなクエリが来るので処理せよ。 1 l r : {a[i]|l≦i≦r}の最小値を求める。 2 l r x : l≦i≦rなるiについて、a[i] = a[i] ^ xとする。^はbitwise xor 制約条件 N≦250000 0≦a[i], x≦65535

問題 要約不能なので元の問題文参照（http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp14Day3&pid=F） 数直線上にn個の点が左から順に並んでいて、 1番の点からn番の点まで、D回以下の移動で移動したい。 一回の移動ではi->jの好きな点…

問題 長さnの順列p[i]が与えられる。 この順列を並べ替えて、完全順列（すべてのiについて、p[i]≠iが成り立つ順列）にしたい。 並べ替えは、i番目の要素とj番目の要素をコスト|i - j| * (p[i] + p[j])かけて入れ替えることを繰り返して行う。 完全順列にする…

問題 x軸上にn本の線分がある。i番目の線分は[l[i], r[i]]である。 これらの線分に対して以下のm個のクエリに答えよ。 i番目のクエリではk[i]個の点が与えられる。それぞれの座標はx[i][j]. これらの点を一つ以上含む線分の本数を出力する。 制約条件 n, m≦3…

問題 n人がいて、それぞれ番号が1〜n番である。 全員がピストルとk発の弾をもっていて、k回つぎのことを行う。 自分以外の生存者のうち、番号がもっとも小さい人に向けて同時に銃を撃つ。 i番目の人が撃った銃は、p[i]%の確率で当たる。弾が当たった人は死ぬ…

問題 n個の都市が双方向に通行可能な道路n-1本の道路で結ばれている。 任意の二都市をつなぐパスが存在する。 道路はいくつかが壊れている。 i番の都市を選ぶと、1番の都市からi番の都市へ行くのに必要な道路がすべて修理される。 最低いくつの都市を選べば…

問題 n人がコンテストをした。全員l以上r以下の整数の得点を取った。 全員の得点の合計はsall点。上位k人の得点の合計はsk点である。 このような条件を満たす全員の得点の取り方をどれか一通り出力せよ。 解が存在することは保証されている。 制約条件 n, l,…

問題 n個の料理を順番に食べる。n番目の料理はa[i]. a[i] = 1のときはボウルで食べる。 a[i] = 2のときはボウルかプレートどちらでも食べられる。 最初綺麗なボウルをm個、プレートをk枚もっていて、 食事のたびに料理の種類に応じて、綺麗なボウルまたはプ…

問題 数直線上に駅がn個ある。i番目の駅はx[i]にある。 ここから駅をk個残してあとは廃止する。 残す駅は、全ての二つの駅間の距離の平均が最小になるようにしたい。 （Sを残す駅としたら、Σ[a, b∈S, a 駅の残し方をどれか一通り出力せよ。 制約条件 n≦3*10^…

問題 n枚の皿があって、i番目の皿の容量はa[i]リットル。 i番目の皿に水を注いで、容量を超えた分はi+1番目の皿に溢れる。（i+1番目の皿も一杯ならi+2番目に……となる） n番目の皿から溢れた水は捨てられる。 次のクエリがm個来るので答えよ。 i番目の皿にxリ…

問題 ハンバーガー一個を作るにはSがrs個, Bがrb個, Cがrc個必要である。 最初Sをns個、Bをnb個、Cをnc個持っている。 足りない材料はSを一個ps円、Bを一個pb円、Cを一個pc円で買えるが、 予算はr円。 最大でハンバーガーはいくつ作れるか求めよ。 制約条件 …

問題 二数a, bに対して次の操作ができる。 どちらか一方を2で割る（割り切れるときだけ） どちらか一方を3で割る（割り切れるときだけ） どちらか一方を5で割る（割り切れるときだけ） この操作を何度か行いa, bを等しくしたい。 必要な操作の回数の最小値は…

問題 各要素が1または2の長さnの数列a[i]が与えられる。 与えられたnの約数kについて、a[i]を周期kにするには、a[i]の要素を最低いくつ変更しなければならないか。 制約条件 n, k≦100 a[i]は1または2

問題 座標平面上に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

問題 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がともに(今のターン数…

問題 数直線上y = 0の線を、x = lからx = rまで移動したい。 n個のライトがあって、それぞれの座標は(x[i], y[i])で、 a[i]度の角度の範囲だけを照らすことができる。 移動できる部分は、線分に一つ以上のライトがかかっているところだけ。 最大でどれだけ移…

問題 n項からなる数列x[i]が与えられる。 素数pに対してf(p)は、xのうちpの倍数であるものの個数とする。 [l, r]が与えられるので、l以上r以下の素数p全てについてf(p)の和を求めよ、 というクエリがm個くるので答えよ。 制約条件 n≦10^6 m≦50000 x[i]≦10^7 …

問題 文字列sが与えられる。 文字列sのi文字目からj文字目を抜き出したものをs(i, j)とする。 s(i, j)のうち"bear"を連続する部分文字列として含むものはいくつあるか答えよ。 制約条件 sの長さ≦5000

問題 ハチミツ１バレルの値段が与えられる。i日目に売り買いするときはa[i]円。 i日目に友達にハチミツ１バレルを借りて、 その日に売り払ってa[i]円を得て、次の日にa[i+1]円払って買い戻して、 友達にハチミツと利子のc円を払う、ということを全体で一度だ…

問題 n枚のカードがあって、それぞれには1〜nの異なる整数どれかが書かれている。 何回でも次のような操作をすることができる。 残っているカードのうち連続するw枚のカードを選ぶ 数字が最小のカードを捨てる w点をもらう 操作を終えた後のカードの状態が与…

問題 有向グラフがinterestingであるとは、 多重辺が存在しない。 一つの頂点cがあり、cはほかのどの頂点へも辺があり、どの頂点からもcへの辺がある。 頂点cには一本だけ自己辺がある。 c以外の頂点は入次数、出次数ともに2である ことを言う。 多重辺の存…

問題 自然数の数列a[i]に対して次の操作を、要素が一つになるまで繰り返す。 好きなi, j（i != jかつa[i]≧a[j]）を選び、a[i]のうしろにa[j]を文字列としてくっつけて、新しくできた項をaに追加し、a[i], a[j]を削除する。 n桁の数字が与えられる。 このn桁…

問題 n問のコンテストを作る。i番目の問題の難易度はa[i]になるようにしたい。 持ってる問題はm問あって、i番目の難易度はb[i]. 問題の難易度はコスト0で小さくすることができるが、大きくすることはできない。 コンテストを開催するためには何問新たに問題…

問題 起床時刻sと睡眠時間tが与えられる。昨日の就寝時刻を求めよ。 時刻および時間はhh:mmの形で入力される。この形で出力せよ。 制約条件 hh:mmは0をつめる