動的計画法入門(An introduction to Dynamic Programming)KMCの競技プログラミング練習会Advanced第3回を担当いたしました。 去年Normalでフローを行わなかったので, 基本からやっていきます.
DPの話 - aizuzia
この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と
Microsoft PowerPoint - ppt-3.pptx
テーマ３：凸包 凸包の定義，構成アルゴリズム 凸包の定義 凸包(convex hull)とは， 与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと． 凸包の定義 凸包(convex hull)とは， 与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと． １点ずつ加えて行く． 現在の凸包の内部の点なら 何もしない． 現在の凸包の外部の点なら その点から凸包に接線をひき， 凸包を修正する． 問題１：凸包の内部/外部の判定方法 問題２：凸包への接線の求め方 凸包の定義 凸包(convex hull)とは， 与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと． 全ての点を含む最小の軸平行 長方形から始め，ここから削っていく． ちょうど良い 削りすぎ 削りすぎた分をどのように 復元するか？ 凸包構成アルゴリズム(1) 凸包の基本的な性質１： 平面上の点集合Sの凸包の頂点
簡単そうで難しい組合せ最適化
簡単そうで難しい組合せ最適化 簡単そうで難しい組合せ最適化 高校生，高専生，大学学部生の皆さん 私たちの研究室では，組合せ最適化（離散最適化）という ものを研究の対象にしています．これは離散数学の問題で すが，私たちの身近なところにも現れています．ここでは 組合せ最適化問題の例を挙げて，その解決に向けた研究に ついて説明いたします 京都大学工学部情報学科 数理工学コース 京都大学大学院情報学研究科 数理工学専攻 離散数理分野 長方形詰め込み問題 最初にパズルのような問題を紹介しましょう．左の図のようにいくつかの長方 形が与えられ，これらを入れ物に重ならないように詰めます．このとき，右の 図のように詰めた結果の高さをできるだけ低くすることがこの問題の目的です． １ ２ ３ ７ ６ ４ ５ ６ ８ ９ ２ ８ ５ ７ ４ ９ １ ３ 与えられた長方形 入れ物 詰めた
数学 Tips５心(重心、内心、傍心、外心、垂心）
ここでは、プログラムでよく使われる。数学の公式・定理を紹介します。 例えば、三角形の５心(重心、内心、傍心、外心、垂心）、多角形の面積・重心計算などです。 重心：３つの中線の交点 内心：３つの角の２等分線の交点 傍心：１つの頂点における内角の２等分線と，他の２つの頂点における外角の２等分線の交点 外心：３つの垂直二等分線の交点 垂心：各頂点から対辺またはその延長上に下ろした垂線の交点 〜の交点とあるので、定義に従って交点計算をしていけば、確かに求められるのですが、ベクトル表記を使うと非常に簡単に求める事ができます。 ほとんど１行ですんで、しまいますのでアプレットなどでは計算量が少ないので高速表示が可能になります。 下にある三角形をモデルとして使用します。 頂点A、B、Cのそれぞれの座標は、 A(X1,Y1) B(X2,Y2) C(X3,Y3) とします。
Rubyで最小公倍数を求める 〜Rubyでオイラープロジェクトを解こう！Problem5 - hp12c
Problem 5 - Project Eulerより 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest number that is evenly divisible by all of the numbers from 1 to 20? 2520は1から10の各数字で割り切れる数の中で最小のものである。 同様に1から20の全ての数字で割り切れる最小の数は何か。 素直に20より大きい数字を順に1から20で割って 割り切れるものを見つける def find_divisible(max) n = max loop do break n if divisible_all?(n, max) n
掃き出し法
ガウス・ジョルダン法による掃き出し計算 x - 2y - 2z + 2w = 5 ..... (1) 2x - 2y - 3z + 3w = 10 ..... (2) -x + 6y + 3z - 2w = 2 ..... (3) x + 4y - w = -10 ..... (4) 以下各ステップで式番号を、上から順に(1),(2),(3),(4)と繰り返し使う。 [ステップ１] (1)式のｘの係数を１にして、残りの式のｘの係数を０に式変形する。 (2)式の変形：(2)式 － (1)式×（＋２） (3)式の変形：(3)式 － (1)式×（－１） (4)式の変形：(4)式 － (1)式×（＋１） x - 2y - 2z + 2w = 5 ..... (1) 2y + z - w = 0 ..... (2) 4y + z = 7 ..... (3) 6y + 2z - 3w = -15 ..
年と月を入力してカレンダーを出力する - 三十路エンジニアの備忘録+α
プログラミングスレまとめ in VIPの練習問題を解いてみた 練習問題 - プログラミングスレまとめ in VIP //答え import java.util.*; class MyCalendar { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("年を入力: "); int year = scan.nextInt(); System.out.println("月を入力: "); int month = scan.nextInt(); System.out.println(year + "年" + month + "月"); System.out.println(" 日 月 火 水 木 金 土"); Calendar cal = Cale
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/wp-content/uploads/2014/12/2014.pdf
サービス終了のお知らせ
DPL_1_B:
推薦システム-神嶌敏弘.pdf
SQLで木と階層構造のデータを扱う――入れ子集合モデル