鳩でもわかるC#

c++ には set と map があります。setは重複を許さない順序付き集合です。重複データがある場合は、重複データは自動的に削除されます。またmapは各要素がキーと値を持ち、同じキーが重複することがありません。 C・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 動的計画法 最長共通部分列問題 蟻本読書会の続きです。 部分和問題とは 「{1, 3, 7, 10, 13} の部分和で、和が 21 になるものは存在するか？」という問題です。この場合、・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 動的計画法 01ナップサック問題 蟻本読書会の続きです。 最長共通部分列問題 最長共通部分列 ある列 Z が X と Y 両方の部分列であるとき、Z を X とY の共通部分列と言います・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 本当は難しい貪欲法 選択肢を多く残す 蟻本読書会の続きです。今回から動的計画法ゾーンに入ります。 01ナップサック問題とは？ ナップサック問題、価値 viと重量 wi をもつ n 種類の・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 猪突猛進！ 貪欲法 区間スケジューリング問題 辞書順最小など 蟻本読書会の続きです。 貪欲法とは「問題を部分問題に分割して，各部分問題に対する局所最適解を求めることを繰り返すという手法」・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 n! 通りの全探索 next_permutation 意外と奥が深い全探索 蟻本読書会の続きです。 貪欲法は近似アルゴリズムの最も基本的な考え方の一つである。近似アルゴリズムとは組合せ最・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 迷路の最短路 意外と奥が深い全探索 蟻本読書会の続きです。 全探索のなかには n! 通りの全探索やnext_permutationを使うものもあります。C++ には next_permu・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 幅優先探索と深さ優先探索 意外と奥が深い全探索 蟻本読書会の続きです。 迷路の最短路を幅優先探索で探す 迷路の最短路を探すときも幅優先探索を使います。深さ優先探索でもできますが、探索空間・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 意外と奥が深い全探索 bit全探索 蟻本読書会の続きです。 幅優先探索と深さ優先探索 幅優先探索と深さ優先探索も全探索のひとつと考えることができます。頂点と頂点が辺でつながっている場合、・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会の続きです。 基本は全探索 競技プログラミングにおけるすべての基本は全探索です。といってもfor 文を二重三重にして回すだけでは全探索を理解したことにはなりません。bit全探索や深さ優先探・・・

続きを読む