問題概要 重さと価値がそれぞれWi,Viであるようなn種類の品物がある。 これらの品物から重さの総和がWを超えないように選んだときの、 価値の総和の最大を求めろ。 ただし、同じ種類の品物を使ってよい。i番目までの品物から重さの総和がj以下となるように選…

問題概要 ２つの文字列t, sが与えられる。 これら２つの共通部分文字列の長さの最大値を求めよ。 共通部分文字列とは、互いに共有する文字列であり、連続で一致している必要は無いが、 順序は等しくなければならない。 例示 s = "abcd" t = "becd"LCS = 3 (…

問題概要 フィボナッチ数列の総和を返す 解法 1.メモ化 /* メモfb[]はあらかじめ-1(メモ無し)で初期化する */ fib(int a){ /* メモ化チェック */ if(fb[a] != -1 ) return fb[a]; if( a == 0 ) ret = 0; else if( a == 1 ) ret = 1; else ret = fib(a-1) + f…

問題概要 重さwと価値vがついた品物がn個ある。 これらの品物から、重さの総和がWを超えないように選んだときの 価値の総和の最大値を求めなさい。 問題解法 1.全探索 再帰的に、品物をチェックし入れた場合、入れなかった場合とで探索を繰り返す。 重さの総…

問題概要 とても長い板からN個の板を切り出す。 切り出す板はL1,L2,...Lnであり、元の板の合計となっている。 板を切断する際に、その板の長さだけコストがかかる。 例えば２１の板を１３と８に分けた場合、コストは13+8である。 最小コストで板を切り出した…

サイコロの期待値 期待値 期待値は「確率で重み付けした値の和」。*1 例題*2 アリスがa面サイコロ、ボブがb面サイコロを持っている。 単純に出た目が多い方が勝ちというゲームを行う。 アリスが勝つことを知っているとき、アリスが出す出目の期待値を求めよ…

問題概要 入力：整数集合 出力：整数値 整数集合の冪集合を抽出し、その合計値を算出せよ。 ただし、冪集合は隣り合う値でのみ採用する。 {1, 2, 3} ▶︎{ 1 }, { 2 }, { 3 }, {1, 2}, {2, 3}, { 1, 2, 3} ▶︎1, 2 ,3, 3, 5, 6 ▶︎20 class SumOfPower { public …

演算 商を求める double d = (double)a / (double)b; 型を変換しないとint型として出力されてしまうことに注意する。 配列操作 初期値付き配列宣言 int[] score = new int[6]{0, 0, 0, 0, 0, 0}; 配列内をソート int[] array = new int[3]{3,1,2} Array.sort…

問題概要 入力：N文字の文字列S、長さ０の文字列T 以下の操作を行い、辞書順比較でできるだけ小さい文字列Tを作れ。 ・Sの先頭を１文字削除し、Tの末尾に追加 ・Sの末尾を１文字削除し、Tの末尾に追加 問題考察 貪欲法を使う。 先頭の文字が小さければ小さい…

問題を読む為の英単語 単語 意味 keycaps キー配置 decipher 解読する 問題概要 入力：タイプ文字列とキースイッチ キースイッチは{"A:B","C:D"}というような形式で与えられ、 例えば始めのキースイッチが押された場合、 タイプ文字列にAがあればBに、Bがあ…

問題を読むための英単語 単語 意味 evenly 平に,平等に 問題概要 入力：数値 出力：個数入力される数値に含まれる数字の中で、入力される数値自身を割ったとき、 あまりが０になる個数を出力せよ。 ただし、同じ数値は出現する回数分可算し、また０では割っ…

問題概要 入力として与えられる辺の候補より、周長が最も長い三角形を作れ 入力：辺の長さ 出力：周長 ただし、三角形を作ることができなければ０を出力せよ。 基礎知識 三角形が作れる条件は、 \[ 三角形で一番長い辺 方法 あらかじめ辺の配列を長い順にソ…

問題を読む為の英単語 単語 意味 male 男 fimale 女 direction 方向 arrange 配列する 問題概要 入力：男の人の数、女の人の数、削除パターンK 出力：男女の並び順 男女の並び順を作る。男女の並びはサークルになっている。 開始位置(先頭)から始めて、K番目…

問題を読むための英単語 単語 意味 Julius Caesar シーザー(ローマ将軍) cryptography 暗号法 further さらに遠くに、さらに進んで 問題概要 Input:暗号文、シフト数 Output:復号文文字をアルファベット順である文字数分だけシフトする暗号がある。 例えば'A…

問題を読む為の英単語 単語 意味 rectangular 長方形の 問題概要 入力：width, height 出力：長方形の個数以下のような四角形が与えられる。 __ __ __ |__|__|__| |__|__|__| |__|__|__| (width:3 height:3)与えられた四角形に存在する長方形の数を出力せよ…

問題を読む為の英単語 単語 意味 scoring 採点法 Yahtzee ヤッツィー(ダイスゲーム) upward 上へ向かう considered 熟考したうえで instance 実例 end up 最後には、終わる 問題概要 サイコロをふって出た目のポイントで最大のものを出力せよ。 入力：５つダ…

尊敬する結城先生の著書で覚えておきたいことをまとめる。 論理(AならばB) AならBは以下のように記述する。 \[ A \Rightarrow B \] 「AならばB」の定義は以下の通りである。 A B A▶︎B ture true ture ture false false false ture true false false true

SRMs 1 145 DIV2 500 強くなりたい 問題を読む為の英単語 単語 意味 workout (計算を)解く exercise 演習 routine ルーチン(決まりきった仕事) whole 全体の lasts 最後に残った 問題概要 コンピュータが処理を行うとき、現在の進行度をパーセンテージで表示…

SRMs 1 145 DIV2 200 英語難しい。 問題を読む為の英単語 単語 意味 dithering ディザリング ※1 determine 決心する upper 高い方 surround 取り巻く 問題概要 入力：ディザリング文字列 : スクリーン 出力：ディザリング文字の数スクリーン内のディザリング…

SRMs 1 144 DIV2 200 どうやらDIV2の方が簡単らしい。 問題を読む為の英単語 単語 意味 tend 傾向がある represent 代表する particular 特有の、個々の midnight 真夜中 formatted 書式化された 問題概要 現在０時である。 与えられる秒数から、現在からの…

バックトラック法 全数探索の総当たりを大きく改善したアプローチ。 問題の制約が違反するとわかった時点で、探索をあきらめる。 そして最後の有力な部分解まで戻り再検討を行う。

問題を読む為の英単語 単語 意味 gamblers ギャンブラー variety 多様な wide variety 種類が豊富 lottery 運、くじ represent 代表する inclusive すべてを含んだ appear 出現する indicate 指し示す restriction 制限 descending 降下的な order 順序 like…

[CodeIQ]チケットゴブル問題 問題概要 国名と旅行日程が与えられる。 一年間でより多くの国へ行ける旅行プランをたてよ。 入力：国名 旅行期間(例：1/1-1/5) 出力：国名(アルファベット順にソート) 解法 この問題はスケジューリング問題に帰着する。 スケジ…

[TopCoder]練習（SRMs 1 144 DIV 1 300) 問題を読む為の英単語 単語 意味 following 次の say 示す encrypt 暗号化・符号化 adjacent 隣接した above 上の particular 詳細 opposite 反対の 問題概要 ・入力 ０〜３までの数列 ・出力 入力のコードを複合化し…

[計算理論]チューリン機械part2 停止問題 停止問題(halting problem)とは、チューリング機械の結果が「受理・拒否」か「ループ」を 判定できるかという問題。 一般的に「停止性をアルゴリズム的に決定する方法は存在しない」。 万能チューリング機械 万能チ…

[計算理論]チューリング機械 チューリング機械の特徴 ・チューリング機械はテープに大使、書き出しも読み出しもどちらもできる。 ・読み書きヘッドは左右どちらでも動く。 ・テープは無限長である。 ・チューリング機械は拒否や受理に対応する状態に入るとす…

[計算理論]正規言語 決定性・非決定性 ・決定性(deterministic)：次の入力文字を読み出すと、次の状態が何であるか決まる ・非決定性(nondeterministic)：どの時点においても次の状態としての複数の選択肢が存在する 決定性有限オートマトン(DFA) ・すべての…

[計算理論]正規言語 正規演算 正規演算とはAとBを言語とした場合に、以下で定義する３つの演算のいずれかを指す。 ・和集合演算(union) \[ A \cup B = \{ x | x \in A または x \in B \} \] ・連結演算(conncatenation) \[A \circ B = \{xy | x \in A かつ y…

[計算理論]正規言語 計算モデルの導入 理想的な計算モデルとして有限状態機械「有限オートマトン」を導入する。・有限オートマトンの正式な定義 有限オートマトンは以下の要素を持つ。 状態の集合 入力アルファベット 動作規則(δ：遷移関数 によって定義され…

[計算理論]計算理論の導入3(関数と関係について) 計算理論を学ぶ為に関数と関係についてまとめる。 語句 ・関数(function)：入力と出力の関係を決める。 ・写像(mapping)：関数と同意。f(a) = bは「fはaをbに写す」と言う。 ・定義域(domain)：入力となりえ…