最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
最小カットを使って「燃やす埋める問題」を解く
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
2-SATと強連結成分分解 - naoya_t@hatenablog
ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。（ちなみにSRM464には出場している） SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみのあれです (x_0 ∨ ¬x_1) ∧ (¬x_0 ∨ ¬x_3) ∧ ... みたいな論理式（乗法標準形）を満たす真偽値 x_0, x_1, ... の組み合わせが存在するか否か。（存在する場合、その組み合わせを知りたかったりする） 上の例ではすべての節が(高々)2変数なので2-SATと呼ばれる。 （2-SATは線形時間で解けるらしい）。 論理和 x ∨ y が論理包含 ¬x⇒y （または ¬y⇒x）に書き換え可能なことを利用して、論理式を有向グラフに変換してみたり 出来上がっ
強連結成分分解 - Win The Game
蝶本, Tips 強連結成分有向グラフにおいて、頂点の部分集合Sが「任意の２頂点u,vをとったとき、uからvへ到達できる」とき、Sは強連結であるという。 頂点の強連結な集合Sに、他のどの頂点集合を付け加えても強連結にできないとき、Sを強連結成分(SCC:Strongly Connected Component)という。 また、任意の有向グラフはいくつかの強連結成分の、共通部分を持たない和集合に分解することができる。 強連結成分分解任意の有向グラフをいくつかの強連結成分の、共通部分を持たない和集合に分解すること。 強連結成分を１つの頂点につぶすｋとで、DAG(閉路をもたない有向グラフ)になる。 強連結成分分解は２回の簡単なDFSで行うことができる。 １回目のDFSでは、適当な頂点からはじめ、まだ通っていない頂点を帰りがけの順で番号をつけていく。まだ通っていない頂点がある場合は、再びそこからは
2SAT - yasu0207の日記
強連結成分分解のアルゴリズムをゼミでやったのでメモ。 2SATは強連結成分分解を利用して解ける。 2SATは多項式時間で解ける。ちなみに3SATはNP完全。解き方は２つある。 (1)ある変数xの割り当てを0で固定すると、2SATなので、xを含む節のxとは異なる変数の割り当てが決まる。 このようにして矛盾が起こると、xへの割り当てが決定し、xを含む節を消去して再帰。 (2)2SATなので節は(x∨¬y)のような形をしている。これはy⇒xと同じである 各論理変数、論理否定それぞれに頂点を用意して、y⇒xを式が含んでいれば有効辺(y,x)をグラフに加える。 このようにしてできたグラフに強連結成分分解アルゴリズムを適用し、ある強連結成分が同じ変数の真リテラルと偽リテラルを含んだときに充足割り当てが存在しなくなる。
SRM580 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
SRM580のwriterをしていました。 点数はsolveまでの時間にも依存するので必ずしも600が激ムズという訳では一応ないです。 Div2 Easy 概要：区間が与えられるので重なってるペアの個数を数えよ。 解法：区間が50個しかないので全ペアについて試す。 Div2 Medium, Div1 Easy 概要：うなぎが区間として与えられるので、２点を選んでそれらのうちどちらか又は両方を含む 区間を最大化せよ。 解法：tから２つ選ぶのを全て試す。 Div2 Hard 概要：コストまたは通れないマスが書かれたgridがあるので、うまく横方向の壁を置いて左上のマスから下の段までの上移動を使わないpathのコストを最大化せよ。 解法：dp[i][j] = i段目に初めて到達したマスが左からj個目である時のコスト Div1 Medium 謝罪：TCでO(N^2)という制約はこういう入力にするし
Factorial number system - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Factorial number system" – news · newspapers · books · scholar · JSTOR (March 2021) (Learn how and when to remove this message) In combinatorics, the factorial number system (also known as factoradic), i
Fast Bit Counting
Devise a fast algorithm for computing the number of 1-bits in an unsigned integer. If the machine supports n-bit integers, can we compute the number of 1-bits in O(log n) machine instructions? Can we compute the number of 1-bits in O(b) machine instructions where b is the number of 1-bits in the integer?
Hamming weight - Wikipedia
The Hamming weight is named after the American mathematician Richard Hamming, although he did not originate the notion.[5] The Hamming weight of binary numbers was already used in 1899 by James W. L. Glaisher to give a formula for the number of odd binomial coefficients in a single row of Pascal's triangle.[6] Irving S. Reed introduced a concept, equivalent to Hamming weight in the binary case, in
Bit Twiddling Hacks
By Sean Eron Anderson seander@cs.stanford.edu Individually, the code snippets here are in the public domain (unless otherwise noted) — feel free to use them however you please. The aggregate collection and descriptions are © 1997-2005 Sean Eron Anderson. The code and descriptions are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY and without even the implied warranty of
DPの話 - aizuzia
この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と
JOI 2011-2012 春季トレーニング合宿 問題
2012年 3月 20日 情報オリンピック日本委員会 春季トレーニング合宿は 2012年3月19日(月)～25日(日) に，NTT DATA 駒場研修センター・国立オリンピック記念青少年総合センターで実施されました． 合宿中に 4 回の競技を実施しました． 競技時間は競技 1～4 とも 5 時間で，それぞれ 3 問が出題されました． 各問 100 点満点で合計 1200 点満点です． 各問題ごとにプログラムを作成し， 複数の採点用入力データ（セット）に対して実行し， 制限時間内に出力された正解（セット）数を競います（出力のみの課題(Output-only task)を除く）． (2013年2月16日追記) 4 回の競技の合計点が 439 点以上の 4 名を，IOI 2012 日本代表選手として選抜しました． 使用可能プログラミング言語： C, C++ （Java は使用できません） 使用機
スライド
論文・本の解説 SC 2010-2011 並列・分散グラフ処理特集 (超やっつけ) Virat Agarwal, Fabrizio Petrini, Davide Pasetto and David A. Bader, Scalable Graph Exploration on Multicore Processors, SC 2010. Roger Pearce, Maya Gokhale, and Nancy M. Amato, Multithreaded Asynchronous Graph Traversal for In-Memory and Semi-External Memory, SC 2010. Vijay V. Vazirani, Feedback Vertex Set. Approximation Algorithms, Chapter 6. Yuriy
hos.ac/slides/
hos.ac/slides/ 講義 2015/03/19-20 ネットワークフロー入門 (JOI 春合宿 講義) 2014/03/19 Binary Indexed Tree のはなし (JOI 春合宿 講義) 2013/03/19 プログラミングコンテストでの数え上げ＆整数論テクニック (JOI 春合宿 講義) 2012/03/19 「解けない問題」を知ろう (JOI 春合宿 講義) 2011/05/04 グラフ探索アルゴリズムとその応用 (JOI 代表選考会) JOI 解説 2015/03/23 記憶縛り (Limited Memory) 解説 (JOI 春合宿) 2014/03/22 かかし (Scarecrows) 解説 (JOI 春合宿) 2012/03/23 コピー＆ペースト (Copy and Paste) 解説 (JOI 春合宿) 2012/03/23 招待 (Invita
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Microsoft PowerPoint - SATSolving.ppt
generate all subsets of size k from a set
Sum-subset with a fixed subset size
How to find the longest substring containing two unique repeating characters
Find longest substring without repeating characters
プログラミングコンテストでの動的計画法
Topcoder