2011-11-01から1ヶ月間の記事一覧
問題 男女n人が一列に並んでいる。 それぞれの性別およびスキルの値が与えられる。 この列に対して、以下のような方法でペアを作れるだけ作る。 列で隣り合う男女のうち、スキルの差の絶対値が最も小さいペア(複数ある場合最も左のペア)を選び、ペアを作る…
問題 出来事がn個ある。 それぞれの出来事はl[i]日目からr[i]日目のどれかに起こった。 同じ日に2つ以上の出来事が起こることはなかった。l[i],r[i]が与えられたとき、 出来事の起き方として条件を満たすものを、どれか一通り出力せよ。 条件を満たす出来事…
問題 XxYの文字列で与えられる長方形の紙がある。 これをAxBの長方形に切る(AはXの約数かつBはYの約数でなければならない) 切ったあとの長方形について、かかれている文字が同一であるものがあってはならない。 (回転して重なるものは同一とみなす。左右…
問題 n個の都市の名前がある。 これらを一行に二つずつ、文字dで区切って並べる。 各行は全て同じ文字数でなくてはならない。(このような並べ方が存在することは保証されている) 並べた後のn/2行の文字列を、そのまま順につなげた文字列が辞書順で最小にな…
問題 ある会社の組織図が与えられる。 「自分の(直接または間接の)部下と同じ名前を持つ人」は何人いるか、答えよ。組織図の与えられ方は以下の通り。 employee ::= name. | name:employee1,employee2, ... ,employeek. name ::= 従業員の名前(文字列) …
問題 n個の部屋と,部屋と部屋を結ぶ通路m本により出来ている家がある。 虫が、m回の移動でちょうど全ての通路を通り、元の部屋へ戻ってくる。 この移動経路がm+1個の部屋番号によって与えられるとき、 m回の移動でちょうど全ての通路を通り元の部屋へ戻って…
問題 Bobはn日間メモリの商売をする。 n日目の行動は以下の形式で与えられる。 win x 2^xMBのメモリを勝ち取る。このメモリは、自分が持つか友人にタダであげるかする sell x 2^xMBのメモリを欲しがる客が来る Bobはメモリを同時に一つしか持てず、客がちょ…
問題 高さhの完全二分木がある。これに対してq個の次のようなクエリに答えよ。 add v e 頂点vにeの電荷を加える decay 木のdecay(後述)を求める。 木のdecayとは、次のようにして計算される値である。 木の葉をランダムに一つ選ぶ。木の根から、その葉まで…
問題 k人の仲間がいる。 店で買える基礎アーティファクトがn個あり、 合成によりできる合成アーティファクトがm個あり、それぞれのレシピが与えられる。 q個の購入するアーティファクトおよび購入者のリストが与えられる。 アーティファクトが合成できるよう…
問題 n匹のネズミがy=y0の直線上に一列に並んでいる。 m個のチーズがy=y1の直線上に一列に並んでいる。 それぞれのネズミおよびチーズの座標が与えられる。 ネズミは次のように動く。 最も近いチーズに向けて走る。 チーズに最初に辿り着いたネズミは、それ…
問題 切符には二つの番号(x,y)がついている。 切符がluckyであるとは、x*y=rev(x)*rev(y)が成り立つことをいう。 ただし、rev(x)は、xの数字を反転させたもので、 例えばrev(132)=231, rev(1200)=21である。 今、xとyをx≦maxx,y≦maxyとなるように決め、 (p,q…
問題 n個の都市とm本の道からなる、国がある。 道は双方向に通行可能である。 州とは、道により行き来できる都市の塊を言う。 都市と都市を結ぶトンネルを以下の条件を満たすように好きに掘ることができる。 一つの都市につながるトンネルは最大1本である。 …
問題 nxmマスのグリッドにおいて、「星」とは 1 111 1のような1の並びを言う。星は互いに一部が重なっていてもよい。nxmマス長方形の部分長方形で、星をk個以上含むものはいくつあるか、求めよ。 制約条件 n,m≦500
問題 nxnのチェス盤にm個のクイーンが置かれている。 クイーンのうち、 他の0個のクイーンの効きにあるような駒の数、 他の1個のクイーンの効きにあるような駒の数、 …… 他の8個のクイーンの効きにあるような駒の数 をそれぞれ求めよ。 制約条件 n≦10^5 m≦10…
問題 n個の頂点とn個の辺からなる連結な単純無向グラフが与えられる。 このグラフには閉路が一つだけ存在する。 それぞれの頂点の、閉路からの距離を求めよ。 制約条件 n≦3000
問題 n人の男とm人の女のうち、t人が映画に出演する。 ただし、映画に出演する男は4人以上、女は1人以上でなくてはならない。 出演者の選び方は何通りあるか、求めよ。 制約条件 n,m≦30
問題 n人の人がいて、それぞれ値t[i]をもっている。 t[i]=-t[j]であるような二人i,j(ただしi≠jとする)はペアを作ることができる。 ペアは何通りできるか求めよ。 制約条件 n≦10^5 10≦t≦10
問題 全てが大文字である 最初の一文字が小文字であり、その他の文字が大文字である 与えられた単語が、上のいずれかの条件を満たすとき、 単語のキャピタルを全て逆にして出力せよ。 満たさないときは、単語をそのまま出力せよ。 制約条件 単語は100字以下
問題 チェスに新たにビリヤード球という駒を導入する。 この駒はビショップのように動くが、盤の端で(何度でも)跳ね返ることができる。 盤の角で跳ね返った場合、元の進行方向へ戻る。 nxmのチェス盤に、互いに効きのないビリヤード球が最大いくつ置けるか…
問題 n個のボトルにそれぞれwリットルの牛乳が入っていて、それをm個のカップに同じ量ずつ分けたい。 一つのボトルから注げるカップは2つまでという制限があるとき、牛乳を同じ量ずつ分けることは可能か。 可能ならそのような分け方をどれか一通り出力し、そ…
問題 nxnマスの研究所がある。 それぞれのマスは炉(壁)もしくは通路である。それぞれの通路に最初、何人の人がいるかおよび、 いくつの避難カプセルがあるかが与えられる。 時間0に'Z'で表されるマスの炉が暴走した。 'Z'のマスから汚染が、次のような広が…
問題 m種類の写真が、それぞれa[i]枚ある。 n枚の写真を環状に並べたいが、隣り合う写真は違うものにしたい。 そのような並びが可能なら、並べ方をどれか一つ出力し、 不可能なら-1を出力せよ。 制約条件 n≦1000 m≦40
問題 集合S={a1,a2,..,ak}に対して、Sのsum of Mediansとは、 Σ[i≦k かつ i mod 5 = 3]a[i]により定義される。 最初集合Sは空である。 次のn個のクエリが与えられるので、それらに答えよ。 add x 集合Sにxを加える。この操作の時点でSにxは存在しない。 del …
問題 文字列に対しての条件がc個与えられる。 アルファベットa[i]がちょうどw[i]の整数倍個だけ含まれている ただし、同じアルファベットに対してw[i]が複数個定義されている場合、w[i]のどれかの倍数になっていればよい。 長さnの文字列で条件を満たすもの…
問題 super lucky numberとは、各桁が4または7であり、 4の現れる回数と7の現れる回数の等しいような数を言う。 与えられた数n以上の、最小のsuper lucky numberを求めよ。 制約条件 n≦10^5
問題 重み付き無向木が与えられる。 木のそれぞれのノードには宝が埋まっている。 ノード1から出発して、グラフの全部のノードを辿るように探索し、宝の埋まっているノードにたどり着いた瞬間に宝をする。 ただし、同じ辺は2度までしか通ることができない。 …
問題 n個のアイテムがある。 それぞれ、名前、class,atk,def,res,sizeが定まっている。 classはweapon, armor, orbのいずれかである。 sizeは、アイテムに宿らせることのできる精霊の数である。 k個のアイテムに宿る精霊的な何かがある。 それぞれ、名前、ty…
問題 n本のベクトルが与えられる。 それぞれのベクトルv=(x,y)に対して次のような変換を施してよい。 v1=(x,y) v2=(-x,y) v3=(x,-y) v4=(-x,-y) このとき|v[i]+v[j]|が最小となるようなi,jおよびそのときの変換を求めよ。 答えが複数あるときはどれを出力し…
問題 '('と')'からなる文字列が与えられる。 括弧が正しく対応しているかを判定せよ。 制約条件 言語はbefunge 文字列の長さ≦100
問題 文字列が与えられる。 文字列中の小文字を全て大文字にして出力せよ。 制約条件 言語はbefunge 文字列の長さ≦100 入力文字のASCIIコードは33から128