問題 待ち行列に人がどんどんやってきて、注文をして、食品を受け取って帰っていく。来た順に、「いつ来たか」と「注文してから食品を受け取るまで何分かかったか」の情報が渡されるので、列に入ってから注文まで一番待たされた人は何分待たされたか求めなさ…

(^o^)ノ TCHS09のRound 2だよー。(^o^)ノ 今日の27時からだよー。(^o^)ノ こわいよー。

問題 ミーティングの時間に遅れたり早く来たりするんだけど、全てのミーティングを同じ時間だけずらして待ち時間が最低になるようなずらしかたが何通りありますか。 解 全ての時間を同じだけずらすので、会議の待ち時間順で考えて真ん中にあるぶんだけずらす…

問題 8人でトーナメント形式の大会を行う。ある人が他のある人に勝利する確率が与えられるので、8人それぞれが優勝する確率を求めなさい。 解 n人目が決勝に出る確率 r[n] は、i人目がj人目に勝てる確率を p[i, j] とすると b = {2, 0, 6, 4}[n / 2] r[n] = …

問題 ある文字列sを無限に繰り返して列を作る。この無限列と全く同じ列を作り出す、最も短い文字列を求めよ。 解 元の文字列が繰り返しになってれば削れる。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collecti…

あぶねぇ・・・。1533 -> 1395 (-138) Easy さっと書いてぱっと提出。なかなか。 Medium 再帰でややこしく解こうとして、最終的に結局三試合しかないんだからわざわざ再帰する必要のないことに気付いた。気付いたのは大会の後。 Hard とりあえずこんな感じじ…

再帰の見本としてよく使われる階乗をJとF#で実装してみるテスト。 F#の場合 まずは普通に再帰的に実装してみる。 let rec fact = function 0 -> 1 | n -> n * fact (n-1) 次に末尾再帰の形で実装してみる。 let rec fact2 n res = if n = 0 then res else fa…

問題 縦横の和が全て等しい3*3魔方陣を作る。魔方陣の要素となる9つの整数が与えられるので、作ることのできる魔方陣が何通りあるか求めなさい。 解 next_permutationゲー。C#にも欲しいです＞＜ using System; using System.Text; using System.Text.Regula…

問題 トランプの山から隣あった数の和が13になるものとKのカードを取り除いていく。最後に何枚のカードが残るか。 解 山の一番最後と一番最初でもペアが作れることに注意する。 using System; using System.Text; using System.Text.RegularExpressions; usi…

問題 立方体の惑星に龍が六匹、それぞれの面に棲んでいる。食事の際、龍はそれぞれ隣り合った四面にいる龍の食事を盜もうとして、結果としてそれぞれの食事の四分の一を盜んでくる。最初にそれぞれの龍が食事を持っている量が与えられるので、指定の回数だけ…

問題 男女が輪っかの形に並んでて、K人目を輪から取り除く作業を女性の人数ぶんだけ繰り返したら、女性が全員居なくなりました。元の輪っかを復元してください。 解 単純にシミュレーションする。 using System; using System.Text; using System.Text.Regul…

意外と見てる人いるじゃんｗｗｗｗｗｗｗｗｗｗｗｗ恐れずに書き込もうぜｗｗｗｗ怪しい人じゃないよｗｗｗｗｗｗｗ「ぬるぽ」の一言でもいいんですマジで。

問題 マスターマインドにおいて、答の候補とそのヒットとブローの数が与えられるんだけど、そのヒットとブローの情報のうちひとつは偽の情報。候補とヒットとブローの情報の関係を満たすような答は何通りあるか。 解 全部の桁は1〜7で、桁は4桁。74 = 2401な…

問題 長方形の中に部分長方形がいくつとれますか。 解 全ての大きさの部分長方形について、数を全部足すだけ。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; publ…

問題 与えられた長さの間で、一番高い部分が決められた高さで、かつ高さの決まってる標識が全て現れるような丘は何通りあるか。 解 俺の嫁でおなじみの動的計画法のご登場です。残りの長さがlで、現在の高さがhで、今までに現れた標識の数がnで、一番高い部…

