貪欲法
問題 n人が参加した大会がある。 大会は2種目の得点の合計が多い人が良い順位になり、 同点の場合は、同点の間でどの順位にもなる可能性がある。 1番目の種目と2番目の種目の得点が順不同で与えられる。 自分はこの中のどれかで、合計がx点以上であることが…
問題 n行m列の行列が与えられる。 それぞれの成分の値は0以上50未満の整数であり、全ての行は異なっていて、 なおかつ可能な全ての行が含まれている。 この行列の行を以下のような手順でソートする。 それぞれの列ごとに、1〜50の順列を作成する。この順列は…
問題 A〜Zのアルファベットで表される物質がある。 最初initialで表される物質を持っている。 錬金反応を何度か起こして物質Xを作りたい。 錬金反応は最低何回起こさなければならないか、求めよ。 錬金反応は、 原料の物質->目的の物質の形式で与えられる。 …
問題 二つの数列a[i]およびb[i]が与えられる。 b[i]から数列c[i]を選び(一つの項は高々一回までしか選ぶことができない)、 すべてのiについてa[i]≦c[i]となるようにしたい。 このときΣc[i]の最小値を求めよ。 制約条件 n≦20000
問題 n本の木の棒があり、それぞれの太さはw[i], 長さはl[i]である。 この木の棒を好きな順番で機械に入れていく。 最初の一本を入れるときには1のコストがかかる。 前の棒が(w[i], l[i])であるとき、次の棒(w'[i], l'[i])が w[i]≦w'[i]かつl[i]≦l'[i]ならば…
問題 n個のランプとn個のスイッチがあり、 それぞれのランプはそれぞれ異なるスイッチただ一つにつながっている。 スイッチがOFFのとき、対応するランプもOFFである。 いま、スイッチをswitch[i]で表されるスイッチをONにしたところ、 それぞれlump[i]で表さ…
問題 英小文字からなる文字列がある。 この文字列の任意の二文字を入れ替える操作を繰り返して、文字列を回文にしたい。必要な操作の回数の最小値を求めよ。 不可能な場合は-1を返せ。 制約条件 文字列の長さ≦50 同じ文字は高々2つまでしか現れない。
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2354) 制約条件 n≦10^5 w≦10^5 -10^4≦wi≦10^4 -10^4≦vi≦10^4
問題 n個の都市からなる国があり、それぞれの都市はいくつかの双方向に通行可能な道路で結ばれている。 kingdom[i][j]が'1'のときiとjは道路で結ばれている。 いま道路を好きなだけつなぐまたは壊して、 任意の二つの都市間にパスが一つだけ存在するようにし…
問題 n個の都市が、一方通行の道でつながっている。 それぞれの都市に警察を置くコストがcosts[i]により与えられる。 全ての都市に、「その都市または、その都市へ行くことが出来る都市のどれかひとつ」に警察が置かれている状態にしたい。 この状態で、警察…
問題 最初G1枚の金貨、S1枚の銀貨、B1枚の銅貨を持っている。 これを両替をして、G2枚以上の金貨、S2枚以上の銀貨、B2枚以上の銅貨を持っている状態にしたい。 両替は、1枚の金貨を出して9枚の銀貨を貰う、 1枚の銀貨を出して9枚の銅貨を貰う、 11枚の銀貨を…
問題 米国式では日付は月/日と書き、英国式では日付は日/月と書く。 日付のリストが与えられるが、書式がどちらで書かれているか解らない。 日付は、早い順に並んでいるものとするとき、日付を全て米国式で記し、つなげた文字列を返せ。 候補が複数ある場合…
問題 一種類の物質を溶かした溶液がn種類ある。 それぞれの溶液の濃度はpercent[i]%で、質量はamount[i]グラムである。 溶液を自由に混ぜて、濃度need%の溶液を出来るだけ多く作りたい。 need%の溶液な何グラム出来るか、求めよ。 制約条件 n≦50 0≦percent[i…
問題 機械に数字を入力したい。 0〜9のキーおよび、+と-のボタンがある。 と-のボタンは表示されている数字を+1または-1する。 0〜9のキーのうち、broken[]の要素のものは壊れてしまっていて使えない。 pageの数字を入力するのに必要なボタンの押下回数の最…
問題 n問からなるコンテストがある。 コンテストはPM 6:00からAM 6:00までの間行われる。 まず最初に、10分間かけて全ての問題に目を通す。 それぞれの問題を解くのにかかる時間はa[i]である。 問題を送信すると、「AM 0:00との時刻の差の分間」ぶんだけペナ…
問題 一辺が2^iの立方体がcubes[i]個ずつある。 これを使ってheight x width x lengthの直方体を埋めたい。 直方体は隙間なく立方体に埋められている必要があり、立方体が直方体からはみ出たり、立方体同士が重なったりしてはならない。 直方体を埋めるのに…
問題 n個の単語を、幅w文字になるよう単語と単語の間に"_"を入れて一行に書きたい。 それぞれの単語と単語の間の"?"の数はなるべく均等になるようにしたい。 (すなわち、最も多い"_"と最も少ない"_"の差が1以下になるようにしたい) それが複数ある場合、辞…
問題 長さlの文字列sが、p周期であるとは、 すべての0≦i<l-pなるiについて、s[i+p]=s[i]を満たすことを言う。 A,C,G,Tからなる文字列が与えられる。 この文字列をmaxPeriod以下の周期を持つように書き換えたい。 最低でいくつの文字を書き換えなければなら…
問題 各桁の積がnに等しいような数Xのうち、桁数最小のものの桁数を求めよ。 そのような数Xが存在しないときは-1を返せ。 制約条件 n≦10^9
問題 n枚のカードがある。 このカードを、次のような機械を使ってシャッフルする。 機械を一度通すと、i番目のカードがshuffle[i]番目に来るよう並び替えられる 1〜maxShuffleの整数を等確率で一つ選び、その回数だけデッキを機械に通す その後、cardsReceiv…
問題 n匹のうなぎがいて、それぞれの長さはeelLengths[i]である。 このうなぎをmaxCut回以下だけ切って長さがちょうど10であるようなうなぎを出来るだけ多く作りたい。 最大でいくつ長さ10のうなぎができるか求めよ。 制約条件 n≦50 eelLengths[i]≦1000 maxC…
問題 36進法の数がn個与えられる。 これらの数から、ちょうどk種類のアルファベットを全て'Z'に置換する。 置換後の全ての数の和の最大値を36進法で求めよ。 制約条件 n≦50 それぞれの数の桁数≦50
問題 ターン制のゲームがある。 最初n個の工場とk人の職人がいて、毎ターンの最初にn*kのお金が入る。 priceのお金でターン終了時に工場を1つ建てるまたは職人を一人雇うことができる。 これはお金がある限り1ターンに何回でも行える。targetのお金を稼ぐの…
問題 0と1からなる文字列に対して二人が次のようなゲームをする。 手番を交互にもつ 手番のプレイヤーは1つ文字を消す 残りが2文字になったら終了 先手は、残る文字列を最小化し、後手は残る文字列を最大化する ただし、与えられる文字列には'?'があり、 そ…
問題 n匹のネズミがy=y0の直線上に一列に並んでいる。 m個のチーズがy=y1の直線上に一列に並んでいる。 それぞれのネズミおよびチーズの座標が与えられる。 ネズミは次のように動く。 最も近いチーズに向けて走る。 チーズに最初に辿り着いたネズミは、それ…
問題 n個の都市とm本の道からなる、国がある。 道は双方向に通行可能である。 州とは、道により行き来できる都市の塊を言う。 都市と都市を結ぶトンネルを以下の条件を満たすように好きに掘ることができる。 一つの都市につながるトンネルは最大1本である。 …
問題 n個のボトルにそれぞれwリットルの牛乳が入っていて、それをm個のカップに同じ量ずつ分けたい。 一つのボトルから注げるカップは2つまでという制限があるとき、牛乳を同じ量ずつ分けることは可能か。 可能ならそのような分け方をどれか一通り出力し、そ…
問題 m種類の写真が、それぞれa[i]枚ある。 n枚の写真を環状に並べたいが、隣り合う写真は違うものにしたい。 そのような並びが可能なら、並べ方をどれか一つ出力し、 不可能なら-1を出力せよ。 制約条件 n≦1000 m≦40
問題 super lucky numberとは、各桁が4または7であり、 4の現れる回数と7の現れる回数の等しいような数を言う。 与えられた数n以上の、最小のsuper lucky numberを求めよ。 制約条件 n≦10^5
問題 重み付き無向木が与えられる。 木のそれぞれのノードには宝が埋まっている。 ノード1から出発して、グラフの全部のノードを辿るように探索し、宝の埋まっているノードにたどり着いた瞬間に宝をする。 ただし、同じ辺は2度までしか通ることができない。 …