[PHP][アルゴリズム] N人の人気投票順位予想でM人を的中させるパターン数

職場の人に考えてみてと言われたので解いてみました。 解法 動的計画法で出しました。 N人からM人一致させるパターンをdp[n][m]として考える。 1. n=mの時は全的中なので1パターン 2. m=0の時は全パターンからm>=1のパターンを引く 3. それ以外の時は(nからm…

[Contest][AOJ][C++] 高速ゼータ変換 / 高速メビウス変換

The Enemy of My Enemy is My Friend | Aizu Online Judgeを高速メビウス変換を使って解きました。その際に学んだことの備忘録としてこの記事を残します。 問題概要 N(N 以下の条件を満たすように同盟を組むとき、1つめの国を含む同盟の軍事力の和の最大値を…

sedで「git blame」に色づけ

CUIで「git blame」を打っても全く色がつかずに見づらいと思っていたところで、会社の先輩がsedでログの標準出力に色を付けていたことを思い出し、やってみました。colorize_git_blame.sed #!/bin/sed -rf s/\([a-z0-9]\+\)/\x1b[31m\1\x1b[0m/ s/\((\)\([a-…

pecoを使って動的にgrepする

動的にgrepを行って絞り込みが出来るpecoというツールを教わったので使ってみました。候補の文字列を動的に絞り込めるのでとても便利なツールです。pecoはなんとGo言語で動きます(pecoの元になったpercolはpython製)。インストールはMacならHomebrewで一発…

 Vimのテキストオブジェクトの使い方と関連プラグイン

今日チームのVimmerの人が小さい勉強会を開いてくれました。そこで学んだ内容をメモに残しておこうと思います。 テキストオブジェクト Vimではある程度のテキストのまとまりをかたまりとして扱う機能が標準でついています。 これを「テキストオブジェクト」…

emacs-navでファイルをウィンドウ分割して開けるようにしてみた

近頃Node.jsを書くことが多かったのでエディタはAtomを使っていましたが、どうも重く感じることがあるので最近はEmacsを使っています。Emacsのファイラはemacs-navを使っています。ファイル構成をツリー状に表示してくれるだけでなく、Emacs上からファイルの…

コード品質管理ツール「CppDepend」を使ってみた

最近Node.jsを書くことが多く、コードの品質管理ツールとしてJSHintを使っています。VimやEmacs、SublimeやAtomなどの有名どころのエディタと連携して動的にコードスタイルのチェックが出来るため、コーディングを重ねることで自然によいコードを書けるよう…

Suffix Arrayを使ってみた

全く解き方が分からなかったMountain HolidaysのEditorialが出たので解いてみました. Mountain Holidays 整数の配列height(1 次の条件のいずれかを満たすとき(i1, j1)と(i2, j2)の2つの連続部分列は異なる. 1. j1 – i1 != j2 – i2 2. height[i1+k] – heigh…

SRM609参加記

初めてdiv2の本番で全完出来てテンションが上がったので書いちゃいます. MagicalStringDiv2(250) '>'と'''>'...' 単に数えるだけ. class MagicalStringDiv2 { public: int minimalMoves(string S) { int len = S.length(); int ret = 0; Rep(i, len){ if(i …

ARC017に参加しました

ようやく修論発表も無事(???)終わり、少し余裕が出来たのでARC017に参加。今回こそはCを解くと意気込んでいました。 A - 素数、コンテスト、素数 N(17≤N≤1,000,000)が与えられるので、Nが素数かどうか判定する。コピペをやるだけ。 始めsqrt(1,000,000)…

CodeChef October Challenge 2013を頑張ってみた

October Challenge 2013に参加しました。 初めて7問(正確には6.143問)解けたので参加記書きます。以下は解いた人が多い順です。 Helping Lira N個の三角形が与えられる。最大の面積と最小の面積を求めよ。 ライブラリがあったのでやるだけ。ソースコード M…

[図形][C++] 多角形クラスを作ってみた

多角形の面積を簡単に出す方法を@hirokazu1020さんに教わったので多角形クラスPolygonを実装してみました。ほとんど蟻本のコピーです。 //二次元座標(from 蟻本) typedef struct _PT{ double x, y; _PT() {} _PT(double x, double y) : x(x), y(y){ } _PT op…

ミラー・ラビン素数判定法を使ってみた

CodeChefのMay Challenge 2013に挑んだ時に解けなかったWitua and Mathを解いてみました。 Witua and Math 整数Nが与えられる(2 オイラーのtotient関数をφとするとき、φ(i)/iを最大とするi(2 totient関数のWikipediaを見ると、この問題は「N以下で最大の素…

Vimのpegjs用シンタックスファイルを改造してみた

研究でPEG(解析表現文法)を扱っており、パーザージェネレータにPEG.jsを使っています。 pegjs形式のファイルはJavaScriptとPEGの文法規則を並べたものから構成されているので、上手いカラーシンタックスが出来ません。一番近いのはJavaScriptのシンタック…

分数の話

Equations整数Nが与えられる。 (1/x) + (1/y) = 1/N! を満たす正数(x, y)の組の数(mod 1000007)を求めよ。 1000000!なので数え上げ系は無理。 変形すると (x + y)*N! = xy なのでこの式と組み合わせを上手く使って解くのかと思ったけどどうも上手くいかない…

切断点や橋を求めるTarjanのアルゴリズム

グラフ理論において、切断点(cut vertex, articulation point)とは無くす事でグラフの連結成分の数が増える頂点のことをいい、橋(bridge)とは無くす事でグラフの連結成分の数が増える辺のことをいいます。 グラフの頂点集合に対してDFSを行うと森(木の集ま…

コピー先に連番が扱えるようにcpの拡張を作ってみた

今までプログラミングコンテストに望む際に、template.cppをA.cpp, B.cpp, ... , E.cppにコピーする必要があり、これが非常に面倒でした。 先日zmvコマンドの記事(http://mollifier.hatenablog.com/entry/20101227/p1)を読んで、もしかして簡単に連番のcpが…

二部マッチング

前から最大流問題を解いてみたいなーを思っており、蟻本を購入したのをきっかけに、この前参加したFacebook Hacker Cup 2013 Round 1の2問目「Security」が二部マッチングの問題だったので解いてみました。 Security {a, b, c, d, e, f}からなるキー k があ…

March Challenge 2013, TCO 2013, Codeforces #172

いくつかコンテストに出たので記録しておきます。 March Challenge 2013 http://www.codechef.com/MARCH13CodeChefのLong Contest。 Tourist Translations やるだけ。 Scalaでやってみました。 やっぱり関数型言語のmap関数は便利です。 ちなみにInt型をChar…

最強のシェル zsh

今までシェルはbash一筋だったのですが、最強のシェルと聞いてzshを使ってみました。Macには標準でもzshが入っていましたが、せっかくなので最新版をインストール。 インストールはHomebrewで brew install zsh で一発で出来ます。 デフォルトシェルの変え方…

BITを使ってみた

前に出たCodeChefのコンテストで解けなかった問題を解いてみました。Magic Board http://www.codechef.com/problems/MBOARDN*NのフィールドとQ個のクエリが与えられる。 クエリは RowSet i x: i行目をx(=0 or 1)にする。 ColSet i x: i列目をx(=0 or 1)にす…

Codeforces Round #166, CodeChefとか

EclipseのC++プラグインCDTがすごい使いやすいんですが、最近デバッグすると飛んだりします。しかも恐ろしいことに頻度が上がってきているような気がする・・・。 February 2013 Challenge http://www.codechef.com/FEB13CodeChefのロングランコンテストに出…

ARC12とZOJ

最近ようやくEclipseのテンプレート機能を有効活用し始めました。for文とか早く入力出来て便利ですねー。もっと早くScannerとPrintWriterをテンプレート化しておけば良かった。 AtCoder Regular Contest #012 http://arc012.contest.atcoder.jp/ A - 週末 英…

コンテストラッシュ2

ここ(http://wikiwiki.jp/kyopro/?FrontPage)を見て面白そうなOnline Judgeがあったのでいくつか登録してみました。あとFacebook Hacker Cupの結果を。 Facebook Hacker Cup 2013 Round 1 https://www.facebook.com/hackercup/problems.php?round=18989011…

コンテストラッシュ

最近プログラミングコンテストがやけに集中して開催されていたので、いくつか出てみました。 Facebook Hacker Cup 2013 Qualification Round 就活のためにと思って登録したFacebookでしたけど、コンテストなんてやっているとは。 1.Beautiful strings https:…

Codeforces Round #162 (Div. 2)に参加してみた!

http://codeforces.com/contest/265登録したもののなかなか参加出来なかったCodeforcesについに参加しました。 Codeforcesは形式がTopCoderに似ていて、得点は時間依存で、hackというTopCoderの撃墜があります。ただし、hackはコーディング中に行うという点…

AtCoder Regular Contest #011に参加してみた

久々のプロコン! A - 鉛筆リサイクルの新技術 そのまま実装すればOK。10分くらい。 ソースコード B - ルイス・キャロルの記憶術 Bにはめずらしくこれも基本的に実装するだけ。終わった時点で30分くらい経過。 ソースコード C - ダブレット ある単語first、l…

JavaScript Engine

研究でJavaScriptを使うことになり、JavaScriptを簡単に実行出来る環境が必要になりました。 Google Chromeを使ってやるのも無理ではないのですが、やはり毎回ブラウザを立ち上げたくないです。RubyのirbとかPythonのREPLみたいな対話式環境と、jsファイルを…

Scalaを使ってみた

前々からScalaを使ってみたいと思っており、Competitive Programming Advent Calendar Div2012でlizanさんのScalaで競技プログラミングしてみるの記事を見てちょっとやってみようかと使ってみました。Scalaは最近ちょっと熱い(らしい)、オブジェクト指向と…

セグメント木を使ってみた

Competitive Programming Advent Calendar Div201218日目の記事、kagamizさんのIntroduction to Segment Treeを見て、セグメント木を実装してみました。解いたのはCodeforcesのC. Circular RMQ。久々にC++で実装しました。スクリプト言語でやろうかとも思っ…