読者です 読者をやめる 読者になる 読者になる

MapReduce と map 関数と reduce 関数を組み合わせたパターンの違い

なんでこんなめんどくさいタイトルになるのかといえば, それはすべて某 G が紛らわしいフレームワーク名をつけたからです. すべて某 G が悪い. それはさておき, map 関数とか reduce 関数というのはリストに関数を適用する高階関数である. map 関数 とは, 1…

Twitter アイコン

これただの絵じゃなくて上がファイストス絵文字 (𐇐) で、下が線文字B (𐀁𐀃𐀗𐀫; eomoro) です。多分フォント持ってないと思いますが。

拡大グラフ上のダイクストラ

ACM-ICPC に Traveling by Stagecoach Traveling by Stagecoach という問題がある. 大雑把に言うと, 入力として道路網のグラフが与えられるので, 最短路を求めよ, という問題なのだが, 一捻りして馬車券という要素が加えられている. 要するに最短路を求める…

メタメタ

メタプログラミングとは何か? という話が最近身近で話題になった. 大体, プログラミングの上に載っている高次の何かっぽいことである気がする. その時の結論としては, 自己言及的なプログラミングという話になったが, それはオートプログラミングとでも呼ぶ…

申し込みトレンド

某コンテストの申し込みを何日前に済ませるかをグラフにしてみるとこのようになります。縦軸は日(対数)です。 だいたい早めに申し込む勢と最終日に駆け込む勢は 7 : 3 で、駆け込み勢は多少の開始日の違いに影響されない様子が見て取れて興味深いですね。 以…

Algorithm Short Course 「探索」

これは2008年11月頃に某所で内輪向けに発行した冊子に掲載したものを転載したものです。

集約される式と展開される式

普通の式は関数からなる. 関数は複数の引数を取り, 1 個の返り値に集約する. しかし, 逆があってもいいのではないか. すなわち, ただ 1 個の種を取り, 複数の返り値に展開していくのである. 一見普通の式であるが, 引数のように見えるところは返り値を渡す先…

多倍長整数の符号化としての UTF-8

UTF-8 は Unicode で使われる 0 から 0x10FFFF までの正の整数を 1 ~ 4 byte の符号で表現する可変長の符号化方式である. その気になれば, 無限に大きい正の数を表現できるように拡張することもできる. 多倍長整数の符号化方式として捉えたときにどうなるか…

学会タイマー

学会タイマーの実装方法は2種類ある. 1秒待って経過時間を加算して画面を更新するということを繰り返す 経過時間の更新と画面の更新は特に同期せず, 適宜開始時刻から引き算する ちょっと考えればわかるが, 1 の方法はアウトである. 更新にかかる時間の分だ…

ゆる募

【緩募】各種中間言語用VMの性能比較 (オーバーヘッドの大きさ、あるいは JIT の賢さ、SIMD系命令への対応など) ってどこかにありませんか?— えおもると寝坊と昼夜逆転さん (@eomole) 2013年5月10日

wakaba の系譜

Java の配列の長さ

問 Java の配列は 231-1 より長いものを作れないというのは、知られていないが案外深刻な問題である。こんなに要素が多いものは作らないと思うかもしれないが、内部で配列を使っているものは少なくない。 String のような文字列、 ArrayList あるいは HashMa…

GW

GCJ (Google Code Jam) Week です。連休中は Round 1 があります。頑張りましょう。 http://code.google.com/codejam/

2分探索したいけれど上限が見積もれないとき

問 2分探索は答えを確実に含むような十分広い区間から初めて、区間を半分にしていくことにより、対数時間で答えの存在範囲を絞り込む方法である。整数値であれば、区間が1になるまで続けることで誤差なしで求めることもできる。しかし、このままでは初期区間…

文字システムについてつぶやいた話

世界の文字: ラテン・キリル・ギリシア・グルジア・アルメニア > おおよそ1音素1文字— もるたるさん (@eomole) 2013年4月20日 アフロアジア系諸文字 > 子音だけ。不便じゃない?と思うかもしれないけど言語の特徴により送り仮名を省略する程度のような感覚っ…

Calling Brainf*ck

