「paizaで修行中」の記事一覧（2 / 3ページ目）

連続する区間の和 与えられたint型の配列において、長さが 1 以上で総和が与えられた値以下であるものを考えます。そのような区間がいくつあるか、区間の長さで最大のものを求めるにはどうすればいいでしょうか？ （例）int[・・・

続きを読む

累積和 累積和とは配列の任意の区間の総和を求めるためのアルゴリズムです。 繰り返し処理を使うと大きな計算量になってしまう区間の計算問題を、適切な前処理を行うことによって高速に行うことができます。 配列と累積和 int型の・・・

続きを読む

最長増加連続部分列 最長増加連続部分列とは、配列があったとき単調増加になっている最も長い部分です。配列が {1, 2, 3, 4, 5} であるなら配列全体が単調増加しているので求める解は {1, 2, 3, 4, 5}・・・

続きを読む

動的計画法で2項間漸化式を解く 漸化式とは数列を再帰的に定める等式です。ある項とそれ以前の項の関係がはっきりしているなら、各項の値を求めることができます。 2項間漸化式を解く a_1 = 6，a_(n) = a_(n &・・・

続きを読む

今回も巡回セールスマン問題を解きます。 巡回セールスマン問題を2-opt法で解く 2-opt法とは以下のような方法です。 初期解を適当に作る。 一定の回数か、解があまり改善されなくなるまで以下を繰り返す 　巡回路を成す辺・・・

続きを読む

巡回セールスマン問題を最近傍法で解く 巡回セールスマン問題を最近傍法で解いてみることにします。やり方は以下のとおり。 始点となる都市を適当に1つ選ぶ。これが今いる都市。 今までに訪れたことのない都市のうち、今いる都市に最・・・

続きを読む

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。 どのようにして解を求めればよいのでし・・・

続きを読む

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路のうち最も短いものを求める問題です。 正確な値は取得できないのですが、最小全域木を使って・・・

続きを読む

グリッド版ダイクストラ問題セットなのですが、C#の解説がありません。そこで自分で解説をつくることにしました。 コストの合計の最小値 グリッド状の盤面で上下左右の移動を繰り返して、左上から右下まで移動するときに通るマスのコ・・・

続きを読む

こんな問題が出てきたらあなたはどうするだろうか？ 引用元：長い長い数列 数列 A = (A_1, A_2, …, A_n) と数列 B = (B_1, B_2, …, B_m) が与えられる。 n・・・

続きを読む