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が書け…

SRM508に参戦。 いやあむずかったっすね。まだまだ俺のレベルでは無理ゲー。 Easy:Challenge Succeeded. Medium:Opened Hard:UnopenedChallenge:No Challenge.Rating:1454 -> 1383250を解くことにすべてをかけるつもりで臨んでいてもむりですかそうですか。 …

SRM504.5 Div1に参戦。 250の解法を早期に思いつけて良かった。 以下結果。 チャレンジは今回はなしでした。250:210.55550:Opened900:Challenge SucceededChallenge : No ChallengeRating: 1405 -> 1454 900はやめときゃよかった。いやホント。 通ってるはず…

SRM505 Div1に参加。難しかったですねー。以下結果。もちろん一つも通りませんでしたが、 チャレンジ成功で0点は免れた結果レートは上昇。250:Challenge Succeeded500:Opened1000:UnopenedChallenge : 1 Challenges,1 successRating: 1291 -> 1405 250は通り…

SRM504 Div1に参加。なのですが……実際参加した人は知ってると思いますが、途中でArenaに不具合が起きてunratedになってしまいました。まあでも、参加はしたので一応点数をば。結果：250:162.06500:Opened1000:UnopenedChallenge : No ChallengesRating: (unr…

SRM503 Div1に参戦。結果：250:Challenge Succeeded500:Opened1000:OpenedChallenge : No ChallengesRating:1455 -> 1291 ＼(^o^)／ﾅﾝﾃｺｯﾀｲ ううむ、今回はEasyの解答をパッと思いつけなかった上、焦って場合分けの条件をミスってしまったのがまずかった。25…

なんかいきなり数学関連カテゴリ書くのもなんだけど、気になり過ぎているのでここに書く。発端は、田崎晴明氏の日記↓ http://www.gakushuin.ac.jp/~881791/d/1104.html#01ここに、下のような記述がある。（以下引用）「……たとえば「ルート 2 が無理数である…

SRM501に参戦。結果： 250:Passed System Test 500:Opened 1000:Opened Challenge : 1 success,1 unsuccess Rating:1344->1455 と、前回よりは改善しました。やっぱりまだDiv1の500を通すのは難しい。 あと、Challengeにもうすこし慎重になるべきだね。いず…

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

SRM二回目にして初のdiv1。 結果：250:Challenge Succeeded 500:Opened 1000:Opened Rating:1354->1344＼(^o^)／ 結論：まだdiv1で戦えるような実力はさすがにない。 いやそれにしても酷いっていうかまず問題の意図すら把握するのが難しかったからね（；・ω…

皆さん大丈夫でしたでしょうか。 とりあえず私は無事です。 今回は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はヒントに合致する限り幾つも考えられますが、 その…

ん？コレその他カテゴリでいいのか？（； ・ω・）TopcoderのSRMに初参戦してきました。 250、500はSystemTest通ったし、Challengeもひとつ成功させたので、個人的に初回にしては頑張れたかなと思いました。平均的に見てどうなのかは知らん。順位は174位で652…

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

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