数学問題

ICPC2017 国内予選 F リボンたたみ

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1621&lang=jp

2014 ICPC模擬地区予選 G - Cookie Counter

問題 n枚のクッキーをd日間かけて食べる。 一日に食べてよい枚数はx枚未満。このとき、クッキーの食べ方は何通りあるか。 二つの食べ方が異なるとは、どこかの日で、二つの食べ方で食べたクッキーの枚数が異なることを言う。 制約条件 n≦2000 d≦10^20

TopCoder SRM 596 Div1 Hard SparseFactorial

問題 nのsparce factorialを、 f(n) = n * (n - 1) * (n - 4) * (n - 9) * ……と定義する。 lo以上hi以下の整数nで、f(n)がdivisorの倍数であるものはいくつあるか、求めよ。 制約条件 lo, hi≦10^12 2≦divisor≦10^6

Codeforces 385(#226 Div2 only) C. Bear and Prime Numbers

問題 n項からなる数列x[i]が与えられる。 素数pに対してf(p)は、xのうちpの倍数であるものの個数とする。 [l, r]が与えられるので、l以上r以下の素数p全てについてf(p)の和を求めよ、 というクエリがm個くるので答えよ。 制約条件 n≦10^6 m≦50000 x[i]≦10^7 …

Codeforces 396(#232 Div1) B. On Sum of Fractions

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

Codeforces 394(#231 Div1) D. Physical Education and Buns

問題 n個の数が与えられる。自由に並べ替えてよい。 それぞれの数に対して何回でも+1または-1をすることができる。 1, -1し終えたあとで、数が非減少な等差級数になっているようにしたい。 必要な+1, -1の回数の合計の最小値はいくつか。 およびその最小値を…

Codeforces 394(#231 Div1) B. Very Beautiful Number

問題 p桁の数で、Leading zeroがなく、下一桁を一番上にもってくると元の数のx倍になるような数最小の数を求めよ。 そのような数がないときはImpossibleと答えよ。 制約条件 1≦p≦10^6 1≦x≦9

Codeforces 354C Vasya and Beautiful Arrays

問題 数列a[i]が与えられる。 それぞれの項から、引いた後0以下にならないように最大kを引くことができる。 なるべく出来た数列の最大公約数を大きくしたい。 最大値を求めよ。 制約条件 a[i]≦10^6 n≦3*10^5

bitwise 2013 04

あとで書く 問題 制約条件

Codeforces 138C (226C) Partial Sums

問題 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

Codeforces 226D (140D) The table

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

Codeforces 226C (140C) Anniversary

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

Codeforces 92B (123B) Squares

問題 二次元平面上の格子点を考える。 格子の座標を(x, y)が悪い点であるとは、与えられた整数a, bに対して x + y ≡ 0 (mod 2a)または x - y ≡ 0 (mod 2b)のいずれかを満たすことを言う。 (x1, y1)から(x2, y2)へ、隣り合う格子点通って移動したい。 このと…

Codeforces 204C. Little Elephant and Furik and Rubik

問題 英大文字からなる長さの等しい文字列a, bが与えられる。 a, bから長さの等しい、空でない連続する部分文字列x, yを取る。 x, yはその全ての候補の中から一つが等しい確率で選ばれる。 f(x, y)を、xi = yi(xのi番目の文字とyのi番目の文字が等しい)な…

UVa First Bangladeshi Contest of 2012-2013 Season Problem (D) Draw and Score

問題 二分木を根のノードから書いていく。 二分木がバランスしているとは、 根が2つの子を持ち、それぞれの子を根とする部分木の大きさが等しいことを言う。 ノードを書いた後で、どれかを根とする部分木がバランスしたとき、 スコアに1点を加算する。 (複…

TopCoder SRM 547 Div1 Medium RectangularSum

問題 幅h, 高さwのグリッドがある。 グリッドには 0 1 2 ... w-1 w w+1 w+2 ... 2w-1 ... のように数字が書かれている。 このグリッドの長方形の部分で、書かれている数字の総和がSであるような部分のうち、 最も面積が小さいものの面積を求めよ。 そのよう…

TopCoder SRM 327 Div1 Medium QuadraticEquations

問題 tについての方程式at^2 + bt + c = 0であって、 係数a, b, cが-k以上k以下の整数で、 t = (x + y * √d) / zを解の一つとして持つようなものはいくつあるか、求めよ。 制約条件 0≦k≦10^6 -1000≦x, y, z≦1000 zは0でない 1≦d≦1000

TopCoder SRM 369 Div1 Medium AbsSequence

問題 次のように定義される数列aがある。 a[0] = first a[1] = second a[i] = | a[i - 1] - a[i - 2] | (i > 1) このとき、aのx番目の要素を求めよ。 制約条件 first, second≦10^18 x≦10^18

TopCoder SRM 453 Div1 Medium TheTournamentDivOne

問題 nチームが何試合か試合をした。 同じ組み合わせのチームが何回か対戦した、または一度も対戦していないチームの組み合わせがあることがある。 試合で勝ったチームにはw点が入り、試合が引き分けだと両方のチームにd点が入る。 全てのチームの得た得点が…

UVa 12407 Speed Zones

問題 n個の層があり、i番目の層は、 y座標y = i * 100からy = (i + 1) * 100の、x軸方向に無限に伸びる帯になっている。 i番目の層を進む速度は、方向にかかわらずs[i]である。 いま、(0, 0)を出発して、(D, n * 100)の地点に到達したい。 最短でどれだけの…

PKU 3092 Non-divisible 2-3 Power Sums

問題 与えられた数nを、 n=Σ2^ni 3^miの形の和で表せ。 ただし、任意の互いに異なるi, jについて2^ni 3^miは2^nj 3^mjを割り切ってはならない。 制約条件 n<2^31

PKU 1019 Number Sequence

問題 11212312341234512345612345671234567812345678912345678910123456789101112345678910... と続く数列がある。この数列のi番目の数字を求めよ。 制約条件 i≦2147483647

UVa 11038 How many 0s?

問題 n以上m以下の整数を10進数で全て書いたとき、 書かれる0の数は合計いくつか、求めよ。 制約条件 0≦n, m<2^32

Codeforecs 185 A. Plant

問題 正三角形を、それぞれの辺で中点を取り、それらを結んで4つの正三角形に分割する、 という操作をn回繰り返す。その後で、上向きの正三角形はいくつあるか、mod 10^9 + 7で答えよ。 制約条件 n≦10^12

Codeforces 180 B. Divisibility Rules

問題 ある数が2で割り切れるかは、下一桁が2で割れるかを見ればよい。このような判別の仕方を2-typeという。 ある数が3で割り切れるかは各桁の和が3で割れるかを見ればよい。このような判別の仕方を3-typeという。 ある数が6で割り切れるかは、2-typeと3-typ…

TopCoder SRM 449 Div1 Hard StairsColoring

問題 n段の階段があり、ちょうどn枚の長方形の板でできている。 長方形の板には重なりやはみだしがない。 このようにして作れる階段を全部つくり、階段を(一つの階段は一色で)それぞれk色のどれかで塗る。 このようにして出来上がるものは何通りあるか、mo…

Codeforces 156 B. Suspects

問題 n人の容疑者がいて、それぞれは "x番の人が犯人である"または、 "x番の人は犯人でない"と主張している。 容疑者のうち、m人は本当のことを言っていることがわかっている。 このとき、それぞれの容疑者について、 確実に本当のことを言っている人にはTru…

OUPC2012 問題I Plane Division (AOJ2358)

問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2358) 制約条件 入力は全て整数 n≦20 -100≦A,B,C,D,E,F≦100 -100≦Ai,Bi,Ci≦100 Ai≠0またはBi≠0 曲線は二次曲線 同一の直線が存在しうる

OUPC2012 問題H Permutation(AOJ2357)

問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2357) 制約条件 n≦2000 c≦n i≠jならai≠aj

OUPC2012 問題L Sort (AOJ2361)

問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2361) 制約条件 n≦8 0≦c[i][j]≦10^5 cは対称行列