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

問題 hxwマスのグリッドがある。 一番上の列と下の列はループしてつながっていて、 右端と左端もループしてつながっている。 それぞれのマスには上下左右いずれかの向きの矢印が書かれている。 一点からスタートした人は、その矢印に従って移動することを繰…

問題 n個の都市があり、そのうち0番からm - 1番のm個の都市は特別な都市である。 これらの都市をk本の道で以下の条件を満たすように接続したい。 条件を満たす接続方法をmod 10^9 + 7で求めよ。 一つの道路は異なる二つの都市を結ぶ ひとつの二つの都市のペ…

問題 n頂点からなる無向木が与えられる。 頂点iには数字v[i]が書かれている。 この木に対して次の操作を好きなだけ行うことができる。 頂点1を含む部分木を選び、その頂点全ての数字を+1する 頂点1を含む部分木を選び、その頂点全ての数字を-1する 全ての頂…

問題 nxm行列がlovelyであるとは、行列の各行がそれぞれ単調非減少数列になっていることを言う。 今、lovelyだった行列の要素をいくつか-1に変え、 列をいくつか入れ替えた行列が与えられる。 元の行列としてありうるものをどれか一つ求め、 元の行列のi番目…

問題 n頂点からなる無向グラフが与えられる。 頂点には重みa[i]がついている。 このグラフの大きさ2*n/3以上のクリークで、 重みの和が最大になるものにおける、重みの和を求めよ。 クリークが存在しないとき、-1を返せ。 制約条件 n≦50 a[i]≦100000

問題 (x, y)（0≦x≦w, 0≦y≦h）を満たす点3点からなる三角形で、 面積が正の整数であるものの個数を求めよ。ただし、点の順序は区別するものとする。 制約条件 w, h≦4000

問題 nxnの行列がniceであるということを以下のように定義する。 行列のそれぞれの行に対して、列を重複なく一つずつ選ぶ。 このとき、列をどのように選んだとしても、選んだ成分の和が一定であるときその行列はniceである。 行列が与えられる。 いくつかの…

問題 座標平面上の点の集合pに対して、次のようにして点の集合qをつくる。 (x, y), (x+1, y), (x, y+1), (x+1, y+1)に点があるとき、 (x+0.5, y+0.5)をqに加える。 p := qとする。 座標平面上にn個の点(x[i], y[i])がある。 この点の集合は、ある集合に対し…

問題 無限に広いチェス盤がある。最初どのマスにも駒は置かれていない。 左上を(0, 0)とする。以下t回以下の操作を繰り返す。 1回目は(0, 0)にAを置く 次からはB, Aと交互に置く (x - 2, y)と(x - 1, y - 1)の2マスのうち、どちらか一方のみに今置こうとして…

問題 有向グラフが与えられる。 0番の頂点から出発して、 枝の出ている頂点のうち、もっとも番号の小さい頂点に移動することを繰り返す。 この移動で、n-1番の頂点にいけるように、 枝を好きに削除することができる。 削除しなければならない枝の本数の最小…

問題 HxWマスのグリッドがあり、それぞれのマスは'L'または'P'または'.'である。 このグリッドに、二つの互いに交わらない長方形を書き、 その中に入っている(Lの数) + (Pの数)を最大化したい。ただし、(Lの数) と (Pの数)の差の絶対値はmaxDiff以下でなくて…

問題 HxWのグリッドを'B'または'W'の色で塗る。 既に色が塗られているところはB, Wの文字が書かれていて、 そうでないマスには'?'が書かれている。 このグリッドの?のマスを全てBまたはWの色で塗り、以下の条件を満たすようにしたい。 全ての同色のマスは、…

問題 n個の建物があり、それぞれの高さはheights[i]である。 この建物を一列に並べるが、隣合う建物同士の距離は、隣合う建物のうち大きいほうの高さでなくてはならない。 列の端から端までの距離が最小になるような並べ方のうち、 辞書順で最小のものを求め…

