問題 全ての頂点が格子点であるような、単純多角形で、周の長さがLであるものを考える。 これらのうち、頂点数が最も少ないものであって、それが複数あるときは 最も長い辺と短い辺の長さの差が最小であるものを求めよ。 答えには最も長い辺と短い辺の長さの…

evima先生作問。 問題 自然数A, Bが与えられる。 最初X = 1で、Xに次の操作を繰り返し適用してX = A^Bとしたい。 操作の適用回数の最小値を求めよ。 １回の操作では以下のうちどれかを適用できる。 好きな素数pを選んでX = p*Xとする Xの好きな約数dを選んで…

問題 空間上の点の集合がsubcubeであるとは、それらの点が、ある立方体の頂点の部分集合になっていることを言う。 n個の点が与えられる。 この点の部分集合のうち、subcubeであるようなものの個数を求めよ。 制約条件 n≦50 座標の絶対値≦100万

問題 世の中にはM種類の名前がある。 n個の大学があって、i番目の大学にはcount[i]人の生徒がパーティに参加する。 i番目の大学の人の名前は、一人目がfirst[i], 二人目以降は(前の人の名前) * mul[i] + add[i] mod Mという風に生成する。 パーティでは、同…

問題 A, Bが数当てゲームをする。 Aは1以上10億以下の数を思い浮かべ、Bがそれに対して質問する。 Bの質問は一つの数字の形式で、それに対して、Aは(自分の思い浮かべた数) - (Bの言った数)の絶対値を答える。 Bの質問とそれに対するそれぞれのAの答えが与え…

問題 長さnの順列Pが与えられる。（整数1〜nの順番を並べ替えたもの） これに対して、次のような操作を高々K回行うことができる。 二つの数(i, j)を選ぶ。i≦k≦jなる全てのkについて、P[k]をmax{P[k]|i≦k≦j}で置き換える。 P = {1, 7, 2, 3, 6, 4, 5} に対し…

kagamizさんが主催のコンテストに出てみた。 http://kcs.miz-miz.biz/contest/1006/problem_list 問題 日本語なので本文参照。 http://kcs.miz-miz.biz/contest/1006/view_problem/D 要約すると、最後の石を取ったら負けのNim 制約条件 石の個数の和が10^6以…

問題 自然数N, Kが与えられる。 {1, 2, ..., 2*N}の集合を互いに素なN個ずつの集合A, Bにわける。 A, Bの要素を小さい順に並べたとき、どのiについても|A[i] - B[i]| ≧ KとなるようなA, Bの選び方は何通りあるか、mod 10^9 + 7で求めよ。 制約条件 N≦50 K≦10

問題 n個のハンバーガーがあり、それぞれ種類がtype[i], 味がtaste[i]である。 この中からエイリアンに食べさせるハンバーガーを選ぶ。 エイリアンの満足度は、食べさせたハンバーガーのうち異なるtypeが何種類あるかをY 食べさせたハンバーガーの味の合計を…

問題 n個の点および凸なm角形が与えられる。 m角形の内部で、n個の点からの距離の二乗の和が最小になる場所における、 距離の二乗の和の最小値を求めよ。 制約条件 n≦10^5 m≦10^5 座標の絶対値は10^6以下

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

問題 10, 11, 00のドミノが合計でn*m個与えられる。 これらを横向きにn*m個に並べる。 それぞれの列ごとにその列の数の和を求める。 この和の最大値が、最小になるようにしたい。最小値を求めよ。 ドミノは回転させることはできるが、縦に使うことはできない…

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

問題 |||+||=|||||のようなマッチ棒を使った式が文字列で与えられる。 A+B=C（A, B, C ＞ 0）のときに正しい式である。 誤っているかもしれない式が与えられるので、棒を一本動かして正しい式に出来るならその式を、そうでないならImpossibleを出力せよ。 +,…

問題 線分の（重複）集合からなる図形が(x1[i], y1[i]), (x2[i], y2[i])により与えられる。 この図形を平面上に回転させずに、ずらして、コピーする。 どの二つのコピーも重ならないように、平面内の有限の範囲に無限に敷き詰められるか否かを判定せよ。 制…

問題 n項からなる数列A, B, Cが与えられる。 Aの先頭u項、Bの先頭v項、Cの先頭w項の和集合と、 A, B, Cの和集合が一致するような(u, v, w)について、u + v + wの最小値を求めよ。 制約条件 n≦10^5 各項≦10^9

