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

多角形の面積を簡単に出す方法を@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以下で最大の素…

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

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

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

今までプログラミングコンテストに望む際に、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 http://www.codechef.com/MARCH13CodeChefのLong Contest。 Tourist Translations やるだけ。 Scalaでやってみました。 やっぱり関数型言語のmap関数は便利です。 ちなみにInt型をChar…

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

前に出た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)にす…

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

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

ここ（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:…

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

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

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

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