問題 Innaは整数の配列a[i]を使って次のようなことをする。 a[i]を一列に全部書く。これをa1[i]とする。 次に、n - 1個の(a1[i] and a1[i + 1])を書く。（ただしandはビット演算のand） これをa2[i]とする。 次にn - 2個の(a2[i] and a2[i + 1])を書く…… を…

問題 n匹のバクテリアがいて、（匹？）、1〜nと番号がついている。 最初のc[1]匹が種類1,次のc[2]匹が種類2……で、全部でk種類である。 バクテリアu[i]からv[i]へまたはv[i]からu[i]へ、エネルギーを移すことがx[i]ドルで可能である。 このような関係がm個与…

問題 n行m列のグリッドにp個キャンディが置いてあって、i番目のキャンディはx[i]行y[i]列にある。 このグリッドをx回時計回りに90度、y回水平反転を、z回半時計回りに90度回転させる。 操作の後でそれぞれのキャンディは何行何列にあるか出力せよ。 制約条件…

問題 n行m列のグリッドがあって、それぞれ'*', 'G', 'S'のどれか。 '*'は何もないセルで、'G'はロボット、'S'は飴のあるセル。 一行には必ずちょうど一つずつだけ、GとSが含まれている。 号令をかけると、まだゴールしてない全てのロボットが一斉に動き出し…

問題 それぞれ'O'か'X'が描かれた12枚のカードがある。 i番目のカードにはs[i]が描かれている。 二数a, bを選び、このカードを次のように並べる。 最初のb枚を取って一列に、 次のb枚を取ってその下の列に一列に並べる…… こうして12枚のカードをa行b列に並べ…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_12） 重みつき有向グラフが与えられる。 各辺には+, -, =の3種類があって、 +の辺を通ると所持金が1円増える -の辺を通ると所持金が1円減る（所持金0のときは通れない） =の…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06） 自己辺多重辺がありうる重みつき有向グラフが与えられる。 このグラフの0番の頂点から0番の頂点へ戻る閉路（同じ辺や頂点を２度使ってもよい）の長さを、 長さが短い順…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_09） 根つき木が与えられる。 各頂点には数字がついている。 それぞれの頂点に対して、 自分の親でも子でもない頂点のうち、自分に最も数字が近い頂点の数字を答えよ。 複数…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_08） NxNの二次元グリッドに石がM個ある。 i番目の石は(x[i], y[i])にあって、強さの和がa[i]以上b[i]以下になるようレーザーを当てる。 レーザーはx軸に平行またはy軸に平行…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_07） 夏休みがM日あって、N人の掃除当番を使って、 「連続して掃除がされない日数の最大値」をなるべく小さくしたい。 i番目の人はa[i]日目〜b[i]日目のうち一日だけ掃除がで…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06） n頂点からなる無向グラフが与えられる。 最初全ての頂点は自分自身だけかならるグループで、クエリによりグループ同士をマージしていく。 グループA, Bをマージした後、…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_05） 変数がn, 節の数がm以下の乗法標準形の論理式が与えられる。 （よくある2-SATの(x1 or x2) and (~x3 or x4) and ...みたいな形という意味） この式に対して変数の割り当…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_04） 二分ヒープを表す長さnの配列a[i]がある。 二分ヒープを表す長さm（m≧n)の配列b[i]で、b[i]の後ろn個がa[i]になっているものが存在すれば、その最小のmを、なければ-1を…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_03）二つの重みなし無向グラフが与えられるので、 それを一本の辺でつなぐとき、 できたグラフの直径を最小にするようにつないだときの直径 できたグラフの直径を最大にする…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_02） うなぎ暦はy年には13 + (y - 2013)月まである。（2013年は13月、2014年は14月…） 西暦のy年m月が与えられたとき、うなぎ暦のy'年m'月に変換せよ。 制約条件 y≦10^17 m≦12…

コンテストは凄くどうでもいいとこでバグを出してハマって、 デバッグで時間を浪費してしまい、 面白いほうの問題を考察する時間がなくなってしまったのが残念だった。 問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_01） …

問題 長さnの順列p[i]が与えられる。 p[i]よりも辞書順で前にある全ての順列について、転置の総数の和をmod 10^9 + 7で求めよ。 制約条件 n≦10^6とか

問題 n頂点からなる木が与えられる。頂点には数字が記憶されていて、最初は全て0. これにq個のクエリが来るので処理せよ。 1 v x k 頂点vにxを足す。 vの子孫全てにvからの距離がdならばx - k*dを足す。 0 v 頂点vの数字をmod 10^9 + 7で答える。 制約条件 n…

問題 u(n) = n以下の最大の素数 v(n) = nより大きな最小の素数 とするとき、与えられたnに対して Σ[i = 2 to n] 1 / u(i)v(i)を既約分数の形で求めよ。 制約条件 1テストにつき500個のnが与えられる。 n≦10^9

問題 n個の数aiが与えられる。 m = a1 * a2 * ... * anとする。 mをn個の数の積b1 * b2 * ... * bnとしてあらわす方法は何通りあるかmod 10^9 + 7で答えよ。 制約条件 n≦500 ai≦10^9

問題 集合Sがperfectであるとは、任意の（同一でもよい）a, b∈Sについて、 (a xor b)∈Sとなることを言うものとする。 全ての要素がk以下であるようなSの選び方は何通りあるか、 mod 10^9 + 7で求めよ。 制約条件 k≦10^9

問題 二人がゲームをする。 n個のカードの山があって、i番目の山にはsi枚のカードが積まれていて、上から順にci1, ci2, ..., cisiである。 先手は好きな山を選んで先頭からカードを一枚、後手は好きな山を選んで底からカードを一枚引くというのをカードがな…

問題 無向グラフで頂点1から2への最短パスの総数がちょうどk通りであるような頂点数1000以下のグラフを出力せよ。 答えが複数ある場合はどれを出力してもよい。 制約条件 解の存在は保証されている。

問題 n個の大きさ、重さが全て同じ箱があって、i番目の箱は自分の上に他の箱をxi個置ける。 一つの箱のすぐ上にはちょうど一つの箱しか置けないとき、 全ての箱をなるべく少ない数の山に分けて積み上げたい。 山の最小個数はいくつか。 制約条件 n≦100

evima先生作問。 問題 n人の人がいて、それぞれの名前が与えられる。 i番目の人の名前はj番目の人のprefixであるというグラフを作る。 このグラフの頂点に以下の制約を満たすように0〜n-1の番号を振りたい。 m個のinfoが与えられて、info1[i]番の頂点はinfo2…