Brainf*ck のループが常々鬱陶しいと思っていたので [, ] を置き換えてみた. 記号 値 実行内容 @ 0 何もせず次へ進む. 0 以外 i 番目の @ ならば i 番目の ^ の直後にジャンプする. ^ 0 i 番目の ^ ならば i-1 番目の @ の直後にジャンプする. 0 以外 i 番目…

hello world

Hatena Blog に移ってみた。インポート機能があって記事は全部移せたのでよかった。

今年の抱負

抱負を手に入れる。。(再)

日本における ACM-ICPC のデータ(2)

2011年にACM-ICPCに参加した日本の大学は71校であるが、今までに参加したことのある大学は117校あるらしい。その辺も調べてみた。 なお、大学内から何チームという制限があるので表記揺れがないはずなのだが、電通大など一部の大学は統一されていないらしい…

日本における ACM-ICPC のデータ

気になったので、Baylor 大のサイトから登録されているチーム名のリストをとってきてカウントしてみた。 数字は3種類で、大学数、チーム数、チームの特定大学への集中度である。 集中度というのは各大学から参加するチーム数がべき乗則に従うと仮定して、傾…

今年の抱負

抱負を手に入れる。。

誕生日ネタ

適当なことをつぶやいたら問題を作られてしまいました. https://twitter.com/#!/miracjp/status/146070398730121216 https://twitter.com/#!/peria/status/146075492351606784 これを求めるプログラムを書いてみてくださいな.

バグのないプログラムを作るための技術

2015/12/10 追記: バグを本気で無くしたい方はこんな良く辺鄙なブログなんて見ずにソフトウェアエンジニアリング系の国際学会に行くなり、そこの論文を読むなりするといいと思います。ICSEなんかは日本語の勉強会資料もあってとっつきやすいでしょう。バグの…

Dijkstra's Algorithm

