Algorithm
問題 ある文字列sを無限に繰り返して列を作る。この無限列と全く同じ列を作り出す、最も短い文字列を求めよ。 解 元の文字列が繰り返しになってれば削れる。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collecti…
問題 縦横の和が全て等しい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) が最大になるよう…
問題 同じ文字の出現回数で文字列の類似度をはかります。文字列がたくさん与えられるので、一番類似度の高い文字列のペアの類似度を求めなさい。 解 やるだけなんだけど、これがもっと早く書けるといいな。類似度計算が汚い。ヒストグラム使うとかスマートな…
問題 木構造の根から出発して、全ての葉を回る最短経路を求める問題。 解 問題が読めればあとは実装するだけ。根から全ての葉にたどり着くことができるので、根から葉までの距離が一番大きい葉を一番後回しにすればおｋ。 using System; using System.Text; …
問題 ある文字列について、ある文字が全て離れていない場合、Groupedであるとする。"aaabbcccc", "ccccccccccc", "abcdefggggh", "ab" = Grouped"aaaabbbba", "medium", "abcdeffe", "aba" = Groupedではないここで、ある文字列を分割したものが渡される。こ…
問題 長方形の形にライトが敷き詰められてて、それぞれOnかOff。ひとつの列のライトのON/OFFを反転するスイッチを全部でK回押すとき、ある行の全てのライトがOnであるような部分は最大何個ですか。 解 全ての行について、その行の全てのライトをOnにするよう…
問題 1〜15までのうち、7以下をSolid、9以上をStripeとする。8はどっちでもない。この15個の数を三角形の形に並べるんだけれども、色んな制限があって作れるのは以下の形のみ。(XがStripe, OがSolidとする) X O O O X X X 8 X O 8 O O X O X X O X O X O X O…
じゃんけんをする。相手が二回同じ手を出したあとはもう一度同じ手を出す、二回異なる手を出したあとはその二つと異なる手を出す、という理論で相手の手を推理しようと思う。最初の二回は判断材料がないので、とりあえずこちらはグーを出すとし、あとは上記…
ビットいぢり。一番右から'01'があったら'10'に変えて、その場所より右の'1'を全部詰めてあげておわり。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; public cla…
1100点問題。俺の嫁である動的計画法を駆使しｔ（ｒｙ using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; public class QuickSums { int[,] dp; string s; int N; cons…
全部試してみてTriggerならカウンタ++というか最近Easyばっかやってる気がする。Mediumも解けるようにしないと。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; pu…
