programming

IEEEXtreme 2009 の賞品が届いた

IEEEXtremeという、IEEE主催で1.5年に1回ほどのペースで開催されているプログラミングコンテストがあります。 今回で3回目となる本大会に、Konohanasakuyaというチーム名で@nodchipと@bonboriと一緒に参加しました。 二人のパワーのおかげで5位/700チームに…

POJ 1769 Minimizing maximizer

データ構造を工夫しないと通らない、かといって典型的なデータ構造を探してきて適用すれば良いわけではない。どうにかオーダーに間に合うように工夫するのが楽しかった問題。長さn (2 区間[i, j] (1 問題は、ある完成品のMaximizerが与えられているとき、無…

srm452

とても久しぶりに参加。 div1:250 NotTwo 最大1000*1000の盤面に、ユークリッド距離が丁度2になるような石のペアが存在しないように可能な限り石を置いた時に最大でいくつ置けるか。 整数座標でユークリッド距離が丁度2になるのは上下左右に2マス離れた場合…

ICPC国内予選C その2

予定してませんでしたが。そして多分その2で終わりです。昨日学内の練習会でImos Judge(http://judge.imoz.jp/)を利用させて頂いて国内予選の復習をしていたのですが、そこで「Cの制限時間が厳しくて通らない」という話題で少し盛り上がっていました。 厳し…

ICPC国内予選C

模擬国内予選と国内予選の参加記も書くつもりですが、取り急ぎCのソースだけ! Cは一見楽勝に見えてそのまま書き始めると実にかったるい(next_permutationを使ってしまったり)ですが、問題文を読み込めばDFSですっきり書けます。 #include <iostream> #include <set> #inc</set></iostream>…

Aho-Corasick

Spaghetti Sourceの複数パターン検索 (Aho-Corasick)で紹介されているスライドを参考にして、書かれている疑似コードをほぼそのままC++で書き直してみたもの。Trieのvalues_フィールドが保持しているのは、そのノードに到達した時点でマッチしている単語の集…

KMPとかACとか、文字列検索系の問題

KMP Algorithm - Search for Problemsに載っているのをちょこちょこ送信中。UVaは掲示板書き込みの英語率が高いのが良い。

UVa 10975 Dueue's Quiz

長さ1000以下の単語が最大15000個与えられる。最大100*100の文字テーブルの中に出現する単語を全て数え上げよ。文字テーブルの読み方は、縦横斜めをそれぞれ双方向。Aho-Corasick、だけれど、細かい所で注意しないといけない微妙な問題。具体的には以下。 ci…

UVa 11475 Extend to Palindrome

長さ100000以下の文字列sが与えられる。sの後ろにできるだけ少ない文字列を連結して回文にし、出力せよ。少し考えると、sをreverseした文字列をs_revとして s.substr(s.size() - N) == s_rev.substr(0, N) となるような最大のNを求めれば良い事が分かる(で…

明治ミルクチョコレートパズル(ブラック):回答編

いきなり回答編ですが。最近研究室の後ろに座ってる人がこれ(http://www.amazon.co.jp/%E3%83%8F%E3%83%8A%E3%83%A4%E3%83%9E-%E6%98%8E%E6%B2%BB%E3%83%9F%E3%83%AB%E3%82%AF%E3%83%81%E3%83%A7%E3%82%B3%E3%83%91%E3%82%BA%E3%83%AB/dp/B000BVN0AA)を持…

srm437

久しぶりのsrm、のはずだけど、今年からペースが落ちたので問題セット的には間は空いてない。 しかしまぁ緊張した。 div1:250 TheSwap 1 スワップを全通り試すと6C2 ^ 10になって当然終わらないけど、6桁の数字の並び替えはせいぜい6! = 720通りしかないので…

srm433 復習

参加記の方書くの忘れてた。 本番は250で8! * 160 * 160を書いてしまって撃墜され、500でad-hocをやって撃墜されてしまって0点。うぐぐ。難し目のセットだったようであまり下がらなかった。 div1:250 MagicWords T(i) = T(0)となるiがK個存在するT(0)はK個の…

srm431

srm430からそれほど間を空けずにsrm431。前回は登録出来なかったので助かった。 ただ来年は月二回ペースとの噂があるのでなんとも残念。 div1:250 直行座標系の第一象限と第四象限に、y軸と並行な長さ1以上の線分がいくつか与えられる。偏角-PI/2 〜 PI/2の…

OS Xでアセンブリからシステムコール呼び出し

とりあえずのhello world。 .file "hello.S" .data msg: .ascii "hello world\n" len = . - msg .text .globl start start: # call write(1, $msg, $len) pushl $len pushl $msg pushl $1 lea -4(%esp), %ecx # stack pointer - 4 movl $call_exit, %edx # r…

srm429

全っ然分からなかった。今でも何が起きたのか謎。もっと勉強します。。。 div1:250 dpと思ってやってたので全然思いつかないのも当たり前。 あるマスに着目するとそのマスを含むような四角形の作り方の数が定数時間で求められる。 全てのアルファベットの出…

ICPC 2008 アジア地区予選 参加記

本番で書いたコードが送られて来たら思い出しながらしみじみ書こうかと思ったんですが、一向にその気配が無いので今更ながら書きます。とりあえず当日だけ。僕たちはトップチームとかでは全然ないので参加者が読んでも新たな知見を得られたりするわけではあ…

srm427

とってもひどかった時のsrm日記。 div1:250 今回もなかなか読めなくて、要するに(yearLength % dayLength) * x = dayLength * yとなるような最小のxを求めれば良いんだろーと思ってlcm(yearLength % dayLength, dayLength) / (yearLength % dayLength)って書…

Binary Indexed Tree

FloatingMedianとProductOfPricesとUVa 10909で動くのを確認。 template<class T> class BIT{ public: BIT(int n) : n(n), tree(n) {} T read(int idx) { // returns 0 if idx is smaller than 0 T ret = 0; for (; idx >= 0; ret += tree[idx], idx = (idx & (idx + </class>…

srm426

黄色くなって初めてのsrm! div1:250 読んでも読んでも問題の意味する所が分からなかったが、こんだけ分かりづらかったらみんなもスコア低くなるだろ。。。と思って特に焦らず読む。10分ほど読んでようやく手計算と結果が一致したので注意深く組んで提出。部…

UVa 11544 Recruiter's Problem

二部マッチングの練習をしようと思ったら丸一日かかった…グラフはこんな感じ。 SRC --1-- CANDIDATE(i) --1-- PROJECT(j) --r-- SINKまず最初にここと同じで、一人目の一つ目の仕事からgreedyに割り振り、流量が減らないなら採用する事を繰り返す、という方…

DinicとEdmondsKarp

どれが最新か分からなくなりそうなのでここにメモ。 // UVA 10989 AC:0.990sec // PKU 3469 AC:5938MS // (時間はdinicの方) class Graph { private: struct Edge { int to, back, flow, cap; Edge(int to, int cap, int back) : to(to), back(back), flow(0…

srm425

調子に乗ってる時だけ更新するsrm日記。 div1:250 深さ14で枝が4本伸びると2億、うーん。。。もしかしてNESWの列だけ見て簡単にsimple性を判定する方法があるのか?と悩んで遅れる。ちょっと考えてバック出来ないんだから枝の数は3本以下になって400万余裕じ…

srm424

調子の悪い時は書かないsrm日記。 div1:250 2〜9で与えられた数を割っていけば良い。最初2から割って100が2*2*5*5で4になってしまった(正しくは4*5*5で3)ので9から割るようにした。 passed system test 225.63 div1:600 600だけど簡単。strengthとintellect…

ICPCから帰宅

コンテスト終了〜 結果はABCFGの5問を解いて11位でした(standings)。 目標に1問届かなかったけど去年より難しめのセットだったから仕方ないかな。 素人としてはまずまずの成績を残せたと思います。 去年ほどの残尿感は無し! そして何より二日目の夜に他の…

ICPC 2008 アジア地区予選前夜

というか既に当日...! 荷造り中です。 とりあえず定規と方眼紙とシャーペンと消しゴムを持った。 これで幾何も怖くない。 唯一の問題はspeechの原稿が白紙のままだという事です。。。 6問目指して頑張るぞー

はてぶデバッグモード

はてぶ閲覧中にfirebugで Hatena.Tracker.manager.debugMode(true); と入力すると全リンクに赤枠が付いてはてなもしっかりclick through rateを取ってるんだなと思える遊び。

Min-Cost Max-Flow Related Problems

こんなのが紹介されていたのでメモ。

UVa 563 Crimewave

UVa 563 Crimewave50*50の格子点上に泥棒が沢山居て、他の泥棒の逃走経路と交差しないような逃走経路で格子点から逃げ出したい(格子点の端の点に辿り着けば良い)。全ての泥棒がそのようにして逃走可能ならばpossible、不可能ならばnot possibleと出力せよ…

MaximumCup2008に参加してきました

結果はA->G->B->Dの4問ACで、前回2問しか解けなかった私は大変満足です。ふぇふぇふぇ。 MaximumCupは半分国語の問題のような気がします。 A 支持対象が無かった場合"No"になるんだけど、問題文によると「 該当者なしの場合、町の人の回答は "No" という 2…

google maps walking direction (beta)が凄い

この記事http://journal.mycom.co.jp/news/2008/07/23/003/index.htmlにあるように、7/23に米国版google mapsで徒歩の粒度での最短距離検索が行えるようになりました。とりあえずアメリカの西の端のあたりから東の端あたりまでの距離を検索した結果を見て下…