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

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

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

問題 ロボットが座標平面の原点にいる。 好きな歩数を動くことができて、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の行…

問題 nxnのグリッドに白石'o'と黒石'x'が置かれている。 何も置かれていない場所は'.' 辺を共有する白石はひとかたまりとみなす。 ひとかたまりの白石が、何も置かれていない場所に隣接していない状態になると、 その白石は全て'.'に変わる。黒石を好きなだ…

問題 動物がn匹いて、2チームに振り分けてリレーをする。 それぞれの動物は、自分の区間をA[i]秒以上B[i]秒以下のどれかの時間で走る。 二つのチームの走行時間の差の最大値が最小になるようなチーム分けにおける、 走行時間の差の最大値を求めよ。 制約条件…

問題 Hex格子上の図形が与えられる。 隣り合う格子を必ず違う色で塗るとき、図形のすべての格子に色をつけるためには何色必要か求めよ。 制約条件 図形は50x50に収まる

問題 長さnの01からなる文字列が与えられる。 この文字列に大して以下の操作を行うことができる。 任意の1文字の0,1を反転する 先頭からk*m文字の0,1を反転する（ただしkは任意の自然数） 操作を終えたあと、文字列の先頭からn-m文字の部分文字列と、末尾か…

問題 R, G, Bのどれかの色をした歯車がn個ある。 同じ色をした歯車は、すべて同じ向きに回転している。 歯車のうち、いくつかは噛み合っていて、噛み合っている歯車は必ず反対向きの回転をしている。 同じ色をした歯車同士が噛み合っていることはない。 この…

問題 英小文字からなる文字列が与えられる。 文字列に対して、文字x, yを選び、文字列に現れるすべてのxをyに置換することができる。 このときにかかるコストはxが現れている回数である。 この操作を繰り返し行い、文字列を回文になるようにしたい。 かかる…

問題 n頂点からなる無向完全グラフで表される都市と道がある。 ここに雨がふって、それぞれの道がroads[i][j] / 8の確率で残り、 それ以外の確率で破壊される。 残った道が、木になっている確率を求めよ。 制約条件 n≦16

問題 正の整数a, b, cが与えられる。 a + b = cが成り立つように、それぞれの数字を 数字を一つ削除するごとにコストdelCost 数字を一つ挿入するごとにコストinsCost 数字を一つ置換するごとにコストrepCostで、 何回でも削除、挿入、置換ができる。 ただし…

問題 n個のドアがある。 i番目のドアを開けるのに、赤の鍵がdoorR[i]個、緑の鍵がdoorG[i]個必要である。 i番目のドアを開けると、（最初の一回だけ） 赤の鍵がroomR[i]個、緑の鍵がroomG[i]個、白の鍵がroomW[i]個得られる。 一度使った鍵は壊れるのですぐ…

問題 n個の歌があり、それぞれの歌の長さはduration[i], トーンがtone[i]である。 Tの時間のうちに異なる歌をできるだけ多く歌いたい。 トーンがaである歌の直後にトーンがbの歌を歌おうとすると、|a - b|の時間の休憩が必要である。 最大でいくつの歌を歌え…

問題 n個の部屋が一直線上に並んでいる。 i個目の部屋にコンテナが置いてあるかどうかが与えられる。 部屋をいくつかの監視カメラが監視している。 全ての監視カメラは、長さLの連続する部屋を監視している。 それぞれの監視カメラが監視する部屋に重複があ…

問題 それぞれn頂点からなる木A, Bが与えられる。 この二つの木を次のようにしてつなぐ。 0, 1, ..., n - 1の順列をP[i]とする。 A[i]とB[P[i]]の間に辺を張る。 出来たグラフに大きさKの単純閉路（同じ点を二度通らない閉路）はいくつできるか。 全ての順列…

問題 うさぎがn匹いて、それぞれs[i]からt[i]の間部屋にいた。 部屋にいた時間の区間が長さ0以上の共通部分をもつうさぎは友達になった。 うさぎが全員twitter的なサービスで自己紹介を、他の全てのうさぎに見せたい。 友達の自己紹介は直接見られるが、友達…

問題 hxwの土地があって、それぞれのマスはfield[i][j]で表される。 filed[i][j]が'w'のところは荒野で、 'C'のところはCurviesがいるところ、 '.'のところは何もないところである。 'w'以外の全てのマスに、線路を引く。 線路はマスの４辺のうち、２つを接…

問題 h x wのチェス盤がある。 座標(i, j)が、(i + j) % 2 = 0 を満たすマスは黒で、そうでないマスは白である。 いくつかのマスには障害物が置かれている。 チェス盤に、ちょうど３マス分のサイズのL字のブロックを置く。 ブロックは、角の部分が黒いマスに…

問題 正n多角形がある。 この多角形の頂点を折れ線で結んでいく。いま、pointsで示される頂点を結んで、pointsの最後の頂点にいる。 残りまだ訪問してない頂点を、次の条件を満たすように結ぶ。 次の頂点への線分を描くとき、今までの折れ線に交差する。 最…

問題 n個の場所が、向きのないゲレンデによってつながっている。 つながっている箇所はroad[i][j], road[j][i]がYになっている。 それぞれの場所には高さがあり、i番目の高さ≧j番目の高さのとき、 iからjに移動することができる。 今、0番目の場所からn-1番…