こんな世界になっていたのですね。 あきばやべぇ。 Dijkstra のアルゴリズム - (iwi) { 反省します - TopCoder部

Dijkstra's Algorithm

最近 Dijkstra's Algorithm の話があったので, ちょっと思い出したことを徒然と. この algorithm では, 次に始点から一番近い頂点を探すときに heap を使うことが多いかと思います. しかし, priority_queue とか PriorityQueue には, すでに heap に入ってい…

SRM503結果 概略

ねむ。 250 500 1000 Challenge 185.13 253.26 Opened - Score Rank Rate 438.39 97 1749 -> 1845 500がちゃんと解けたのでひとまずOK。 そういえば、自分の部屋で不正があるとか言われていた人たちはどうなったのだろう。

SRM501結果 概略

大撃墜大会。 250 500 1000 Challenge 189.31 Compiled Opened - Score Rank Rate 189.31 345 1775 -> 1749 流行に乗れず…。前回の貯金がマイナスに。

SRM500結果 概略

500回記念賞金付き。帰省地より。 250 500 1000 Challenge 95.90 Opened Unopened - Score Rank Rate 95.90 311 1750 -> 1775 遅すぎ酷いです...でもレート微増で自己最高更新中。 ただし、もちろん賞金無縁。

自鯖

こっちには書かないことにしようと思っていたけれど、一応連絡。 3/26まで日がありますが、サーバー安定稼働できないっぽいので、このまま落としっぱなしにします。wakabaの遺跡については、pukiwikiのディレクトリ丸ごとアーカイブしたもの (要するに PHP, …

SRM499結果 概略

ねむす。 250 550 1000 Challenge 230.92 249.30 Opened - Score Rank Rate 480.22 148 1672 -> 1750 Greedy...

Maximum Winter-Contest 2011結果 概略

特にScannerが遅いって書いてありますが、使わなくてもやっぱり遅くて苦しめられました。 結果:3問 最終順位はどうなることでしょうか。追伸:オフライン3位(3/7)でした。賞品もらってしまいました。あれま。

SRM497結果 概略

出てみた。 250 550 1000 Challenge 193.45 Opened Unopened - Score Rank Rate 193.45 182190 1630 -> 1672 550の実装まだまだ重いなあ。

計算と記述の順序

Java には計算の記述に次のようなスタイルがありますよね. y = fn(…(f1(f0(x)))…); y = x.f0().f1().….fn();プログラムの計算順序をメソッド名のトークンの順序と関連付けて考えると, 上は逆向き, 下は同じ向きになっていると思います. 左から右に流れる自然…

SRM496結果概略

気分転換。 250 500 950 Challenge 228.00 196.64 Opened - Score Rank Rate 151.13 160 1540 -> 1630 早解き無理。

高校振り分けアルゴリズム

自分が入学した年まで、母校とライバル校は一括で募集を行っていて、合格者は何らかの方法で半分ずつ振り分けられていました。高校の目の前に住んでいるのにもう一方に入れられてしまった!といった数々の不条理を生んだこの制度ですが、その当時はライバル…

The first NASA Tournament Lab Marathon Match

卒論も切羽詰まってきて出てる場合ではないのですけれど、賞金に釣られて問題を見てしまいました。 何このすごく具体的なMM…。 ちょっと引きました。心置きなく卒論ができそうです。

SRM493結果概略

300 450 1000 Challenge 0.0 Compiled Unopened - Score Rank Rate 0.0 220 1577 -> 1540 だめぽ

SRM492結果概略

うっかり参加してしまいました。 250 550 1000 Challenge 151.13 Unopened Opened - Score Rank Rate 151.13 171 1510 -> 1577 微妙。

hos' Xmas Contest 2010

予定が変わって参加できるようになったので、出てみたものの…完全に腕がなまってますね。でも、当分廃人プレイに費やすのは無理なのでなんかもどかしいです。

卒論…

よく考えたら、たいていのここに書くようなネタが卒論に関係してくるので、こんなところにアウトプットできませんね。 というわけで、移転直後にも関わらず3月頃まで放置になりそうです。。

SRM

残念なことに今月の残りのSRMは予定がかぶっているみたいです。11月に入ってから1回も出ていない気がします。そろそろ練習しないと2度と復帰できない気がしているので、時間作って練習することにしましょう。

ブログ移転

自宅サーバーの調子も自分自身の調子もあまりよろしくないので、プログラミング・コンテスト関連とその他のブログを分離することにしました。これらの関係の記事はこれからこっちに書いていくことにします。また、以前の記事もこちらに移転しました。これか…

SRM

次のSRMが残り少ない必修と重なっているではありませんか! 後でやっておくとしましょう。

SRM

いろいろゆとりに乏しいですし、中間発表も近いのでスルーしてしまいました。 来年のすでに入りかけている予定からすると、こっちのレベルアップもきちんと図っていかないといけないんですけどね。 まあ頑張ります。

不正行為

今回今回Div2で40秒で出すとかあからさまな不正をした人がいるみたいですね。完全に一致とか言う噂も立ってますけど、他の人が開いている問題を見たという程度の不正だとなかなか断定するのは難しいですよね。昔あった250を18秒で出すとかはそのまま残ってた…

SRM485

何か思考が負のスパイラルに陥っているので本日は自宅静養してました。ついでにTwitterでの発言もお休み。でもSRM。250はまあいいとして500は実験すると実質的な計算量がかなり落ちることが分かるみたいですね。気付かず突撃して順位が60位ダウン。だめだめ…

SRM484

MPが回復してきたので参加しました。まさかのりんご回でした。 250 うさぎ数の個数を求める問題。うさぎ数とは各桁の数字の和S(x)が、S(x^2)=S(x)^2を満たす数。 100万くらいまでやってみて3以下しか出てこないことが予想できたので、候補を絞って求めてやっ…

JAG夏合宿

ラストチャンスのICPC国内予選で負けてOBOG会に入ったので、夏合宿にスタッフとして参加していました。剃刀忘れて伸び放題になっていた人です。運営側の苦労を色々知りました。基本的にまだまだ雑魚ですけど、頑張ろうと思います。 あといろいろミスりました…

SRM482

前回移動のためスルーしたのでちょっと間があきました。このところ眠気がひどいので、今回も頭が重かったです。 250 規則に従って消去していって最後に残るものを求める問題。 最初n^2で書いたら当然TLEだったので、高速化しました。ライブラリ使わずに配列…

最近

MPが足りなかったり、スケジュールが合わなかったりであまり参加できてないです。 今はちょっと調子悪いですけど、新学期モードになったらもうちょっと頑張っていきたいと思います。