問題 HxWのグリッドがあり、はじめ全てのグリッドは0である。 1行を自由に選んでその0, 1を反転する操作を合計Rcount回行い、 1列を自由に選んでその0, 1を反転する操作を合計Ccount回行う。 操作を行った後で、1の個数がS個になっているような、 操作の選び…

問題 少女がn人いて、i番目の少女がj番目の少女を愛しているかのグラフが与えられる。 グラフは対称ではない。 このグラフに対して以下の操作を好きなだけ行うことができる。 初期状態で、全ての少女は魔法少女ではなく、護られている少女ではない。 魔法少…

問題 座標平面の第一象限に青い点がいくつかあり、 x軸の正の部分に赤い点がいくつかある。 これらの点から青い点P, Qおよび、赤い点A, B, C, Dを選び、 三角形PADが三角形QBCを厳密に含み 角PAD, 角PDA, 角QBC, 角QCBが全て90度より厳密に小さい とき、これ…

問題 それぞれの頂点の次数が3以下の無向グラフが与えられる。 このグラフの頂点を0か1の色に塗り分けて、 すべての頂点について、その頂点につながる同じ色の頂点の数を1つ以下にしたい。 そのような塗り方を具体的に一つ求めよ。 不可能な場合は-1を返せ。…

問題 木が与えられる。 この木のそれぞれのノードを、1/2の確率で赤、1/2の確率で白に塗る。 塗り終えた後で、同じ色のノードを全て連結にするために、自由に辺を足す。 ただし、それぞれのノードに新たに追加できる辺は、 1本目は無料で、2本目以降は1ずつ…

あとで書く 問題 制約条件

問題 n階立ての建物があって、i階目にはstudents[i]人の人がいる。 Jediは一人でK人の人を倒すことができる。 x人の人が一つの階にいるとき、x/K(切り上げ）人のJediが必要である。 それぞれのstudentsを、動かさないか、上下の隣り合う階に移すことができる…

問題 n項からなる数列a[i]が与えられる。 これに対して、次のような操作を考える。 s[i] = Σ[j = 0 to i] a[j] として、a[i] := s[i]と置き換える。 この操作をk回行った後のa[i]をmod 10^9 + 7で出力せよ。 制約条件 n≦2000 a[i]≦10^9 k≦10^9

問題 二つの文字列s, tが与えられる。 任意のiに対して、sのi番目の文字を含んだ、必ずしも連続しないsの部分文字列であって、 tに一致するものが存在するか。存在するならYesを、そうでないならNoを出力せよ。 制約条件 s, tの長さ≦2 * 10^5 s, tは英小文字…

問題 '(', ')', '[', ']'からなる文字列が与えられる。 この文字列の連続する部分文字列のうち、 括弧の対応が正しいもので、'['の含まれる個数が最大であるものをどれか一つ出力せよ。 制約条件 文字列の長さ≦10^5

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581） h, wのグリッドの左上から右下まで、右または下に移動することを繰り返して到達する。 #のマスには進入できず、数字のマスに進入すると、 最初の一回だけその…

問題 nxm行列aijが与えられる。 この行列に対して、 どれか一つの列を選びその列の項全ての正負を反転させる どれか一つの行を選びその行の項全ての正負を反転させる 操作を好きなだけ行い、 全ての行について、その行の項の和が0以上 全ての列について、そ…

問題 n番目のフィボナッチ数をFiとする。 与えられた数l, r, kに対して、 Fl, Fl+1, ..., Frから異なるk個の数を選び、その最大公約数を求める。 全ての選び方のうち、最大公約数が最大になるようなときの、最大公約数をmod mで求めよ。 制約条件 l, r≦10^12…

問題 n頂点m辺からなる無向グラフが与えられる。 n頂点からなる完全グラフのうち、m辺をAliceが、 のこりの辺をBobが取る。 Aliceのグラフ中の三角形の数と、 Bobのグラフ中の三角形の数の和を求めよ。 制約条件 n, m≦10^6