2012-01-01から1ヶ月間の記事一覧
問題 n人にアンケートをした。m個の質問に対して、 それぞれの人は0〜10までの数字を答えた。 それぞれの質問に対する答えの平均値が、 小数点以下3桁未満を切り捨てて与えられる。 このとき、nとしてありうる数は最低でいくつか、求めよ。 制約条件 m≦2500…
問題 n個の錘がある。 天秤を使って、これらの錘の重さ全てを量りたい。 n個の中からできるだけ少ない種類の錘をを選んで、n個の重さを全て量れるようにしたい。 同じ種類の錘は何個でも使うことができ、天秤のどちら側に錘をのせても良いものとする。 錘は…
問題 機械に数字を入力したい。 0〜9のキーおよび、+と-のボタンがある。 と-のボタンは表示されている数字を+1または-1する。 0〜9のキーのうち、broken[]の要素のものは壊れてしまっていて使えない。 pageの数字を入力するのに必要なボタンの押下回数の最…
問題 hxwのグリッドで表される迷路がある。 迷路の中に二人がいる。 maze[i][j]が'#'であるマスは壁で、進入することができない。 maze[i][j]が'.'であるマスは何もないマスで、進入することができる。 maze[i][j]が'P'のマス(迷路上に二つ)は、二人のスタ…
問題 行列が与えられる。 行列から、条件を満たすように成分を選ぶ。 同じ行から二つ以上の成分を選ばない 同じ列から二つ以上の成分を選ばない 上の条件を満たす選び方で、選ぶ個数が最も多くなるように選ぶ このとき、どのような成分の選び方をしても、成…
問題 ある数をひっくり返して、元の数から引く。 (例えば4321だったら4321-1234=3087, 120だったら120-21=99) この差がdifferenceであるような数のうち、最小のものを求めよ。 存在しない場合はNONEを返せ。 制約条件 difference≦1000000
問題 n人の人がいて、それぞれ白または黒どちらかの色の帽子をかぶっている。 それぞれの人に対して、「自分以外で白い帽子をかぶっている人は何人いるか」という質問をした。 質問の答えがcount[]により与えられるとき、白い帽子をかぶっている人の人数を求…
問題 n項からなる数列において、i番目の項が極値であるとは、 1<i<nかつ、a[i-1]<a[i]>a[i+1]または、a[i-1]>a[i]<a[i+1]が成り立つことを言う。 (最初の項または最後の項は極値にはならない) 数列のうち、いくつかの項が-1に置き換わったものが与え…
問題 ある数字がmirror numberであるとは、 その数字を鏡に映しても意味のある数字になっていることをいう。 数字を鏡に映すと、1は1のまま2は5に、5は2に、8は8に、0は0になり、 数字の順序が逆になる。 反転前または反転後にleading zeroがあることは許さ…
問題 n人がテーブルに座って握手をする。 それぞれの人は他のただ一人と握手する。 全員が握手をしていて、かつ手が一本も交差していないとき、握手の仕方を良いと呼ぶ。 良い握手の仕方は何通りあるか、求めよ。 制約条件 n≦50
問題 n個の発電所がある。 そのうち、最初から起動しているものはplantListによって与えられる。 すでに起動している発電所iを使って発電所jを起動させるコストconnectionCost[i][j]が与えられる。 合計でnumPlants個以上の発電所を起動させるのに必要なコス…
問題 n人がペイント球を投げる遊びをしている。 それぞれの人が所属するチームが与えられる。 また、誰が誰にボールを当てたかという情報も与えられる。 AがBにボールを当てたとき、AとBが違うチームならAに1点、Bに-1点が加わる。 AとBが同じチームなら、A…
問題 n個の数が与えられる。 これらのうちの最小値をm,最大値をMとする。 この数のうち、3個以上がその項となっているような等差数列のうち、 (初項-d)がm以下、(末項+d)がM以上となっているようなものを考える。 この等差数列の項数をq、q個のうちn個の数の…
問題 メモリに書き込みをしたい。 書き込みたいデータはn個あり、それぞれoffset[i]番地から連続してsize[i]バイトのデータを書き込みたい。 書き込みたい番地以外には、何かを書き込んでも、何も書き込まなくても良い。 一度の書き込みでは、maxPacketSize…
問題 整数nが与えられる。 整数nに非負の整数を加えて、和の各桁の数字のうちどれか一つ以上がkになるようにしたい。 最小でいくつの数を加えればよいか、求めよ。 制約条件 nの桁数≦50 k≦9
問題 折れ線とは、線分の連なりであり、それぞれの線分の始点が前の線分の終点に一致しているものをいう。 折れ線がいくつか与えられる。 折れ線同士が共有点を持つとき、それらの線分は一つの絵になっていると言う。 与えられた折れ線の集合は、いくつの絵…
問題 n人のチェスのチームが二つある。 自軍のそれぞれの人の強さはus[i]で表され、敵軍のそれぞれの人の強さはthem[i]で表される。 それぞれのチームからn人を順番に出し、勝負(強さの大きい人が必ず勝つ。強さが同じなら引き分け)をして、 勝ったら2点、…
問題 width x lengthのグリッドを、(0,0)をスタートして、 壁(グリッドの外周)にぶつかるか、今まで訪れたマスを再び訪れてしまうとき左に曲がる。 最後に訪れるマスはどこか、求めよ。 制約条件 width,length≦5000
問題 次のようなゲームがある。 最初moneyのお金を持っていて数字nから出発する。 1ドル払って、nの桁をどれか一つ小さくすることができる。(0は小さくできない) 1ドル払って、nの桁をどれか一つ大きくすることができる。(9は大きくできない) nが11の倍…
問題 n本の車線のそれぞれに車の列がある。 車は以下のようにして順に車線から出る。 同じ車線で、自分より前に車がいる車は出られない より低い番号の車線に、出ようとしている車がいる車は出られない 最初自分が車線の最初にきたら、一度だけより高い番号…
問題 n人の通行人が、幅roadWidthの道路を横断する。 それぞれの通行人について、到着時刻および、横断速度が与えられる。 車がcarArrivalの時刻に道路にやってくる。 車は、通行人の隙間の最も大きい部分がcarWidthになると道路を通過できる。 車が通過でき…
問題 単語の列が与えられる。 これをheight x widthの板に、順に書きたい。 同じ単語は同じ行に書かなければならない。 また、一行の中の単語と単語の間は一つのスペースで区切る。 最大でいくつの大きさのフォントで板に全ての単語を書けるか求めよ。 フォ…
問題 上空からスケートリンクを捉えた写真が与えられる。 この中から、チームの番号がkの人のリストを作成したい。 写真の連続する(上下または左右に隣接する、色が同じである)領域で、色がkであり、面積がthreshold以上の領域をチーム番号がkの人と認識す…
問題 Syllable sortingとは、文字列を音節に分解したものを元に文字列をソートすることを言う。 ここで、音節に分解するとは単語を、(空で無い子音が連続するものを最も長く取る)+(空で無い母音が連続するものを最も長く取る)に分割することである。 二つの…
問題 タイプミスに対するペナルティを、キーボード上での最短距離と定義する。 与えられた文字列に対して、長さが等しく、ペナルティの和が最小になるような"日付"を求めよ。 候補が複数ある場合、もっとも早い日付を答えよ。 "日付"は、月 日の形式で表され…
行列カテゴリを新たに作った。 問題 マーブルを操作する機械がグリッド上に並んでいる。 layout[i][j]が数字kであるとき、(i,j)のマスにはk番の機械があることを意味する。 機械は、機械ごとに定められた動作actions[i]を繰り返す。 actions[i]の最後までき…
問題 列車の線路がグリッドにより与えられる。 '|'のマスは縦向きの線路を表し、上下から進入して、上下に出ることができる。 '-'のマスは横向きの線路を表し、左右から進入して、左右に出ることができる。 '+'のマスは交差点の線路を表し、どの方向からも進…
問題 n問からなるコンテストがある。 コンテストはPM 6:00からAM 6:00までの間行われる。 まず最初に、10分間かけて全ての問題に目を通す。 それぞれの問題を解くのにかかる時間はa[i]である。 問題を送信すると、「AM 0:00との時刻の差の分間」ぶんだけペナ…
問題 半径Rの円の内部に、半径rの円をn個、Rの円周とrの円周が接するように置きたい。 そのような置き方が可能であればYESを、そうでなければNOを出力せよ。 制約条件 r,R≦1000 n≦100
問題 頂点が黒または白のいずれかに塗られている無向グラフで次のようなゲームを行う。 最初は白のターン 白のターンのとき、黒の頂点にかかれている数字を、隣接する白の頂点にかかれている数字の和にする。白の頂点にかかれている数字はそのままにする。 …