2010-01-01から1年間の記事一覧
みんな大好きScalaですが、immutableなPriorityQueueが標準で無かったので試しに作ってみました。想定バージョンはScala 2.7.7です。Immutable PriorityQueue in Scala — Gist データ構造 今回は優先順位つきキューの実装に、Leftist Heapというヒープを使い…
Download Coq(英語) ダウンロードしなければ何も始まらない。 Download | The Coq Proof Assistant ちなみにLinuxディストリならcoqideパッケージをインストールするのが吉 Coqの入門記事を書く会 そこそこ体系的な入門サイト 2010-09-02 - ひとり勉強会 201…
404 · GitHub 今回はJavaで挑んでみた 1 4つの時間(秒)の和を求めて分秒にしなさい。 やるだけ import java.util.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; public class Main { static Scanner sc = new Sc…
↓今読みなおすと頭抱えたくなるような記事なんですが残しておきます基本的なことは 黄金原本更新, 【もはや最短理解でもなんでもない】なぜ5×3ではなく3×5なのか - 跡地, たくさんの反響ありがとうございます - ワタタツの日記!(2010-11-13)に譲るとして。あ…
JOI(日本情報オリンピック)予選 第13回 予選 1. 平均点 (Average Score) 2. 投票 (Vote) 3. 超都観光 (Super Metropolis) 4. 部活のスケジュール表 (Schedule) 5. タクシー (Taxis) 6. 小籠包 (Xiao Long Bao) 第12回 予選 1. 宿題 (Homework) 2. 数当てゲー…
パソコン甲子園の夜の肴にしようと思い準備ネタ元: グーグル、分散処理のためにデザインされた言語「Sawzall」をオープンソースで公開 - Publickey download and extract szl - Szl - A Compiler and Runtime for the Sawzall Language - Google Project Ho…
報告が遅れましたが、去る8月14日から21日の間、カナダのWaterloo大学で開催された第22回国際情報オリンピック(22nd IOI)に行ってきました。なんか早くも忘れかけているのですが、レポートを書きます。 国際情報オリンピック(IOI)について 国際情報オリンピ…
Day7 フリータイム Conestoga Mallに連れてってもらった 携帯屋多すぎ hmvが小文字だった H&Mがあったけどだからどうということはなかった ゲーム屋があったがラブプラスは売ってなかった 電気屋に行ってiPadで遊んだ ザコーブのDVDが売ってた。買わなかった…
Day6 Niagara Falls 言うまでもない有名な滝 前回のexcursionで楽しめなかった(日焼けだけした)であろうsemiexpが「楽しそう」などと言うのでsemiexpの意向に従って行動することにした 朝超早かった 行きのバスは寝たのでしらない 午前中は適当にgdgdした。…
Day4 Canada's Wonderland、いわゆる遊園地 バスの中でItalyな人々が歌いまくってた。Nel blu, di pinto di bluだけわかったので歌ってやった。 入園するところで荷物チェックされた 突然写真を撮られた。帰りに興味があれば買えということらしい いまいまカ…
直前合宿 だいたいみんな成田エクスプレスだった ホテルは良かった IOIの問題の解説が予定されていたが、およそ皆解いていたので暇だった APIO>>>越えられない壁>>>IOI ルール変更の確認とかした 夜更かしした 飛行機 カレーは安定 電源ついてて大勝利 iPad…
8月14日から8月21日にかけてカナダのWaterloo大学で開催される「第21回国際情報オリンピック」に日本代表として参加してまいります。 情報オリンピックについて 情報オリンピックは、数学オリンピックや、化学、物理、生物、天文学オリンピックなどと並ぶ、…
Linux使ったら便利すぎて他のOS使えなくなるディストリによるが
Q. サンプルタスクのGuessのサンプル解答および想定入出力に誤りがあるようですが。 A. 把握しました。修正します。報告ありがとうございます。 Q. 参加者の半数以上が同点だった場合、金メダルの授与条件とメダル全体の授与条件が矛盾すると思うのですが。 …
valgrindにあわせて、この前使ったoprofileの記事も書こう。oprofileはIOIでは使えないけど、SuperConの定数倍最適化のために使った。前回と同じように、-gオプションを付けてコンパイル。で、以下のようなシェルスクリプトを用意した。 #!/bin/sh sudo opco…
IOI2010の試験環境にはvalgrindとdddとgdbがインストールされているので、valgrindとdddをちょっと使ってみた。こんなソースを用意。 #include <cstdio> #include <vector> using namespace std; int main(int argc, char **argv) { int n = 100; vector<int> v(n); for(int i = 0</int></vector></cstdio>…
2010-07-14 - メモ用紙の裏Ubuntu(lucid lynx)+GCC4.4.3では以下を実行するとSEGV。 条件を変える(配列ではなくvectorを使う、ソート対象を17より大きくする)と、他の環境でもSEGVするかも。 #include <algorithm> bool cmp(int x, int y) { return true; } int main(in</algorithm>…
優先順位つきキューを用いたエラトステネスの篩の変形がある。 優先順位つきキューの削除と挿入のコストをO(log n)とすると、エラトステネス全体のオーダーはO(n log^2 n)である。追記:以下は整数値オーバーフローのため値がおかしい。かつ、修正すると低速…
http://d.hatena.ne.jp/laciryl/20100712#1278918861 のお話。対象となるのは以下の有名なHaskellコード。 primes = sieve [2..] sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] これをScalaで書く。 // This Haskell Code in Scala // primes = s…
DebianとかUbuntuでカーネルモジュールを作ってみた 環境の準備 $ sudo aptitude build-dep linux-image-`uname -r` $ sudo aptitude install linux-headers-`uname -r` まけふぃれ $ mkdir hello_ko $ cd hello_ko $ vim Makefileobj-m := hello.o KDIR := …
去年優勝しましたZATORIKUは今年もSuperCon楽しませてもらいます。二連覇しますよ。期末なのでこれ書いたら寝ます。 解法概要 mが奇数のとき0 そうでない場合、[ [0,1],[1,1] ]^nと[ [1,2],[1,3] ]^(m/2)のしかるべき位置の積 行列累乗はバイナリ法を利用 O(…
http://www.famm.jp/wireless/modules/weblog/details.php?blog_id=326これを読んで、自分は全然加速しなかったしもうだめだと思った。しかしめげてる場合じゃない。あしけ頑張る。
静的型付け教 const教 クロージャ教 メソッドチェイン教 まとめ: JavaとC++とRubyの影響
vector > table(width, vector(height)) 遅い(らしい) ちょっと冗長な気がする int table[WIDTH][HEIGHT] サイズ情報は保持されない スタックに確保するので、スタックオーバーフローの問題あり 0でのfillのみできる static int table[WIDTH][HEIGHT] サイズ…
JMO夏季セミナー JMO夏季セミナー公式ページ 数学オリンピック財団が主催するセミナー。 数学関係の本がいくつかあり、好きな本を選ぶ。その本を選んだ人と担当のチューターでゼミを行い、最後に発表する。自由時間は遊ぶ。期間:8/22〜28 山梨の清里に篭る。…
1 IOI表敬訪問: 8/23 SuperCon: 8/23〜8/27 JMO夏季セミナー: 8/22〜8/28 JOI夏季セミナー: 8/23〜8/27もはやJOI夏季セミナーは大岡山でやればいいのにとか思ってしまう。自分は表敬訪問は致し方ないのでSuperConは1日目だけ頼んで休ませてもらおうと考えて…
#!/usr/bin/scala !# { println((0 to 999 toList).filter(s => (s%3==0 || s%5==0)).foldLeft(0)((a,b)=>a+b)) } { def f(x:Int,y:Int,s:Int):Int = if (x <= 4000000) f(y,x+y,x*(1-x%2) + s) else s println(f(1,2,0)) } { def f(n:Long,x:Long):Long = i…
設定が全部ファイルであり、あなたのデータはホームディレクトリ内に集約されている。OSがぶっ壊れたので同じものを再インストールしてバックアップを復元したら設定も復元して特に不具合とかはない。ほんとLinuxでよかった。
概要 ぐーぐる先生のプログラミングコンテスト。Online Round 1は150分のSub-Roundが3回開催され、各Sub-Roundから上位1000人が選ばれる。通過者は次のSub-Roundには参加できない。通過しなかった場合は参加しなかった場合と同じく、次のSub-Roundに再挑戦で…
かたわ少女開発者ブログ: かたわ少女Act1の日本語訳リリース!こういうプロジェクトを本気で進め、ここまでの成果を為し遂げた人達は本当にすごいと思います。これからも期待しています。残念なことに自分はこれをプレイする時間はないですが、とりあえずシー…