Haskellには、C++で言う所のpriority_queueにあたるモジュールがないので、Codeforcesでこれが必要な問題は解けないという問題を抱えていた（幸い、これまで自分が出てきたコンテストでそういう問題には当たらなかった、はずです）ので、自前で実装してみま…

SRMに参戦。 いい結果でしたが、妙にEasy・Mediumが簡単だった？ような気がします。早解き出来るかが勝負の分かれ目になりそうです。 Easy: 208.12 Medium: 437.90 Hard: Opened646.02pts 77th Rating :1469 -> 1644なんにせよ黄色には復帰＆自己ベスト更新…

前回参加したCodeforces #86 Div.2のE(＝Div.1のC) Double HappinessをHaskellで。問題は区間 [l,r] に含まれる・素数 かつ ・２つの平方数の和であるような自然数の数を出力せよとのこと。問題は単純なんで正解を出力するだけならいくらでも書きようあるの…

参戦してきましたが一問もあってなかったので結果だけorz 250: Failed System Test 600: Opened 1000: UnOpenedChallenge: +50/25 Score: 25pts Ranking: 581st Rating: 1512 -> 1469青に戻ってしまいました…… まだまだ実力が足らぬようです。 水曜にもっか…

Codeforces Beta Round #86 Div.2に参戦。 言語はHaskell。結果 A:488 B:824 C:1024 D:TLE E:-2 位 2336 pts Rating:1573 -> 1659Eはpretestの時点でTLEが最後まで取れず、DもTLEで落ちました。 でもDiv2内で順位が2ケタ台までいけたし、なにより紫昇格＆Div…

Codeforces Beta Round #85(Div.2)に参戦。 言語はHaskell。結果 A:484(00:08) B:928(00:18) C:1302(00:33) D:(-4) E:No SubmitHack : No Hacks 2714pts 150位 Rating:1476 -> 1573Dは一応提出しました。正解は出力するようですが、安直に書きすぎてTLEして…

(9/1に追記) (9/9に追記2)そういや最近Haskell記事ばっかですね。 （まあでも、今回話題にする篩はC++でも以前記事にしましたね。） STArrayを使う練習としてエラトステネスの篩を書いてみました。かなりすっきりと書けました。 速度に関する最適化は多少甘…

蟻本の問題から「迷路の最短路」 入力：(N M ≦ 100)N M #S######.# ......#..# .#.##.##.# .#........ ##.##.#### ....#....# .#######.# ....#..... .####.###. ....#...G#S:入口 G:出口 .:床（この上は通過可能） #:壁（通り抜けられない）出力： 入口Sか…

HaskellでCodeforcesに参戦しようとしたときに、ちょっと面倒なのが入出力だったりします。たとえば、Int型の値を直接読み込むI/Oはないので、そんな時は適当にgetInt::IO intみたいな関数を用意しなければならない訳ですが、文字列と数値が混ざっててそれを…

SRMがあると知ったのがCodeforcesが終わってから。 次回はHaskellの記事書くと言いましたがそんな暇なかったですね。結果： Easy: 166.88 Medium,Hard: No Submit1 Challenge,1 Succeed216.88pts 118位 Rating: 1334 -> 1512Medium難しかったのに加え、1撃墜…

Codeforcesに再び参戦。 言語は性懲りもなくHaskell。 今回はそこそことれました。A:412(00:19) B:844(00:39) C:864(01:46) D,E:No Submit No Hack2120 pts 197位 Rating : 1453 -> 1521Aは書くだけだったからもっと手早く書くべきだった。 完全に取れる問題…

Codeforces初参戦。昨夜あったCodeforces Div2 #79に参戦してきました。使用言語はHaskell。 SRMではC++なので、案の定いろいろと苦労しました。基本的にこれから、SRMはC++で、CodeforcesはHaskellで参戦しようと思ってます。 A:Accepted B:Accepted C,D,E:…

Haskellで蟻本記事第二弾。 Haskellでプロコンの問題に取り組もうと思ったときにまず難しいと思ったのは、基本的にリストでデータの集合を扱うHaskellでは二次元データへのO(1)でのアクセスをやろうとすると面倒なこと。 次に、そういったデータの集合を更新…

こんなタイトルなのはちょっと蟻本の勉強しようと思うから。主にHaskellとC++ですね。「くじびき」のコードをC++で書くのは容易いので今回はHaskellのみ。また、解いたのはサイズが大きいバージョンです。問題概要： 整数値k_1……k_nから４つ選んで和をmにす…

SRM513に参戦してきました。 最近ブログに報告はしてませんでしたがちょくちょく参加してました。かなーり調子悪いです。あ、あと今回からこの報告もプログラミングカテゴリにしますね。 とりあえず今回の戦績。Easy:93.65pt Medium:Opened Hard:UnopenedCha…

