2013-01-01から1年間の記事一覧
問題 2次元で与えられた分数と累乗を含む式をmod2011で計算せよ。 詳しい文法はBNF記法で与えられる。 制約条件 式は20行以下 各行は80文字以下
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp) 制約条件 h, w≦30
問題 1以上n以下のn個の整数a[i]が与えられる。 a[i]は全て互いに異なる。 このa[i]に対して、m個の以下のクエリに答えよ。 整数l, rが与えられる。 l≦i, j≦rなるi, jで、a[i]がa[j]の倍数であるものの個数を求める。 制約条件 n≦200000 クエリの個数≦200000
問題 方眼紙の格子点を結んだm角形が与えられる。 このm角形の内部を、0より大きな面積含む格子の個数を求めよ。 制約条件 座標の絶対値≦100 m≦100
問題 wxhのグリッド上にn匹のスライムがいる。 1ターンにスライムのうち1匹が、以下のような動きをすることができる。 上下左右の1方向を選び、 壁にぶつかるか、他のスライムがいるマスに入るまで動く。 他のスライムのいるマスに入ると、二つのスライムは…
問題 論理変数、|, &, ~, および括弧からなるbooleanの式が与えられる。 ただし、一つの変数は、式中にただ一度しか現れない。 この式をtrueにする変数の真偽値の割り当ては何通りあるか、mod 10^9 + 7で求めよ。 式の正確な定義は問題文のBNF記法を参照。 …
問題 xのd次式f(x)がある。 f(x)に、x = 0, 1, 2, ..., d + 2を代入した結果v[0], v[1], ..., v[d + 2]が与えられる。このうち、どれか1つは間違った数字になっている。 このとき、その数字を見つけよ。 制約条件 d≦5 v[i] ≦100
問題 2レーンのプールでn人の人が泳ぐ。 それぞれのレーンは往路、復路の一方通行であり、レーンの幅は狭いため、 途中で泳いでる人を抜かすことはできない。 i番目の人は、レーンを片道泳ぐのにt[i]の時間がかかる。c[i]往復泳ぐとプールから出る。 前に、…
問題 n個の路線がある。 i番目の路線はai個の駅をつなぎ、 それぞれの駅名および、j番目とj+1番目の駅の所要時間が与えられる。 今sの駅からtの駅へ、路線を使っていきたい。 電車はどちらの向きにも使うことができるが、乗り換えには1回あたりTの時間がかか…
問題 hxwのグリッドで表される部屋がある。 Sのマスから下向きにレーザーが出る。 このレーザーを、部屋の適切なマスに鏡を置くことでGのマスに誘導したい。 鏡は'.'のマスにのみ置くことができる。 レーザーは'#'のマスは通ることができないが、Sのマスを通…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jp) 制約条件 n≦100
問題 n頂点m辺からなる重みつき無向グラフが与えられる。 これらのうち、i番目の辺(s[i], t[i])を使わないで作った最小全域木の重みを 全てのiについて求めよ。 制約条件 n≦100000 m≦200000 重みは0以上10^6以下の整数
問題
問題 hxwの土地があって、それぞれのマスはfield[i][j]で表される。 filed[i][j]が'w'のところは荒野で、 'C'のところはCurviesがいるところ、 '.'のところは何もないところである。 'w'以外の全てのマスに、線路を引く。 線路はマスの4辺のうち、2つを接…
問題 h x wのチェス盤がある。 座標(i, j)が、(i + j) % 2 = 0 を満たすマスは黒で、そうでないマスは白である。 いくつかのマスには障害物が置かれている。 チェス盤に、ちょうど3マス分のサイズのL字のブロックを置く。 ブロックは、角の部分が黒いマスに…
問題 正n多角形がある。 この多角形の頂点を折れ線で結んでいく。いま、pointsで示される頂点を結んで、pointsの最後の頂点にいる。 残りまだ訪問してない頂点を、次の条件を満たすように結ぶ。 次の頂点への線分を描くとき、今までの折れ線に交差する。 最…
問題 n個の場所が、向きのないゲレンデによってつながっている。 つながっている箇所はroad[i][j], road[j][i]がYになっている。 それぞれの場所には高さがあり、i番目の高さ≧j番目の高さのとき、 iからjに移動することができる。 今、0番目の場所からn-1番…
問題 n個の直方体の箱があり、それぞれの高さ、幅、奥行きがわかっている。 この箱のうち、好きなものを選び積み上げて塔を作る。 塔は、それぞれの箱を軸に平行に置かねばならず、 箱の底面は、一つ前の箱の底面からはみでてはならない。 箱は自由な向きで…
問題 n個の土地が円周上に並んでいる。 それぞれの土地の高さはheight[i]である。 この土地に対して次のような操作をT回行う。 heightが正であるような土地i全てについて、height[i]を1減らし、height[(i + 1) % n]を1増やす。 この操作は全て同時に行われる…
問題 座標平面上にx座標, y座標がそれぞれ全て互いに異なるN個の点がある。この点のうち、三つを取りそれらをr, g, bとする。 x[r] 制約条件 N≦300000 0≦座標の値<10^9
問題 b + a * i(i = 1, 2, .., n)で表される数列を、二進数で表現し、 初項から隙間をあけずに全部並べて書いた文字列をsとする。 この文字列に含まれる、"01"と、"10"の個数を求めよ。 制約条件 1≦a≦40000 1≦b≦10^18 1≦n≦10^12
ちょうどSRM初参加から3年、ようやくレッドコーダーになれました。 1年半くらい前から、実力的には赤になっていると言い続けていましたが、 どうしてもレートが伸び悩んで、Mediumを全部解いたりしました。 それでも1年以上赤になれなくて、本当に苦しかった…
問題 日本語なので本文参照(http://imoz.jp/data/joi/2013-sp-d3-mountain.pdf) マップから、高さがxであるような点を求める。 マップのそれぞれのマスの高さは異なる。 山の頂点のマスがある。 マップのそれぞれのマスから、頂点から遠くなるほうの隣接す…
問題 日本語なので本文参照(http://imoz.jp/data/joi/2013-sp-d3-koala.pdf)
問題 日本語なので本文参照(http://imoz.jp/data/joi/2013-sp-d1-collecting.pdf) 制約条件 N≦20 Q≦2000000
問題 あとで。眠い。 制約条件 方針 ソースコード ll a[5000]; int n, dp[5000], two[5000]; int main(){ cin >> n; rep(i, n){ cin >> a[i]; two[i] = __builtin_ctzll(a[i]); } int ans = n; rep(i, n){ dp[i] = i; rep(j, i){ ll c = a[i] >> min(two[i],…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp13Day3&pid=E) 制約条件 n≦100 m≦5000
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/contest_status.jsp?id=RitsCamp13Day1) 制約条件 n≦100 m≦10
問題 一人がn桁の数字を思い浮かべ、もう一人がその数字を当てるゲームをする。 (leading zeroがあってもよい) 当てるほうは、n桁の数字をm個言う。 それぞれに対して、自分の数字と言われた数字で、一致している桁数を答える。 言った数字と、そのときに…
問題 座標平面上にn個の円がある。 それぞれの中心は(x[i], y[i])で、半径は時間tのときtである。2個以上の円子によって囲まれた閉領域(円と円の隙間の領域のうち、閉じているもの)のうち、最も大きい時間Tに消滅するものの、消滅する時間Tを求めよ。 制約…