問題 問題文が長すぎて説明マンドクセ 解 激しくやるだけ。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; public class VendingMachine { int[,] items; int N, M…

問題 数列が与えられるので、合計に対する各要素の割合を計算しなさい。ただし端数は割合の多いものに与えていくとする。 解 やるだけ。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.C…

みんなもっと積極的にコメントするべきだと思うよ！いやコメントの付けようが無いのは分かってますけど。

問題 二進文字列Pに対するエンコードQを次のように考える。 Q[i] = P[i-1] + P[i] + P[i+1] Qが与えられる。 P[0] = '0'とした場合とP[0] = '1'とした場合にそれぞれPを復元して返せ。ただし復元不可能な場合はNONEを返すこと。 解 やるだけ、なんだけどやっ…

問題 CDに入る楽曲のサイズ、楽曲の長さ、楽曲の数が与えられる。各楽曲を一秒の空白を挟んで録音するとき、必要なCDの枚数を求めなさい。ただし、CDに入っている楽曲の数が13の倍数に決してならないこと。 解 いろんなケースについて考えられれば大丈夫。 u…

問題 整数が幾つかあたえられて、ここから三つとって、それを三辺の長さとする三角形をたくさん作る。合計の面積が最大になるような三角形の作り方をしたとき、面積はいくらか。 解 整数の数の最大が16。これはintエンコードでメモ化しろって言ってるような…

問題 1〜ある数まで、自身より左にある自身より大きい数の個数が与えられるので、条件を満たすように数列を復元しなさい。 解 深さ優先＆枝刈り。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using…

問題 12時間表記のアナログ時計がふたつあって、ひとつは壊れてて、一時間の秒数がおかしい。もうひとつは正常。この二つの時計が今指している時刻が与えられるので、次にこの二つの時計が同じ時刻を指すのは何時間後か求めなさい。 解 数学の問題。まず分も…

問題 ある文字列があって、1〜文字列の長さまでの数(iとする)を順番に考えていく。すべてのiについて、i文字目までを反転するかしないか選択できるとき、文字列ができるだけアルファベット順で小さくなるようにしたい。一番小さくしたときの文字列を求めなさ…

問題 ある数列Xに対して、Xの各要素がふたつずつ出現し、ある数nふたつの位置がちょうどn+1離れている(間にn個の要素が挟まれている)ような数列(Langford sequence)を考える。数列が与えられるので、その数列に対するLangford sequenceのうち辞書順で最小の…

問題 正方形を無限にならべた横長の板があって、この上に高さが1で横の長さが決まっている長方形がいくつかある。この長方形を左右に動かして、ちょうど決められた範囲を覆うようにしたい。最低何回動かせばぴったり覆えるか求めなさい。 解 俺の嫁(動的計画…

問題 1〜nまでの全ての数で割り切れる最小の数を987654321で割った余りを求めなさい。 解 これもやっていくだけ。最小公倍数なので素数をチェックしてかけていく。注意しなきゃいけないのは、ある素数 p (1 ≦ p ≦ n) に対して、px (px ≦ n) が最大になるよう…

問題 同じ文字の出現回数で文字列の類似度をはかります。文字列がたくさん与えられるので、一番類似度の高い文字列のペアの類似度を求めなさい。 解 やるだけなんだけど、これがもっと早く書けるといいな。類似度計算が汚い。ヒストグラム使うとかスマートな…

Round2へ行けるらしい。 Also, for competing in Round 1, you have won a limited edition TopCoder High School T-shirt!こんな事も書いてあったのでTシャツが貰えるみたい。

問題 木構造の根から出発して、全ての葉を回る最短経路を求める問題。 解 問題が読めればあとは実装するだけ。根から全ての葉にたどり着くことができるので、根から葉までの距離が一番大きい葉を一番後回しにすればおｋ。 using System; using System.Text; …