競プロに強くなりたい人におすすめの本 : Grenache's blog
競プロに強くなりたい方、蟻本以外のいいもの見つけました。 すでに強い方は当然知っているようなことでしょうが、なかなか初心者から抜け出せない私にとってはいいなと思った本です。 「数え上げの問題」に強くなる 「マスター・オブ・場合の数」をおすすめします。 「数え上げの問題」って、なかなかいい参考書がないと思っていました。数え上げ問題に出会うたびに、解説を読んで勉強しますが、なかなか解けるようになりません。知識としていろいろ知っておかなければいけないというよりは、テクニックやノウハウ的な部分が大きいからなのかと思います。しかし、それらにも典型というのはあって、それを知っているのと知らないのでは大きく違うようです。 この本は、典型的な問題がカテゴリ別に整理してあり、解法が詳しく記載されています。また、ちゃんと問題を解くと、同じ系統の問題を何度も練習することになり、いい訓練になりました。解法が1つだ
Re永続データ構造が分からない人のためのスライド
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。
競技プログラミングにおける永続データ構造問題まとめ - はまやんはまやんはまやん
永続データ構造 persistent data structures 解説 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。 完全永続。昔のどのバージョンからでも変更でき、履歴が全て残っている。履歴は木。 永続配列があれば永続Union-Findが作れるらしい 永続配列は永続木があれば作れるらしい 部分永続Union-Findの資料 部分永続はスタックで履歴を残しておいて逆操作をしていって戻すやり方がある（要出典）多分そのやり方でやってる 平衡二分木を永続化するときは赤黒木が最良らしい 問題 完全永続セグメントツリー SPOJ D-query CF429 Destiny (要素add,特殊クエリ) 部分永続セグメントツリー CS
最小費用流の負辺除去 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。 この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくなるのでは思います。 （2019-06-27に若干書き換えました） 追記 (2021-08-15)： ポテンシャルを求めるのが簡単な場合にはそれを使って負辺除去する方が楽です。 この記事の方法はグラフが複雑だったり、思考停止したいとき用かなぁ。 例題 最小費用流への認識 最小費用流は「始点 S から終点 T に水を流す」という問題に見えがちですが、それは少し本質とずれています。 水の例えを用いつつ言うならば「頂点間で水をやりとりして過不足を補い合う」という感じでしょうか。 実装の際に始点と終点があった方が分かりやすいことがあるだけで、定義上は必要なものでは
東京工業大学でTarjan教授を拝見した - でも今日はSRMあるから
講義に出席した。顔を拝むのが目的。 Tarjan先生 我々が毎日書いているUnion-Findや強連結成分分解（lowlinkのやつ）の証明やらアルゴリズムやら考えたすごい人。 1時間の講義でZip Treeをマスターしよう。 Zip Tree 二分探索木の一つ。詳細な解説は講義に出た人の特権なので避けるがTreapにとても似ている。正直、名前聞いたことなかった。 Treapと比較して2つの違いがある ランク Treapはランダムな値を優先度としてノードに割り当てるがzip treeではそれをランクと呼ぶ。Treapでは経験上ノード1つに対してO(log n)ビットの追加メモリが必要だが、Zip TreeはO(log log n)ビット、多分。。。 実装ではこんな感じでいいだろうか？Treapのランクが32ビットなのに対し、Zip Treeは31以下（5ビット）で済んでいる。Treapで乱
Lock-freeとWait-freeアルゴリズム - Wikipedia
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
Python SciPy : 線形計画問題を解く
適当な例を解いてみます。 linprog は目的関数を最小化するベクトルから解を求めます。 問題を目的関数の最大化としたい場合は式の係数の符号を反転させ、結果の符号も反転して読む必要があります。 import numpy as np from scipy.optimize import linprog c = [-3, -2] A = [[2, 1], [1, 1]] b = [6, 4] x0_bounds = (None, None) x1_bounds = (1, None) res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds)) res fun: -10.0 message: 'Optimization terminated successfully.' nit: 3 slack: array([ 0., 0.
線形計画法のソルバの使い方：Python - Research Note！！
最近，線形計画法のソルバを使ってあれこれしました．使うために色々調べたわけですが，時間が立つと調べた内容を忘れそうなので記録しておきます． 線形計画法のソルバはPuLPというライブラリから呼び出して使います． PuLPインストール 方法は色々有るようですが，私の場合はコマンドプロンプトから， pip install pulpと打ってインストールしました． 例題を解いてみる こういう最適化問題があるとします． これは が答えなのですが，本当にそうなるかを試します． バッチ処理版 細かいところを説明する前に，まずは全体像をお見せします．バッチ処理で書くとこんな感じです． # (1)ライブラリ呼び出し import pulp # (2)問題の定義 lp = pulp.LpProblem('lp', pulp.LpMaximize) # (3)変数の設定 x1 = pulp.LpVariable(
【ドワンゴ×チームラボ】競技プログラミング勉強会 by tayama0324 さん - niconare
2015年12月に行われた競技プログラミング勉強会の資料です。 http://dwango-teamlab.connpass.com/event/23053/ http://dwango-teamlab.connpass.com/event/23058/ ACM-ICPCやAtCoderなどで利用されているような、コーディングのスピードと正確さを競う競技スタイルについてドワンゴ競技プログラミング同好会部長の田山より、レクチャーを行います。AOJ や AtCoder の「良問」にチャレンジすることで、アルゴリズムの勉強方法や、選手が利用するライブラリ等のツールについて説明します。最後には、実践として導入問題の回答にチャレンジいただきます。
最小カットを使って「燃やす埋める問題」を解く
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
ネットワークフロー入門
ネットワークフロー入門 保坂 和宏 (東京大学理学部数学科) 第 14 回 JOI 春合宿 2015/03/19-20 1 前置き • ネットワークフローに関する理論的な興味 グラフの難しそうな問題が多項式時間で解ける！ 応用範囲が広い 賢い高速化もいろいろ • 副産物的な発見もある 2 前置き • プログラミングコンテストにおけるネットワークフロー 「問題からうまいことグラフを構成してフローを流して解く」 というパターンが多い • うまいグラフを作るのにひらめき or 経験が重要，ということでコ ンテストにお似合い • フローの部分は皆事前にコードを書いてある (または頭に入ってい る) という風潮あり 二部グラフへの応用 (最大マッチングなど) はそれだけで強力な 道具 • 複雑な貪欲法を回避できることがしばしばあります ICPC, topcoder, Code
日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 - koyumeishiのブログ
日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 先日 RCO が主催したプログラミングコンテスト 日本橋ハーフマラソン のオープンコンテストに参加しました。 オープン参加で賞金もレートもかかっていなかったのでA問題は放棄して、 ビジュアライザが用意されていた B問題 日本橋大渋滞 を解こうとしたのですが、実装が間に合わず未提出、0点のままコンテストは終了してしまいました。 後日考えていた方針の実装を終わらせ提出したところ、かなり出来のいい点数を出せたのでその振り返りをします。 2017/03/26 時点で一位 http://rco-contest-2017-final-open.contest.atcoder.jp/submissions/1176109 入力例2 74手 46555点 おおよその方針は次の一連のツイートの通りですが、もうちょいと詳しく解説。 天才過ぎて70手ぐらいまでにな
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
PuLP による線型計画問題の解き方ことはじめ - Qiita
PuLP で数独を解く - Qiita
http://www.logopt.com/python_learning/wp-content/uploads/2014/05/mipproblem2.pdf
SSSSLIDE
グラフネットワーク〜フロー&カット〜
最小費用フロー問題
最適化基礎 第11回 最小費用流問題 最大重みマッチングとオークション
数理計画法 第9回 ネットワーク最適化 3. 最小費用フロー問題