寝起きにぼけっと考えていた． 縦 | 横 に切ると，再び長方形になる． dp[y][x]や，dp[line][y]といったタイプの動的計画法に帰着しやすい． 面積=縦×横． 各マスに数字を書いたとき，その部分長方形の総和を，下準備O(W*H)の後でO(1)で求められる． さらに…

問題 空間に個の点がある．点から2つの点を選び，2点間のマンハッタン距離を最大化したい． ただし，マンハッタン距離とは，2点に対して で与えられる距離のことである． 単純に全通り試すとだけの計算量がかかるが，が大きいと計算コストがかなり大きくなる…

サークルで久々にSPOJの問題を解いたので解法をメモっておく． 問題 https://www.spoj.pl/problems/ABCDEF/ You are given a set S of integers between -30000 and 30000 (inclusive). Find the total number of sextuples that satisfy: 異なる整数の集合S…

問題設定 n個の正の実数の対 ()と，n以下の自然数kが与えられる． この中からk個の対 ()を選び， …(*) を最大化したい． どのように対を選べば良いだろうか． 解法 (*)式を変形して次のようにする． ここで，総和における各要素に着目し，Tを変数とみなして…

過去に何回か手を付けたけどなぜか全く頭に入っていないので，Wikipediaの記事を参考にまとめる． フローネットワーク - Wikipedia 有限な有向グラフ の各枝 に非負実数の容量 が設定されているとする。 の場合、 と見なす。ここで、2つの頂点、始点 と終点 …

凸関数の極値を求める方法を知りたくなってググってみたところid:nodchipさんのエントリがヒットした． 以下，個人的なまとめ． 実数探索三種類解説 - nodchipの日記 http://d.hatena.ne.jp/nodchip/20090303/1236058357 単調関数の零点を求めるのには2分探…

部室からなんとなく借りてみたところ，気になる項目がいくつか目に付いたので目次を写経してみる． 基礎 1. はじめに アルゴリズム 話題の概要 2. C++(およびC) 例：ユークリッドのアルゴリズム データの型 入出力 追記 練習問題 3. 基礎データ構造 配列 リ…