問題 nxnの小正方形が並んだ正方形がある。大きな正方形の外側は黒い。 この正方形に対して以下の操作をk回行う。 一辺の長さが3以上の奇数の正方形であって、内部が全部白で、外側は黒いものを選ぶ 辺の長さをLとしたとき、内部の小正方形で(L + 1) / 2行目…
問題 n個の点(si, fi, ti)が与えられるので次のQ個のクエリに答えよ。 クエリ：点(x, y, z)に対して、最初のn個の点の中から、s≦x, f≧y, t≧zを満たす点のうち、tがもっとも小さいものの番号を答える。 ただし、最初のn点のtiは全て異なる。 制約条件 n, Q≦10…
問題 n頂点m本の辺からなる重み付き無向グラフが与えられる。 m本の辺それぞれについて、 このグラフの最小全域木に含まれる場合とそうでない場合がある このグラフの最小全域木に必ず含まれる このグラフの最小全域木に含まれない のいずれかを判別せよ。 …
問題 n枚のクッキーをd日間かけて食べる。 一日に食べてよい枚数はx枚未満。このとき、クッキーの食べ方は何通りあるか。 二つの食べ方が異なるとは、どこかの日で、二つの食べ方で食べたクッキーの枚数が異なることを言う。 制約条件 n≦2000 d≦10^20
問題 長さnの数列a[i]が与えられる。 この数列に区間[L, R]に一様に1を足すという操作を何回でも行うことができる。 ただし、一度使ったLは二度とLとして使うことができず、一度使ったRは二度とRとして使うことができない。 （[1, 1]で操作をしたら、[1, 2]…
問題 ２次元のグリッドが与えられる。 Sはスタート。.は何もないマス。数字は宝の番号で、#は壁でBは爆弾。 SからスタートしてSまで戻ってくる閉路（同じマスを二回以上通ってもよい）で、宝を囲いたい。 閉路の長さをvとして、囲った宝の価値の総和をwとす…
問題 n個の円があり、それぞれの中心はx軸上にある。 i番目の円の中心はxi, 半径はriである。 円の列C1, C2, ..., Cnは、円Ci+1がCiの真に内部に入っているときにターゲットであると言う。作れるターゲットの最大のサイズを求めよ。 制約条件 n≦100000
問題 一直線上にn個の目標があり、i番目の座標はxi. xの位置にボールを投げると、1/3の確率でx-1, x, x+1のどれかに飛ぶ。 最適な戦略を取った時、全ての目標を倒すまでのボールを投げる回数の期待値はいくつか。 前に投げたボールの結果を見て、ボールを投…
問題 i, wからなる文字列が与えられる。 この文字列から、連続する"iwi"という三文字を取り除く操作が何度でもできる。 操作ができる回数の最大値を求めよ。 制約条件 文字列の長さ≦300
問題 n個の品物があり、i番目の品物は重さがwi, 色がci, 価値がviである。 ナップサックに重さの合計がW以下, 色の合計がC色以下であるように品物を詰める。 価値の最大はいくつか。 制約条件 n≦100 W≦10000 C≦50
問題 N頂点からなる有向グラフが与えられる。 最初全ての頂点は白で、グラフにパス（同じ頂点を何度通ってもよい）を描くと、 パス上の頂点の色が全て黒になる。 この操作を２回できるとき、黒にできる頂点の個数の最大値を求めよ。 制約条件 N≦300
問題 数列aiをai = 1(i ≦ K) ai = ai-1 + ai-2 + ... + ai-K (i > K) と定義するとき、aNをmod 10^9 + 7で求めよ。 制約条件 K≦1000 N≦10^9
問題 0, 1からなるn個の文字列wiが与えられる。 wiを並べて書いた文字列で、長さがLであるものはいくつあるか。 出来る文字列が同じならば、wiの並べ方は区別しないものとする。 制約条件 答えはmod 10^9 + 7で求める n≦510 wi ≦8 L≦100
問題 N頂点からなる木に、交わらないK本のパスを書く書きかたは何通りあるか。mod 10^9 + 7で求めよ。 パスを書く順序は区別しない。 制約条件 N≦1000 K≦50
問題 英小文字からなる文字列で、 aをちょうどfreq[1]個 bをちょうどfreq[2]個… zをちょうどfreq[26]個含み、同じ文字が隣り合わないものはいくつあるか、 mod 10^9 + 7で求めよ。 制約条件 freq[i]≦10
問題 nxnのグリッドの各マスに'o'か'x'を、次の条件を満たすように入れる。 各マスについて、隣接する４マスのうち、'o'が書かれたマスは偶数個 nxnのうち、k個のマスに入るものがあらかじめ決まっているとき、 残りのマスの埋め方は何通りあるかmod 10^9 + …
問題 日本語なので本文参照（http://tenka1-2014-quala.contest.atcoder.jp/tasks/tenka1_2014_qualA_e） 制約条件 h≦20000 w≦16
問題 二つの数列が与えられる。 この数列に次の2種類の操作を行える。 両方の数列から、空でない任意のprefixを選んで削除する。ただし両方のprefixの、最後の要素は一致していなければならない。 残った数列を全て削除する。 1番目の操作にかかるコストはe,…
問題 整数x1, x2, ..., xnに対してn個の制約 l[i] ≦ xi ≦ r[i] (1≦i≦n) および、m個の制約 x[u[i]] ≦ x[v[i]] + d[i] (1≦i≦m)が与えられるとき、 Σa[i] * x[i]^2 + b[i] * x[i] + c[i]を最大化せよ。 制約条件 n≦50, m≦100 ai ≦10, bi ≦1000, ci ≦1000 -100≦…
友人が出題してた奴。 http://recruit-jinji.jp/intern2014-engineer/challenge.html これのQ2. 小文字アルファベットからなる文字列 S,Tが与えられます。 Sの部分文字列の うちTと同じ長さでTとのハミング距離が最も小さいものすべての先頭文字を、 その部…
問題 辺に重みのついた無向木が与えられる。 二つの頂点u, vについてg(u, v) = uからvへの最短パス上に含まれる辺の重みの最大値 と定義する。数列p1, p2, p3, .. pn(1≦p1≦n)に対してf(p1, p2, ..., pn)を次のように定める。 f(p1, p2, ..., pn) = min{ g(i,…
問題 無向木で表されるような島と橋が与えられる。 辺の重みが、橋を渡る時間であり、その橋を壊す時間である。（両者は等しい） 好きな島から出発し、橋を渡るか、今いる島につながっている橋を壊すかすることができる。 終了時には好きな島にいてよい。 全…
問題 n頂点からなる無向木が与えられる。最初1番の頂点だけが色つき。 この木に対して以下のクエリを処理せよ。 1 v : 頂点vに色をつける。 2 v : 頂点vに最も近い色つきの頂点の距離を出力する。 制約条件 n, クエリ≦100000
問題 フィボナッチ数のi番目をF[i]とする。 長さnの数列a[i]が与えられる。次のようなクエリがq個来るので処理せよ。 1 l r : l≦i≦rなるiに対してa[i]:=a[i] + F[i-l+1]と更新する 2 l r : l≦i≦rなるiに対してa[i]の和をmod 10^9 + 9で出力する。 制約条件 n,…
問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1151&lang=jp） 多角形の内側にそって線分を回転させて、2*PI*Rラジアンまわした後の座標を答える。 棒がつっかかったらそこで終了。
問題 n個の地域に雨を同じ量ずつ振らせたい。 雨の降らせ方はm個あって、 i番目の降らせ方ではa[i]番目の地域に2, b[i]番目の地域に0, それ以外の全ての地域に1の雨が降る。 最初、上の降らせかたで、c0, ... , ck-1の雨を降らせた。 この後、どうにかして全…
問題 カードをN枚買いたい。 最初0円もっていて、毎日のはじめにP円もらえる。 カードは一日M枚まで買えて、i枚買うのにx[i]円かかる。 カードを合計N枚買うのにかかる日数の最小値を求めよ。 制約条件 N≦100 M≦20 P≦10万 x[1]≦P
問題 日本語なので本文参照（http://kupc2014.contest.atcoder.jp/tasks/kupc2014_h）
問題 正整数n, dが与えられる。 長さnの0, 1からなる文字列を好きに出力することができる。 A, Bの二人が、この文字列のi番目, j番目に配置される。 ただし|i - j| = dとなるように置かれる。 A, Bに対して Aを左に1つ動かす Aを右に1つ動かす Bを左に1つ動…
問題 二次元平面上にn匹きつねがいて、 位置が(x[i], y[i]), パワーがd[i]. （何度でも）i番目のきつねにコスト1を支払うとそのきつねのパワーを1上げることができる。 きつねi, jは(iのパワー)+(jのパワー)がi, jのユークリッド距離以上ならば通信できる。 …