問題 フィボナッチ数Fiは F1 = 1, F2 = 2, Fi+2 = Fi+1 + Fiであらわされる数列である。 n, kが与えられたとき、 Σ[1≦i≦n] Fi * i^kをmod 10^9 + 7で求めよ。 制約条件 n≦10^17 k≦40

問題 ハノイの塔がある。 通常のルールに加えて、軸iにささっている円盤を軸jに移動するときにcost[i][j]がかかる。 最初軸0にささっているn枚の円盤を、軸2に全て移動させるのにかかるコストの最小値を求めよ。 制約条件 n≦40 0≦cost[i][j]≦10000

すっごく久しぶりにratedのコンテストに参加。 いやなんか散々だった。 簡単なはずのAでn = 0のケースを忘れて3WA出してしまって物凄いペナルティを食らって、 Cむずいと思ってDをずっと考えてて解けずに終了して、実はC簡単だったという。 Bをせっかく２０…

問題 木が与えられる。 それぞれの頂点には最大１匹のきつねがいる。 きつねは、最終的に以下の条件を満たすように移動したい。 きつねがいる町が連結になっている 一つの町には最大一匹のきつねしかいない このとき、きつねの移動距離の総和の最小値を求め…

問題 ロボットが座標平面の原点にいる。 好きな歩数を動くことができて、i歩目の移動では上下左右のいずれかの方向に、3^iだけ移動する。 ただし途中の移動だけをスキップすることはできない。 ロボットが座標(x, y)で止まることができるかを判定せよ。 制約…

問題 長さn項の二つの数列a[i], b[i]が与えられる。 bの順序を好きに入れ替えて数列b'[i]を作る。 c[i] = a[i] + b'[i]という数列に、なるべく同じ数が出るようにbを並べ替える。 このとき、同じ数の出現回数の最大値と、その数を求めよ。 出現回数の最大値…

問題 n文字でアルファベットの最初のk種類からなる文字列A, Bのうち、 次の条件を満たす(A, B)のペアの総数をmod 10^9 + 7で求めよ。 ある文字列Cが存在し、A + C = C + Bとなる。 （ただし + は文字列の結合を表す） AまたはBが一文字でも違うとき、二つの…

問題 木が与えられる。各頂点には整数のコストが書かれている。 この木で二人が次のようなゲームをする。 二人は交互に手番を繰り返す。 手番のプレイヤーは辺を一つ選んで切断し、木を二つに分ける。一方の木を完全に消滅させる。 木が頂点一つになったら終…

問題 長方形の紙が2*n枚あり、それぞれの一辺の長さはx[i], y[i]である。 （縦横を入れ替えてもよい） この紙をn枚ずつに自由にわける。 n枚について次のような得点を考える。 xy平面上に辺が軸に平行になるよう自由に置く。 全ての紙が重なっている領域の面…

問題 Typocoderにn回参加する。 初期のレーティングはXで、i回目のコンテストで本気を出すとD[i]レーティングが上がり、 本気を出さないとD[i]レーティングが下がる。 ただし、レーティングが0未満になったときは、0になるとする。 レーティングが2200以上の…

問題 {1, 2, ..., N}の部分集合Aを選ぶ {1, 2, ..., M}の部分集合Bを選ぶ。このとき、AとBの積集合が空かつ、（Aの要素全てのxor）＜（Bの要素全てのxor）となる集合の選び方は何通りあるか。 mod 10^9 + 7で求めよ。 制約条件 N, M≦2000

問題 n個のかばんがあって、i番目のかばんにはりんごがapple[i]個とみかんがorange[i]個入っている。 ここから次のようにしてりんごとみかんを取り出す。取り出し方は何通りあるか。 自然数Xを選ぶ。 それぞれのかばんから、りんごとみかんの合計がX個になる…

問題 n個の数字が与えられる。 そこから数字をいくつか削除して、残った数字から どのように数字を選んでそれら全てのbitwise orをとってもgoalの数字にできないようにしたい。最小でいくつの数字を削除しなければならないか求めよ。 制約条件 数字≦10億 n≦50

問題 各成分が0または1の行列Aが与えられる。 Aの行のうちrowCount個以上の行が回文であり、 Aの列のうちcolumnCount個以上の列が回文になるように、 Aの成分をいくつか書き換える。書き換えなければならない最小の個数はいくつか、求めよ。 制約条件 Aの行…