LCSは以前C++で最長共通部分列(LCS) http://d.hatena.ne.jp/g940425/20110210/1297296036書きましたが、ちょっと今回Haskellで書いてみようと思います。動機は、Haskellでは代入ができないのでループを回して二次元配列を更新、という従来の手続き型DPが書け…

最近、一度習って完全に忘れかけていたRubyを再学習し始めました。以前疑似乱数の性能についてプチ実験をした時にも出てきたメルセンヌ・ツイスタ(MT19937、配布ページhttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt.html)をRubyで書きうつしてみまし…

皆さん大丈夫でしたでしょうか。 とりあえず私は無事です。 今回はAOJ（AIZU ONLINE JUDGE）から、簡単な問題のコード短縮に挑んでみました。問題はVolume0の問題0000九九表を以下の形式で出力せよ 1x1=1 1x2=2 ・ ・ ・ 9x9=81 です。言語は短くしやすいCに…

先日参加したSRM499の問題の一つを再考してみる。SimpleGuess（概要）ある２つの自然数X,Yがあって、その和X+Yと差X-Yが int型ベクタで与えられるヒント(vector hints)に含まれています。 そのような数X,Yはヒントに合致する限り幾つも考えられますが、 その…

圧縮や検索などで応用されているBurrows-Wheeler変換（BW変換）＆逆変換を書いてみました。 （以下の説明では、都合上" "（ホワイトスペース）が最も大きいものとしてソートされていますが、本来" "はもっとも小さい文字です。） 変換は、まず元データとなる…

あんまよくわかんないからといって無視してきたstringstreamクラスが、調べてみるとこれがなかなか使えそうだったので覚書。 strstreamではなくstringstreamの方です。もっといえばヘッダじゃなくてヘッダで読み込む奴の方です。 いったいなんでこんなに警告…

前回の記事 「最長共通部分列(LCS)」 http://d.hatena.ne.jp/g940425/20110210/1297296036 の一般化をしてみました。所謂グローバルアラインメントというやつです。前回のdp[i][j]、つまり「パターン1のi文字目までとパターン2のj文字目までのLCSの長さ」と…

最近更新が滞っている…… なんとかせねば（；ﾟωﾟ）なので少し細かな話題をば。 最長共通部分列問題（LCS）というものは、まあ動的計画法(DP)を学ぶとしたらまず確実に練習問題で出される問題で、「二つの文字列の共通部分列のうち最長のものの長さを求めよ」…

新年一発目の記事です。ことよろ（・ω・）ノあ、ちょっと都合によりHN変えました。 のでよろしく。さて、二分探索木シリーズ第三弾。自分の中で「平衡二分木と言ったらコレ！」なイメージがあるAVL木です。多分一番最初に知ったのがこれだったからだと思いま…

平衡二分木の一つスプレー木（スプレイ木、自己調整二分木(英:Splay Tree)）クラスを制作しました。前回の 「Javaで二分探索木クラス作成」 http://d.hatena.ne.jp/g940425/20101211/1292088124 で制作したクラスBinarySearchTreeをベースに、スプレー操作と…

(12/24追記：deleteのコードに一部誤りがありました。すいませんでした。)いやあ、更新空いた空いた。 このままだと本気で何も書かなくなりそうなので、データ構造の練習をしてみることにした。それにしても、大学でCを使うのを強制されてるせいかJavaとC++…

誰得。 安 心 の 俺 得 （ `・ω・） ｂなんてね。 実は「一番手軽に多倍長計算を実装したらどうなるか」を実験してて、思ったよりスッキリしなかったからこういうネタになってしまったと言うだけのはなしです（・ε・）〜♪まあ、簡易的に多倍長計算実装しなき…

「A*探索で１５パズルにも挑戦してみた。」 http://d.hatena.ne.jp/g940425/20100815/1281849151の続き。詳しいことを書くのはいい加減面倒なんで上の前回記事参照ということで。 今回チャレンジしたのが、既にたどり着いた状態の保存形式にハッシュ法を適用…

メモ。プログラミングコンテストの問題とか解いてると、たまに data 1,data 2,data 3, ... ,data n の形でデータを読み込む必要性が出てきて、C++だとsplit()がなくてつまづくので（書けないことはないんだけど）、ここに自分式なやり方を書いとく。言語はC+…

８クイーンの話題二度目。 それにしてもパズル好きだなあと思う。 でも今回は、アセンブラの練習がしたかったのが主な理由。あと、今はじめて知ったのだが、プログラムコード記述用に「シンタックス・ハイライト」なるものがあって、自動的にプログラムを色…