Lexicographically Minimal String Rotation (Booth's Algorithm)

概要 何となく理解したので自分用のメモ 文字列 s を cyclic に回転させた時の辞書順最小の文字列を求める問題をO(n)で解く 呼び方が色々ありそうだけど Wikipedia の Lexicographically Minimal String Rotation (以下 LMSR) を採用するLMSR は Suffix Arra…

AtCoderList

AtCoderで自分がどの問題を解いたか確認しようと思うと, コンテストページに行って自分の提出を見ないといけないので非常に面倒です. そこで,AtCoderのコンテストから自分の提出を自動的に収集して各問題を解いたかどうか確認するためのプログラムを作り…

yukicoder No.78 クジ付きアイスバー

問題 http://yukicoder.me/problems/152 解法 1箱目と最後の箱はシミュレーションし,間の箱はまとめて処理する. 間の箱をまとめて処理するため,以下の事実を使う. まず, n = 1箱に入っているアイスバーの数 s = 1箱に入っている当たりの数の和(2本当た…

KUPC2014

7月5日にKUPC2014がありました. 僕は第一回のKUPC2011にはコンテスタントとして参加して(参加記d:id:sune2:20110807:1312714641), その後の2012,2013には運営側として携わりました. 今年は運営の取りまとめ役として携わり,思い入れも強いので記事を書…

Convex Hull Trick

概要 問題 : 「多数の f_i(x) = a_i * x + b_i と,多数のクエリ x に対し min f_i(x) を求めよ.」 この問題を解くためにConvex Hull Trickというものがある. 蟻本において,K-anonymous Sequenceという問題の解法として紹介されている(Convex Hull Tric…

Technology Campの感想とサポートページ

Technology Camp 去年の9月にインターンとしてサイバーエージェント社によるTechnology Campに参加した。 Technology Campは休日含め10日間で1つのアプリを仕上げる。 開発は2人チームで行うが、何を作るかは完全にこちらに任されるので、企画から行う必要が…

区間のk-th smallestが求められる謎データ構造

この記事は Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83) の16日目の記事です。 データ構造の話です。 地区予選の過去問を解いているときに、以下のような問題を見つけました。 【問題…

org-mode 8.2 導入メモ

インストール 最新版はhttp://orgmode.org/ja/で確認する wget http://orgmode.org/org-8.2.tar.gz tar -zxf org-8.2.tar.gzhttp://d.hatena.ne.jp/buzztaiki/20100201/1265031994を参考にしてorg-table.elを修正する *** lisp/org-table.el 2013-10-01 11:0…

赤記念

前回のSRMでレッドコーダーになりました! レッドコーダーな人達というのはそうそうたる人々で、ずっと憧れていたので仲間に入ることが出来て非常に嬉しいです。 グラフを見るとここ半年くらい妙に上がり調子なのでキープできるか非常に不安ですが、出来るだ…

タイトルの一部を変えるbotについて

[twitter:@titleReplaceBot] 概要 「○○のタイトルの一部を△△に変えると××」という形式のハッシュタグに対して、 データベースに保存された○○のタイトルの一部を△△に変えて15分おきにつぶやく。 詳細 タイトルデータベース 現在、{アニメ,小説,ゲーム,映画}の…

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

http://acm.timus.ru/contest.aspx?id=153 ロシアの怖い合宿で出題されたセットらしい。チームで解いたが10問あって2完という怖いセットだった。 本番ではC,Iを解いて後でA,Fを解いた。 A - Complex Root 問題 x^n = a+bi x^m = c+di を満たすような複素数x…

幾何修行

AOJ

japljさんが幾何の問題集をVirtual Arenaでセットしていたので、最近ちょこちょこやっている。 まだ途中だけど、とりあえずまとめる。 http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=1178&active=status AOJ 2045 - Turn Polygons 多角形の中にある多…

Regionals 2010 :: Asia - ChengDu

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=381 A - Balanced Number 問題 [x,y]に含まれるbalanced numberの数を求めよ。 Balanced Numberとは、ある桁を中心として他の桁の値を重さと見たときのモーメントが…

Regionals 2011 :: Asia - Chengdu

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=520 A - Alice and Bob B - Break the Chocolate 問題 N*M*Kの板?チョコレートがある。 これを1*1*1のピースに分けたい。 分け方には手を使う方法とナイフを使う方…

Regionals 2011 :: Asia - Dhaka

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=518 Binary Matrix 問題 要素が1,0のみのN×M行列が与えられる。 隣接する要素同士をスワップするという操作のみ認められる。 ただし、1行目とN行目のスワップや、1…

Regionals 2011 :: Asia - Kanpur

Strongly Connected Chemicals 問題 (V=L∪R,E)な2部グラフGが与えられる。 L'⊂L,R'⊂R(|L'|>=1, |R'|>=1)なL',R'を選んで、 全ての(i,j)∈L'×R'の間に辺があるようにしたい。 このとき|L'|+|R'|の和の最大値を求めよ。 制約 1 ≤ m, n ≤ 50 解法 L'=Φもしくは…

立命合宿2013参加記

3/11~3/13に立命館で行われたプロコン合宿に行って来ました。 主にコンテストの反省書きます。 1日目 チーム名はevisuto、チームメイトはevimaさんとtokoharuさん 結果は3位 感想 強いお二人と組めてとても楽しかった。 びっくりするくらい楽しかった。 Fは…

Regionals 2009 :: Europe - Northwestern

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=362 A - 4609 - An Industrial Spy 篩&全探索という日本のICPCによくありそうな問題 B - 4610 - Common Subexpression Elimination 問題 二分木を縮約する。 文字…

KUIS卒論諮問会頻出質問集?

昨日発表してきました 疲れた↓頻出順(適当) この研究のポイント(困難な点、自分がやった点、工夫点、新規性)は? (参考文献を見て)本当にちゃんと調べた? 何がしたかったの?(目的が分からん、目的と手法があってない、目的と評価方法があってない)…

各種典型再帰関数を非再帰に変換する

再帰関数はあんまり再帰が深くなるとスタックオーバーフローの危険があり、できれば非再帰で処理を書きたいというケースが稀にある。 再帰関数はスタックを使えば非再帰で書けるとたまに聞くが、実際どうやれば良いか分からなかったので調べてみた。 典型的…

フィボナッチ数まとめ

フィボナッチ数をまとめてみた。 「AOJ2372 - IkaNumber」の解説も入ってる。https://www.dropbox.com/s/6nx2f9htpfyvnkv/fibonacci.pdf競技プログラミングと関係のありそうなフィボナッチ数の話題があったら教えて下さい。とりあえずProject Eulerまわりを…

AOJ 1333 - Beautiful Spacing

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 ICPC Asia Tokyo 2012 Problem I 問題 図1のようにN個の単語を配置する。 1行にはスペースを含めW文字入る。 入力としては、i番目の単語の長さがxiとして与えられる。 以下良い配置の条件 入…

AOJ 2385 - Shelter

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 問題 頂点数Mの多角形領域の中に,N個のシェルターがある。 多角形領域の中に等確率で位置すると考えたとき、最も近いシェルターまでの距離の期待値を求めよ。 制約 M,N -1000 解法 あるシェ…

AOJ 2211 - 迷い猫、走った

AOJ

現実逃避の続き http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2211 問題 略 解法 答えについて二分探索。 答えをk以下に出来るかどうかを判定したい。 猫と餌入れはx座標でソートしておく。 解説スライドの通り dp[i] = i番目に餌を置いた時に…

AOJ 2025 - Eight Princes

AOJ

現実逃避 問題 n個の椅子がある円卓がある。 ここに8人の王子が座る。 ただし、王子が隣り合ったり、ちょうど向かい合ったりしてはいけない。 このとき、何通りの座り方があるか。 回転したり反転したりして同じになるものも区別して数える。 制約 答えは10^…

蟻本練習問題埋め3-2

しゃくとり法 POJ 2566 - Bound Found 問題 要素数nの数列aが与えられる。 各クエリでtが与えられるので、連続する部分列の中で、和の絶対値がtに最も近いものを求めよ。 制約 n ai t クエリの数やデータセットの数の制約は書いてない 解法 しゃくとり法で各…

蟻本練習問題埋め3-1(3)

二分探索(k番目を最小化、その他) POJ 2010 - Moo University - Financial Aid(AC) なんか昔解いてた。 メジアンを決めて、その下からN/2匹、上からN/2匹をコストが最も少なくなるように選んだときF以下になってるかどうかを判定する。 priority_queueなり…

Regionals 2010 :: Asia - Hangzhou

日曜日に時間があったのでやった練習。 http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=866 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=385 BCFHJは解けた。 Dはあと1箇所のミスだった。 Gはぎりぎり解け…

蟻本練習問題埋め3-1(2)

二分探索(平均最大化,k番目の値を検索) 二分探索における現在の区間の中央の値をxと表す。 それにしてもPOJは時間制限キツイなあ。 POJ 2976 - Dropping tests 蟻本通り POJ 3111 - K Best 蟻本通り POJ 3579 - Median 問題 長さNの数列Xiが与えれる。 Xi …

ICPC東京大会と高雄大会反省

いまさら 結果 東京 http://www.cs.titech.ac.jp/icpc2012/regional-contest/standing.html 7(10)位 高雄 http://c68.nsysu.edu.tw/ezfiles/232/1232/img/1439/index.html 5(11)位 反省 東京 EとIが解けないとかどうしようもない 高雄 Gで5回WAを出したのは…