2011-12-01から1ヶ月間の記事一覧
問題 n個のキャンディが一列に並んでいる。 この中から食べるキャンディを一つ、次のような手順を繰り返して選ぶ。 残っているキャンディが1つ以上の間、平方数番目(1,4,9……番目)のキャンディを全て取り除く。 残ったキャンディに左から順に新しく1,2,3,……
問題 'o'または'x'からなる、長さが偶数の文字列が与えられる。 この文字列をちょうど等しい二つの部分文字列にわける。 そのような分け方は何通りあるか、求めよ。 制約条件 文字列の長さ≦40
問題 n匹のうなぎがいて、それぞれの長さはeelLengths[i]である。 このうなぎをmaxCut回以下だけ切って長さがちょうど10であるようなうなぎを出来るだけ多く作りたい。 最大でいくつ長さ10のうなぎができるか求めよ。 制約条件 n≦50 eelLengths[i]≦1000 maxC…
問題 二つの文字列がrhymeであるとは、 それぞれの文字列の後ろからk番目の母音以降の部分文字列が一致することを言う。 (母音の数がkより少ない文字列はいかなる文字列ともrhymeしない) 4*n行からなる詩がある。 n段全てがaabb型、abba型、abab型、aaaa型…
問題 n個の部屋があり、それぞれの幅、奥行き、高さが与えられる。 m種類の壁紙を使って、それぞれの部屋の壁に壁紙を貼る。 それぞれの壁紙の幅と長さと値段が与えられる。 壁紙は、横にだけつなげることができる。 一つの部屋は一種類の壁紙しか使えない。…
問題 nページの本がある。 月曜日から日曜日に読める本のページの量がそれぞれ与えられる。 月曜日から本を読み始めるとき、何曜日に本を読み終えるか求めよ。 制約条件 n≦1000 1週間に最低1ページは読める
問題 文字列がgrouped wordであるとは、 同じ種類のアルファベットの二文字の間に他のアルファベットがはさまれていないことを言う。 文字列を連続する部分文字列に区切った集合が与えられる。 元の文字列が一意に復元できるならその文字列を、 複数通りに復…
問題 36進法の数がn個与えられる。 これらの数から、ちょうどk種類のアルファベットを全て'Z'に置換する。 置換後の全ての数の和の最大値を36進法で求めよ。 制約条件 n≦50 それぞれの数の桁数≦50
問題 図のような床がある。 (1x5の板が縦に5枚並べた正方形Aと、横に5枚並べた並べた正方形がBが、平面上に ABABAB BABABA ABABAB… のように無限並んでいる)この床のx1,y1,x2,y2の長方形の領域を作りたい。 1x5の板はいくつ必要か。 板は好きなように切断…
問題 友達関係のグラフが与えられる。 友達関係は反射的(A→Bが友達ならB→Aも友達)であるが、推移的ではない(A→Bが友達かつB→Cが友達でもA→Cが友達とは限らない)。 このグラフにおいて、n-friendを以下のように定義する。 AとBが友達ならばAとBはn-friend…
問題 ターン制のゲームがある。 最初n個の工場とk人の職人がいて、毎ターンの最初にn*kのお金が入る。 priceのお金でターン終了時に工場を1つ建てるまたは職人を一人雇うことができる。 これはお金がある限り1ターンに何回でも行える。targetのお金を稼ぐの…
問題 正三角形の辺をn等分し、等分した点同士を線分で結び六角形のグリッドを作る。 グリッド上に六角形は何通り書くことが出来るか、mod 10^9+7で求めよ。 制約条件 n≦500000
問題 n本の棒があり、長さはそれぞれsticks[i]である。 これらの棒を最大C回切断した後で、K番目に長いものの長さの最大値を求めよ。 切断の前後で、棒の長さの和は等しく、切断した棒を再び切断することもできる。 また、最後の切断を終えた後で、棒はK本以…
問題 A B C D E F G六角形が7個ならんだ図形に、以下の条件を満たすように数字を書き入れる。(上のA〜Gに数字を入れる) それぞれの数字は1〜2*nの整数であり、 全て互いに異なり、かつ任意の隣合う数字a,bについてa%n≠b%nが成り立つ。 ただし、回転して重…
問題 n種類の質問をした。 何回か同じ質問をしたかもしれないが、質問に対しては"Yes"または"No"の答えが返る。 それぞれの質問に対する答えが与えられるとき、質問の仕方は何通りあるか求めよ。 制約条件 n≦9 質問の個数≦9
問題 同じ大きさをしたn個の正方形を座標平面上に、軸に平行に、かつ重ならないように置きたい。 それぞれの正方形の中心の座標は(xa[i],ya[i])または(xb[i],yb[i])のどちらかでなければならない。 正方形の一辺の長さの最大値を求めよ。 制約条件 n≦50 座標…
問題 数字からなる文字列の積を、その各桁の積とする。 数字からなる文字列がcolorfulであるとは、 (空でない)連続する部分文字列の積が、全て互いに異なることを言う。 n桁のcolorfulな文字列のうち、k番目に小さいものを求めよ。 n桁のcolorfulな文字列…
問題 '0'と'1'からなる行列が隠されている。 それぞれの行ごとの情報がrowsにより与えられる。 rows[i][j]は'0','1'はそれぞれの成分が'0','1'であることをあらわし、 '?'は未確定なことをあらわす。 列ごとの情報がcolumnsにより与えられる。 列ごとの情報…
問題 n+1個の頂点とn個の辺からなる連結なグラフを自由に作る。 次数がdの頂点にはscore[d-1]の点数がつく。 グラフ全体の点数は各頂点の点数の和である。 グラフの点数の最大値を求めよ。 制約条件 n≦50
問題 N行5列に1〜5Nまでの数字がランダムに書かれたくじがある。 当選番号が、5つ1〜5Nの中から相異なるように選ばれる。 くじに、当選番号が3つ以上書かれた行があればくじは当たりである。 くじが当たりである確率を求めよ。
問題 番号のかかれたくじがある。(leading zeroがある場合がある) このくじは、書かれた数が0または、約数の個数が奇数なら当たりである。 くじの番号を何桁か書き換えて当たりにしたい。 最小で何桁を変えなければならないか、求めよ。 制約条件 くじにか…
問題 supersum(k,n)を、 supersum(0,n)=n supersum(k,n)=Σ[i=1 to n]supersum(k-1,i) により定義する。与えられた整数n,kに対してsupersum(n,k)をmod 10^9+7で求めよ。 制約条件 n≦10^9 k≦50
問題 Johnは時間0に教室に来て、以下のことを繰り返す。 waitTimeだけ教授を待つ その間に教授が来なかったらwalkTimeだけ散歩に出かける。 教授はbestArrival以上worstArrival以下のランダムな実数の時間に教室に来る。 教授は、lateTime以上遅刻した生徒を…
問題 上側にn個の点1,2,...,nがあり、下側にn個の点1,2,...,nがある。 上側の点startDot[i]と下側の点startDot[i]が線で結ばれている。 まだ線で結ばれていない上側の点と下側の点を、ランダムに選び線で結ぶ。 全ての点を線で結んだあと、出来ている線の交…
問題 n枚のカードがある。 i枚目のカードの表にはtaro[i]の数字が書かれており、裏にはhanako[i]の数字が書かれている。 これらのカードを全て一列に並べたときに現れる数字の列は何通りあるか。 制約条件 n≦50 taro[i],hanako[i]は1〜nの整数が一度ずつ現れ…
Result 230.63 / 292.09 / Opened 82位 2037 -> 2097 簡単なのにあせってハマった。
問題 文字列が与えられる。 この文字列の連続する部分文字列で、母音の数が子音の数の2倍以下であるようなものを、goodなsubstringという。 goodなsubstringで、長さ最長のものの長さおよび、その長さのgoodなsubstringが現れる回数を求めよ。 制約条件 文字…
問題 文字列が与えられる。 これをk個以下に分割して、それぞれが回文になっているようにしたい。 回文にするために変更するアルファベットの個数の最小値を求め、回文を具体的に一通り+で区切って出力せよ。 制約条件 k≦500 文字列の長さ≦500
問題 n個の区間が与えられる。 区間のうち、他の区間に完全に含まれるようなものはいくつあるか、求めよ。 制約条件 n≦10^5 1≦区間の左端、右端≦10^9 区間の左端の値、右端の値は全て異なる
Result 494 / 976 / 1392 / 1704 / 1810 0 Hacks 14位(Out of competitionなのでノーレート)