問題 根付き木が与えられる。 この木に対して次の操作をK回行う。 K番目の操作を行ったとき、K番目の鳥がどこかの頂点に入れる確率を求めよ。操作： 根に鳥が来る。 鳥が今いる頂点に、他の鳥がまだいなければその頂点に入って終了。 そうでない場合、子を等…

問題 hxwのグリッドがあり、それぞれ'W'（狼）または'S'（羊）か'.'（何もいない）のいずれか。 ここに仕切りを入れて、わかれた区画それぞれについて、狼と羊が同時にいることがないようにしたい。 仕切りは、好きな二列の間、または好きな二行の間に入れる…

問題 'o'または'x'からなる文字列が与えられる。 i文字目がoだった場合goodのスコアを得て、xだった場合は-badのスコアを得る。 スコアを得た時点で、今までのスコアの合計が負になった文字があれば、 その文字列全体はSPAMであり、そうでないならNOT SPAMで…

問題 n個のランプとn個のスイッチがあり、それぞれ一列に並んでいる。 i番目のスイッチを押すと、i番目のランプのオンオフが入れ替わる他、 i-1番目のランプのオンオフが入れ替わる可能性があり、 i+1番目のランプのオンオフが入れ替わる可能性がある。 どの…

問題 文字列Sが与えられる。 文字を並べ替えて文字列Tを作る。 Tのそれぞれの文字は、Sの元の場所から距離i以内の場所になければならない。 できる文字列のうち辞書順で最小のものを求めよ。 制約条件 Sの長さ≦50

問題 文字列に対して次の操作が行える。 好きなiを決める。 先頭のi文字はそのままにして、次からのL文字を、アルファベットの小さい順にソートする。 残りの文字は捨てる。 与えられた文字列Sおよび整数Lについて、 この操作を好きなだけSに適用してできる…

問題 座標平面上にn個の円がある。 原点から好きな方向にボールを投げる。 ボールは距離dの地点でバウンドし、2*dでバウンドし…とk*dでバウンドして無限に跳ぶ。円の内部または周でバウンドすると1点もらえる。 もらえる得点の最大値を求めよ。 制約条件 n≦2…

問題 n個のコップがあり、それぞれ1〜nの番号がついている。 最初順番がバラバラになって一列に並んでいる。 これに対してm回操作をした記録が与えられる。i番目の操作はx[i], y[i]により表され、 左からx[i]番目のコップにはy[i]の番号がかかれていて、 そ…

問題 n人の人がいて、この中の二人が犯人。 n人のそれぞれに犯人は誰だと思うと聞いた結果、i番目の人はa[i]とb[i]と答えた。 犯人の候補(x, y)は、x = a[i]またはy = a[i]またはx = b[i]またはy = b[i]を満たすとき、 i番目の人の同意を得られる。 最低p人…

問題 n人の人がいて、その人たちが参加したチャットの入退室のログがある。 ログはある時刻からある時刻までしか記録されていないが、その間の記録は全て含まれる。 このチャットにおいて、誰か一人でもオンラインになっているときは、 必ずその人がオンライ…

Div1のコンテストで8位だった。 けどレート130くらいしか上がらなかった… 問題 英大文字からなる入力が与えられる。 この文字を左右に反転させても同じかどうかを判定せよ。 文字列を左右反転とは、各アルファベットを鏡像反転させて、逆順に読むことを言う…

問題 長さnの文字列tが与えられる。 長さnの文字列で、tとの編集距離がちょうどiであるような文字列を 1≦i≦nなるiについて出力せよ。 制約条件 n≦25 tおよび出力する文字は英小文字からなる

問題 50人の人がいて、n日間二人ずつプレゼントが渡される。 i日目にプレゼントを渡される人はchoice1[i]およびchoice2[i]である。 プレゼントはPieまたはDolphinで、どちらが渡されるかは決まってない。 全てのプレゼントを渡し終えた後、 各人が持っている…

問題 長いケーキがある。 nの約数のうちn以外の人数の友達が来る可能性がある。 どの人数の友達が来ても、ケーキを連続する区間で同じ長さだけ配れるようにするため、 切れ目を入れておく、切れ目の数の最小値を求めよ。 制約条件 n≦100000

問題 n個の都市が双方向に通行可能な道でつながれていて、木をなしている。 ここにどの都市にいるかを検知するシステムを作る。 発信機を好きな都市に置くことができて、 受信機ではそれぞれの発信機からの距離（木における距離）を知ることが出来る。 全て…

問題 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になることがわかっている。 いま、いくつかの箱を開けて、中に入っているキャンディーの個数の合計を、…

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

問題 n頂点からなる木が与えられる。根は0番のノード。 各頂点には水槽がついている。お金をp円もっている。 最初にk個以下の好きなノードを選び、そのノードの水槽に1リットルずつ水を入れる。 次から全ての水槽が空になるまで以下の操作を繰り返す。 水槽…

問題 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番目のえさを食べる。 食べなかったえさはそのときすぐに捨てられる。 えさを食べるとアメーバは大きさが倍になる。 最初アメーバの…

問題 n組の封筒のペア(p[i], q[i])がある。 p[i], q[i]の封筒にはそれぞれ、コインが2枚ずつ入っている。 それぞれのコインは整数で表される種類がある。 n組のペアについて、高々片方の封筒を取っていく。（どちらも取らないことができる） こうして取り終…

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

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

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