V. Braverman and A. Meyerson, “Streaming k-means on well-clusterable data,” In SODA, 2011.ストリームk-meansアルゴリズム．

解説が無さそうな問題の一言解法．コードは略．

今までで一番時間をかけた問題．基底変換や，線分と放物線の交点等が入り混じった実装問題（not強実装）．

このエントリは，Competitive Programming Advent Calendar Div2012の参加記事です．ICPCアジア地区予選について色々とまとめておこうと思っていたのですが，折角の機会なのでこの場を借りて記事にしてしまいます． チーム情報 チーム名 Ultimate & Escapist…

全体の流れを覚えている限り書いてみた．流れが若干間違っているけどご愛嬌． 0min. izがA，todoがB，k_operafanがCを読み始める．間髪を入れずにk_operafanがCを書き始める．Bはぱっと見で構文解析っぽかったが，そんなことはなくて，瞬殺出来る問題だった…

問題 N*N(N行列式をmod Pで求めよ． 解法 正統な解法はkomiyaさんの記事参照． [id:komiyam:20111216:1323963329]ここでは，逆元とかを使わずに直接求めた．

Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman and Angela Y. Wu. A Local Search Approximation Algorithm for k-Means Clustering. In Proceedings of the eighteenth annual symposium on Computational ge…

David Arthur and Sergei Vassilvitskii, k-means++: The Advantages of Careful Seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (2007), pp. 1027-1035.言わずと知れたk-meansアルゴリズム（Lloydのアルゴリ…

K. Hajebi, Y. Abbasi-Yadkori, H. Shahbazi, and H. Zhang, Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph. ;In Proceedings of IJCAI. 2011, 1312-1317. k近傍グラフ上での山登り方による近似最近傍探索． Locality Sensitive …

結構前の話だが，院試について書く．超ラフな備忘録．質問はコメントかTwitter([twitter:@todo314])にてどうぞ．

Michael Shindler, Alex Wong, and Adam Meyerson. Fast and Accurate k-means For Large Datasets. In NIPS, 2011.k-meansアルゴリズムのストリーム版で，割りと最近のもの．今回は適当に紹介．

David Pearson, A Polynomial-time Algorithm for the Change-Making Problem, Technical Report TR 94-1433, 1994.コインの両替問題のインスタンスについて，貪欲法が常に最適解を返すかどうかをで判定する．更に，答えが"NO"の場合は，最適解と貪欲解が一…

チームUltimate & Escapist Codersで参加． 全体の記録は，id:k_operafanさんの記事を参照． [id:k_operafan:20120707:1341845475] 主に関わった問題 A:Millennium C:Biased Dice F:Generic Poker 以下，各問題に関する反省． A Millennium 問題文で定義され…

A. Björklund and T. Husfeldt. Inclusion--Exclusion Algorithms for Counting Set Partitions. FOCS 2006.ほったらかしにしてた続き． 多項式空間 前回の方法では，空間計算量は指数オーダーだったが，空間計算量を節約して多項式オーダーに収める事が出来…

探索っぽい問題だが，全体集合の部分集合による被覆と考えれば，包除原理で解ける． 序盤 配置可能な正方形をBitSetで全列挙する． 中盤 極大集合（正方形）だけを残す． あるマスを埋められる正方形が1つしか無い場合，その正方形を無条件で採用する． 更新…

A. Björklund and T. Husfeldt. Inclusion--Exclusion Algorithms for Counting Set Partitions. FOCS 2006.備忘録がてら記事を書いていたら長くなったのでとりあえずPart 1．http://d.hatena.ne.jp/wata_orz/20120329 にて彩色数をで求めるアルゴリズムの論…

id:iwiwiさんの高速ゼータ変換に関する記事 http://topcoder.g.hatena.ne.jp/iwiwi/20120422/1335065228 が恥ずかしながら分からなかったので，自分なりに解釈した． やりたいこと 集合に関する関数があり，全集合について， を求めたい． コード for(int i=…

wataさんライブラリの解読． ヨセフス数 J(n,m,k):n人の輪からm人毎に殺していった時にk番目に殺される人の番号[0, n-1]まずn人を以下のように並べる． 0,1,2,…,m-2,m-1,m,…,n-3,n-2,n-1 とりあえず1人殺してみるとm-1が消える． 0,1,2,…,m-2,,m,…,n-3,n-2,n…

VK Cup 2012 Wild-card Round 2 (03/29~04/04) VK Cup 2012 Round 2で大敗したのでチャレンジ． 問題 w*hの長方形領域に，n個の長方形を配置する．各長方形(wi, hi)には，回転，拡大・縮小を行うことが出来る．回転は90°単位で（つまり(wi, hi)が反転），拡…

メモ EvenRoute ある点とある点の経路長のパリティは経路によらないため，各点を最終訪問点とした時のパリティを計算すれば良い． public class EvenRoute{ public String isItPossible(int[] x, int[] y, int par){ int n=x.length; boolean ok=false; for(…

上位700人のみが通過． メモ A Dress'em in Vests! 貪欲に考える． import java.util.*; import java.lang.*; import java.math.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; import static java.util.Collecti…

メモ MergersDivOne 貪欲法でも解くことができるが，自信がなかったのでDP． import java.util.*; import java.lang.*; import java.math.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; import static java.util…

備忘録． 問題 各DNAシークエンシングコールについて3つ組のデータが与えられるので，どの程度信頼性があるかを決定するプログラムを作成せよ． TopCoder 解法 最小二乗確率的分類器（LSPC） LSPC*1は，杉山将氏の考案した確率的分類器で，入力が連続，出力…

コンテスト中に書いたメモをアップしてみる． A. Win or Freeze 最初のプレーヤーをA，次のプレーヤーをBとする．qの自明でない約数が存在しない時はAの勝ち（1 or 素数）．それ以外の時は，qの自明でない約数でかつ，自身の自明でない約数が素数のみとなる…

ポリアの定理 http://ed-www.ed.okayama-u.ac.jp/~suugaku/naru/grad/H11B/ver0217/ged11035/page/groupFrame.htm http://www.is.titech.ac.jp/~sadayosi/course/past/comb06/chapter3.pdf http://ed-www.ed.okayama-u.ac.jp/~suugaku/naru/grad/H11B/ver021…