問題を読むための英単語 単語 意味 evenly 平に,平等に 問題概要 入力:数値 出力:個数入力される数値に含まれる数字の中で、入力される数値自身を割ったとき、 あまりが0になる個数を出力せよ。 ただし、同じ数値は出現する回数分可算し、また0では割っ…
問題概要 入力として与えられる辺の候補より、周長が最も長い三角形を作れ 入力:辺の長さ 出力:周長 ただし、三角形を作ることができなければ0を出力せよ。 基礎知識 三角形が作れる条件は、 \[ 三角形で一番長い辺 方法 あらかじめ辺の配列を長い順にソ…
問題を読む為の英単語 単語 意味 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 最後には、終わる 問題概要 サイコロをふって出た目のポイントで最大のものを出力せよ。 入力:5つダ…
尊敬する結城先生の著書で覚えておきたいことをまとめる。 論理(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 書式化された 問題概要 現在0時である。 与えられる秒数から、現在からの…
バックトラック法 全数探索の総当たりを大きく改善したアプローチ。 問題の制約が違反するとわかった時点で、探索をあきらめる。 そして最後の有力な部分解まで戻り再検討を行う。
問題を読む為の英単語 単語 意味 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 反対の 問題概要 ・入力 0〜3までの数列 ・出力 入力のコードを複合化し…
[計算理論]チューリン機械part2 停止問題 停止問題(halting problem)とは、チューリング機械の結果が「受理・拒否」か「ループ」を 判定できるかという問題。 一般的に「停止性をアルゴリズム的に決定する方法は存在しない」。 万能チューリング機械 万能チ…
[計算理論]チューリング機械 チューリング機械の特徴 ・チューリング機械はテープに大使、書き出しも読み出しもどちらもできる。 ・読み書きヘッドは左右どちらでも動く。 ・テープは無限長である。 ・チューリング機械は拒否や受理に対応する状態に入るとす…
[計算理論]正規言語 決定性・非決定性 ・決定性(deterministic):次の入力文字を読み出すと、次の状態が何であるか決まる ・非決定性(nondeterministic):どの時点においても次の状態としての複数の選択肢が存在する 決定性有限オートマトン(DFA) ・すべての…
[計算理論]正規言語 正規演算 正規演算とはAとBを言語とした場合に、以下で定義する3つの演算のいずれかを指す。 ・和集合演算(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):入力となりえ…
[計算理論]計算理論の導入2(列と組について) 計算理論を学ぶ為に列と組についてまとめる。 語句 ・列(sequence):ものをある順序で並べたもの Example (5, 21, 4) ・組(tuple):有限な列 k個組(k-tuple);k個の要素からなる列 ・対(pair):2個組 ・冪(べき)…
[計算理論]計算理論の導入(集合について) 計算理論を学ぶ為に、集合理論についてまとめておく 語句 ・集合(set):「もの」の集まり ・元(element):集合に属するもの ・要素(member):集合に属するもの(元と同意) 記法 \[ A \in a \] aはAの要素である。 \[ …
[その他]ハテブでTexコマンドを使いたい 導入方法 1. 右上よりデザインを選択する。2. カスタマイズ、サイドバーを選択し、モジュールの追加を選択する。3. HTMLタブに以下のコードを埋め込む。(タイトルは任意) <script type="text/javascript" src="http://cdn.mathjax.org/mathjax/1.1-latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" ></script> 動作確認 ・確認1\[y=ax^2+bx+c\]・結果…