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

ちょっと二分探索について分からないことがあったのでメモっておこうと思います。二分探索は探索空間を半分にしていくことでnの大きさの空間をO(logn)で探索出来る代表的なアルゴリズムです。地球上の人類70億人から1人を見つけるのも33回で出来ます（ちょっ…

先日読んだ「プログラマが知るべき97のこと」という本に環境設定の重要性が書かれていまして、それに触発されて一番よく使うアプリケーションであるテキストエディタで一番良さそうなものを探してみることにしました。 OS Mac OS X Leopard 10.5.8 要望 1. …

一度使ってみたいなあと思っていたPerlでプログラミングをしてみました。 最近はRubyとかPythonみたいなスクリプト言語ばっかり使っていたのでちょっととっつきやすいです。Perlのバージョンはv5.16.1。まずは環境設定。さすがにaptana studioにPerlの環境ま…

選挙は自民党が圧勝でしたね。選挙速報を脇目にARCに参加しました。 A - 名刺交換 そのまま実装すればOK。10分くらい。 ソースコード B - 超大型連休 与えられた日付を祝日とし、祝日が休日とかぶっていたら振替休日にする。そのとき、休日の最大連続数を求…

おそらく一番有名なオンライン競技プログラミングコンテストである、TopCoderのSRM(Single Round Match)に参加してみました。 SRMが僕が今まで参加してきたコンテストと違うのは、獲得点数が時間が経つほど減っていくことと、問題文が英語であることです。英…

授業の課題でが対称正定値行列での時、 minimize subject to を最急降下法、加速勾配法、共役勾配法のプログラムを実装して解くという課題が出ました。対称正定値行列Qとベクトルqはランダムに作ります。 対称正定値行列（固有値全てが正である行列）を作る…

前に参加したコンテストの解説を兼ねた表彰式に参加してきました。 場所は大手町1stSQUAREにあるデジタルアーツ株式会社。どうせまた道に迷うと思い35分前に行ったところ、一番乗りでした。 スーパー有名なAtCoder株式会社代表取締役、chokudaiさんと直に話…

UTPC2012にネット上から参加してみました。 A - 2012年12月02日 与えられた日付の月、日を並び替えて年数と同じに出来るかを判定する問題。始めは指示通りに実装しようかと思ったけど、数字の順番は関係ないので数字の種類だけ覚えておけば良い。自分にして…

DigitalArts プログラミングコンテスト2012に出てみました。 A - C-Filter 文字列のフィルタリング問題。NG文字にワイルドカード「*」が混じっている。確かJavaって正規表現を扱えたよなーとか思いつつ、調べるより書こうと思い素朴に実装。変な勘違いをして…

ネットサーフィンしていたらCompetitive Programming Advent Calendarのページを見つけまして。やっぱりトップレベルの人たちの考え方はすごいなーと見ていたらチャレンジ問題があったので久々にHaskellでチャレンジしてみました。アルゴリズムとしては条件…

気分転換にRubyでコンテストの問題を解いてみました。 Wikipediaによると、Rubyはオブジェクト指向スクリプト言語で、HaskellよりもCやJavaに近いみたいです。 IDEにはAptana Studio 3.2.2のEclipse Plug-in Versionを使用。何故かデバッグは出来ませんが、…

ようやくGCJ2011の予選の問題を全てHaskellで解けました。 解いた順番に書きます。 C. ビット数 与えられた数字を2つの2進数の和で表す時に、1の数を最大化する問題。 唯一自力で解けた問題です。与えられた数字を2進数に直し、下の位から見ていき、一意的に…

天下一プログラマーコンテスト2012決勝のA問題ぶんたんは解き方が全く分かりませんでしたが、解答を見てみるとどうも貪欲に大きいフィボナッチ数を引いていけば良いみたいです。 なんで？と思っていたら証明している方がいました。なるほどなあ。理屈さえ分…

Google Code Jamのこの問題をHaskellで解こうと思い、アルゴリズムが思いついたのでコードを書こうとして気付きました。Haskellの素数表ってどうやって作るんだ？ちなみにJavaやCではbooleanの配列を用意し、2から初めて倍数をfalseにしていき、次に3を見て…

今までHaskellで解いてみたいくつかの問題をまとめてみました。 WUPC2012 A - 招待状 与えられた2つの日付の差を求める問題。javaみたいにCalendarクラスみたいなのがないかな？と調べてみたらありました。import A (B) でモジュールAの関数Bが使えるように…

AtCoder Regular Contest #007に出てみました。 A - 帰ってきた器物損壊！高橋君 文字列からある文字を抜き取る問題。Scannerでcharを読み取る方法が分からなかったので、Stringをcharに変換した。5分くらいで終了。 ソースコード B - 迷子のCDケース CDとケ…

この夏休みにHaskellを勉強してみることにしました。 最近、趣味でプログラミングコンテストの問題を解いていますが、しばらくはHaskellで解いていきたいと思っています。 しばらく、ここにはHaskellの勉強の内容を書いていきます。よろしくお願いします。 H…