友人が出題してた奴。 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のユークリッド距離以上ならば通信できる。 …

問題 テトリスのL字ブロック ■ ■ ■■ ■ ■ ■■を両方少なくとも1回ずつ使って、nxmの長方形のフィールドを隙間なく埋めることができるかを判定せよ。 ブロックは回転させてもよいが、反転させたり、重ねたり、フィールドの外に出したりしてはならない。 制約条…

問題 0, 1のみからなる長さの同じ二つの文字列s, tが与えられる。 s, tに長さが等しく、sからのハミング距離がd1で、tからのハミング距離がd2であるような文字列はいくつあるか。 mod 10^9 + 7で求めよ。 制約条件 s ≦10^5

問題 A, BがいてAが数列a[i], Bが数列b[i]を持っている。 a[i]の長さはn, b[i]の長さはmである。 a[x[i]] = b[y[i]]という関係x[i], y[i]がc個与えられる。 二人が一緒に数を書いていく。 Aはk回目にa[k % n]を書いて、Bはk回目にb[k % m]を書く。 二人の数…

問題 1以上1000以下の整数の秘密の数を当てる。 質問は200回まですることができて、質問では、 好きな自然数xに対して、秘密の数がxの倍数かどうかを聞くことができる。 秘密の数を当てよ。

問題 日本語なので本文参照（http://kupc2014.contest.atcoder.jp/tasks/kupc2014_a）

問題 日本語なので本文参照（http://kupc2014.contest.atcoder.jp/tasks/kupc2014_k） 文字列s1, s2, ... snの中のうち、文字列tを連続する部分文字列として含むものの個数をkとする。k * |t|の最大値を求めよ。 制約条件 n≦10^5 Σ|si|≦10^5

問題 文字列sが与えられる。次のようなクエリq個に答えよ。sの連続する部分文字列で、文字列x, yをともに連続する部分文字列として含むような文字列のうち、長さが最小のものの長さを出力せよ。 そのような文字列が存在しない場合-1を出力せよ。 x, yはオー…

問題 n個の図形が与えられる。 それぞれの図形は半径r[i], 中心が(x[i], y[i])の円か、 それぞれの頂点が(x[i_0], y[i_0])..., (x[i_k-1], y[i_k-1])k[i]角形どちらか。 この図形の凸包の長さを求めよ。 制約条件 n≦100 k[i]≦10 答えは小数点以下6桁まで出力…