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

ipc_botの紹介

この記事はTheorem Prover Advent Calendarの22日めの担当記事です.今年の僕の持ちネタの一つですが,ipc_bot というTwitter botを作りました.https://twitter.com/ipc_botこのbotは直観主義命題論理の命題を投げると解いてくれるbotです. 仕組み 証明を…

情報オリンピック予選 2014

情報オリンピックの予選に参加しました.(予選は誰でも参加できます)次のような制約で解くことにしていました. 1番は Wolf RPGエディター 2番は TeX 3番は Scratch 4番は Excel 5番は APL 6番は Bash 結局1と4を解きました. 1番 Wolf RPGエディターで解き…

夏季セミナー参加記&反省会

来年やる人が同じ失敗をしないために色々書いておきます途中で「です・ます」調でなくなっているのは息切れです。めんどくさいので直していません 参加記 端的にまとめます 場所:今年は埼玉の準山奥でやりました。2009年に僕が生徒として参加したときと同じ…

情報オリンピック夏季セミナーの参加記一覧とか

2013/08/26 - 08/30の間、夏季セミナーというのにチューターとして参加していました。以下はその記録として参照できる各種媒体へのリンクです。参考:去年のリンク集 募集案内 実施の概要 参加者のtwitterリスト 発表会の様子(Togetter) その1(AI) その2(グ…

ICFPC参加記

チーム名 qnighy メンバー qnighy (計1名) 記録 08/06 ICFPCの登録期限が目前に迫っていたのでEasyChairに登録する。 08/07 EasyChairに登録するだけではだめで、ICFPCという名前のカンファレンスに論文を登録したことにしないといけないことを知り、論文の…

今週のContest Management System (2)

CMS (Contest Management System) の最近の動向について書いてみようかなと思います企画2週目 DBモデルの修整とインポーターのダイエット lerks(Luca) がDBモデルの細かい問題点をチェックし、修整しています。例えば、アクセス元の許可リストとしてIPアドレ…

今週のContest Management System

CMS (Contest Management System) の最近の動向について書いてみようかなと思います クロアチアと日本での採用 CMSが次の大会で採用されました。 クロアチアの3段階ある国内大会 日本の国内大会のうち、代表選抜合宿 クロアチアでの採用を報告したメールによ…

CoqのtacticをOCamlで書く話

CoqのtacticをOCamlで書いてみたので、同じようなことをしたい人のためにメモ。なお私はOCamlについてはそれほど詳しくないので、そこの正確性については注意が必要。 同じ事をしているtacticがないか探す 同じようなことを考えている人は必ずいるはず。とい…

Advent Calendar Advent Calendar (2012) 12日目

飛び入りで書きます。Advent Calendar Advent Calendar僕が今日紹介するのはLispギャグアドベントカレンダーです。 Lispギャグアドベントカレンダー 2011 Lispギャグアドベントカレンダー 2012 Lispに関するギャグが、かわいい絵とともに書かれています。で…

Re:永続データ構造が分からない人のためのスライド

この記事はCompetitive Programming Advent Calendar 2012の12/01担当分の記事です。永続データ構造が分からない人のために、「Re:永続データ構造が分からない人のためのスライド」というスライドを頑張って作りました。 slideshareで見る SpeakerDeckで見る…

情報オリンピック夏季セミナーの参加記一覧とか

2012/08/25 - 08/29の間、夏季セミナーというのにチューターとして参加していました。以下はその記録として参照できる各種媒体へのリンクです。 募集案内 実施の概要 参加者のtwitterリスト 発表会の様子(Togetter) その1 その2 その3 その4 その5 slideshar…

お久しぶりです

qnighyです。ブログ移行しました。ここまでにあった出来事 東京大学(理科一類)合格 (余裕の点数でした) 情報オリンピック春合宿(チューターとして参加) ICPC国内予選(学内予選落ち) 私立プログラミングキャンプ参加 情報オリンピック夏季セミナー(チューター…

センター試験参加記

前提 qnighyは東大理一志望で、他の大学や科類には興味ない。東大の前期と後期のみ受験予定。 qnighyの強みは数学、弱みは国語。 2012年東大のセンター概要 センター試験は国語・外国語・数学・社会・理科が各200点ずつで最大1000点分の試験を受験できるが、…

Krakatoa and Jessieを用いた、Javaプログラムの正当性&安全性証明(アルゴリズムもあるよ!)

概要 Javaプログラムに専用の記法で満たすべき条件を形式的に記述し、それをCoqの問題に変換して手動で証明する。この記事はCompetitive Programming Advent Calendar 2011およびTheorem Proving Advent Calendar 2011の12日目の担当記事である。 用意するも…

Why 2.30とWhy3のビルド&インストール (Ubuntu)

目的 これに続く記事において、Krakatoa+Why3で証明を行うため。 想定環境 Ubuntu 11.10 (oneiric ocelot) なお、筆者の環境はamd64。 関連パッケージの準備 余計なのも書いてるかも。 $ sudo apt-get install build-essential devscripts dh-ocaml ocaml-no…

IOI2011メモ

07/20 荷物整理 パソコン…一台あれば十分だが、二台持っていった。 衣服…下着は毎日替える。他は適度に使い回し。 書籍…「計算困難問題に対するアルゴリズム理論」を暇つぶし用に。また、競技中は紙の辞書を使用できるので、念のため持参した。(ただし、普通…

高校生がアルゴリズムで世界に挑んできます

2011年7月22日から29日にかけて、IOI2011 (詳細は後述) がタイで開催されます。 以下の4名が日本代表として参加します。 村井 翔悟 (開成) 原 将己 (筑駒) ←自分です 今西 健介 (八千代松陰) 城下 慎也 (灘) 以下では、IOIに関してひと通り説明したあと、今…

第23回国際情報オリンピック(タイ大会)の日本代表になりました。

IOI概要 国際情報オリンピックは、問題を効率よく解くアルゴリズムに対する洞察力を競うためのプログラミングコンテストであり、数学・生物・化学・物理と並ぶ国際科学オリンピックの一つであると同時に、数あるプログラミングコンテストのうちの1つでもあり…

情報オリンピック合宿中止

まえがき 僕のいる地域は東京の隣にある多摩ニュータウンという地域で、地震の被害については交通機関のマヒ以外は無事でした。震災にあっている人のために出来ることは限られているので、はてな経由で200ポイントだけ寄付したのち、元の生活に戻ろうという…

こんなWikipedia○○言語版ってあり?

Wikipediaにはすごい数の○○言語版があります。 Wikipedia:全言語版の統計 - Wikipediaによると現在279言語ですって!その中でも目を引くものがいくつかあったので紹介します。 エスペラント http://eo.wikipedia.org/ http://eo.wikipedia.org/:image:small …

SELinuxを独学したよ。

こんにちは。今回は誰得感の否めないSELinuxエントリです。しかも独学なのでかなり眉唾物です。SELinuxのポリシーをスクラッチで書くのが目的です。既存のポリシーを運用する話ではないです。環境はDebian squeezeです。 SELinuxとは SELinuxは、Linuxにおい…

優先順位つきキューが壊れたのでセグメントツリーを使ってDijkstraを実装してみました。

ネタを思いついたので実装してみました。As priority_queue broken, we tried implementing Dijkstra using RMQ. — Gistオーダーは変わりません。既にRMQの実装が手元にあるのであれば、こっちの実装方法のほうが楽ということもあるかもしれないとだけ言って…

情報オリンピック参加者の皆さんへ

情報オリンピックに参加した皆さんこんにちは。僕はqnighyです。一応すごい人です。予選で終わってしまった人も、本選で終わってしまった人も、これから合宿に行けるという人もいると思いますが、これ以降も競技プログラミングに精進したい!という人のため…

JOIは銀賞でした

20+20+20+6+20japljの呪詛によって4番がエンバグしました。詳細はあとで調べます。

第10回日本情報オリンピック(JOI)本選

出来事 学校でゼミをやってから代々木に直接行った。 いつもの面子との再会と、きゅうりperyaudo組との遭遇。 Practiceはほとんどやらずにずっと駄弁っていた ちなみに今回はVimではなくEmacsを使うことにした 名刺はPractice中に配りまくった。しかし、40枚…

バレンタインチョコ欲しい!キャンペーン

バレンタインチョコ欲しい! 欲しいプレゼントは… BPS バトルプログラマーシラセ ( DVD2枚組 )出版社/メーカー: スターチャイルド発売日: 2004/03/24メディア: DVD購入: 3人 クリック: 157回この商品を含むブログ (25件) を見る 他の人からのプレゼントもお…

TopCoderのコンパイラバージョンって判別むずかしい…

Java バージョンを調べるAPI。 public void printVersion() { System.out.println(System.getProperty("java.version")); } 上記を実行して調べた結果、1.5.0_08でした。 Java‚̃o[ƒWƒ‡ƒ“‚ðƒvƒƒOƒ‰ƒ€‚ÅŠm”F‚·‚é(Javaƒ}ƒXƒ^[) C++ プリプロセッサマクロで…

C++のiostreamは遅いという話

大量の入出力データを扱う課題を解く際に,入出力の処理に cin, cout ストリームを使用した C++ プログ ラムは scanf, printf 関数を使用した同等のプログラムに比べてとても遅くなることに注意してほしい.よっ て,cin / cout ストリームを使用しているの…

MacBook Air 11インチ別に要らない!

ScalaでimmutableなPriorityQueueを作ってみたよ

みんな大好きScalaですが、immutableなPriorityQueueが標準で無かったので試しに作ってみました。想定バージョンはScala 2.7.7です。Immutable PriorityQueue in Scala — Gist データ構造 今回は優先順位つきキューの実装に、Leftist Heapというヒープを使い…

Coqで独習するならどのページがいい?と聞かれたときのメモ

Download Coq(英語) ダウンロードしなければ何も始まらない。 Download | The Coq Proof Assistant ちなみにLinuxディストリならcoqideパッケージをインストールするのが吉 Coqの入門記事を書く会 そこそこ体系的な入門サイト 2010-09-02 - ひとり勉強会 201…

第10回情報オリンピック(JOI)予選

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)に譲るとして。あ…

AOJ in JOI,PCK 回別リスト

JOI(日本情報オリンピック)予選 第13回 予選 1. 平均点 (Average Score) 2. 投票 (Vote) 3. 超都観光 (Super Metropolis) 4. 部活のスケジュール表 (Schedule) 5. タクシー (Taxis) 6. 小籠包 (Xiao Long Bao) 第12回 予選 1. 宿題 (Homework) 2. 数当てゲー…

今話題のSzl(Sawzall)をUbuntuに突貫インストール

パソコン甲子園の夜の肴にしようと思い準備ネタ元: グーグル、分散処理のためにデザインされた言語「Sawzall」をオープンソースで公開 - Publickey download and extract szl - Szl - A Compiler and Runtime for the Sawzall Language - Google Project Ho…

国際情報オリンピックで金メダルgotしてきました。

報告が遅れましたが、去る8月14日から21日の間、カナダのWaterloo大学で開催された第22回国際情報オリンピック(22nd IOI)に行ってきました。なんか早くも忘れかけているのですが、レポートを書きます。 国際情報オリンピック(IOI)について 国際情報オリンピ…

ここまでのIOI(メモ)#4

Day7 フリータイム Conestoga Mallに連れてってもらった 携帯屋多すぎ hmvが小文字だった H&Mがあったけどだからどうということはなかった ゲーム屋があったがラブプラスは売ってなかった 電気屋に行ってiPadで遊んだ ザコーブのDVDが売ってた。買わなかった…

ここまでのIOI(メモ)#3

Day6 Niagara Falls 言うまでもない有名な滝 前回のexcursionで楽しめなかった(日焼けだけした)であろうsemiexpが「楽しそう」などと言うのでsemiexpの意向に従って行動することにした 朝超早かった 行きのバスは寝たのでしらない 午前中は適当にgdgdした。…

ここまでのIOI(メモ)#2

Day4 Canada's Wonderland、いわゆる遊園地 バスの中でItalyな人々が歌いまくってた。Nel blu, di pinto di bluだけわかったので歌ってやった。 入園するところで荷物チェックされた 突然写真を撮られた。帰りに興味があれば買えということらしい いまいまカ…

ここまでのIOI(メモ)

直前合宿 だいたいみんな成田エクスプレスだった ホテルは良かった IOIの問題の解説が予定されていたが、およそ皆解いていたので暇だった APIO>>>越えられない壁>>>IOI ルール変更の確認とかした 夜更かしした 飛行機 カレーは安定 電源ついてて大勝利 iPad…

プログラミングの国際大会「国際情報オリンピック」に行ってきます。

8月14日から8月21日にかけてカナダのWaterloo大学で開催される「第21回国際情報オリンピック」に日本代表として参加してまいります。 情報オリンピックについて 情報オリンピックは、数学オリンピックや、化学、物理、生物、天文学オリンピックなどと並ぶ、…

子どもにLinuxを使わせるべきでないたった一つの理由

Linux使ったら便利すぎて他のOS使えなくなるディストリによるが

IOI

Q. サンプルタスクのGuessのサンプル解答および想定入出力に誤りがあるようですが。 A. 把握しました。修正します。報告ありがとうございます。 Q. 参加者の半数以上が同点だった場合、金メダルの授与条件とメダル全体の授与条件が矛盾すると思うのですが。 …

おてがるoprofile

valgrindにあわせて、この前使ったoprofileの記事も書こう。oprofileはIOIでは使えないけど、SuperConの定数倍最適化のために使った。前回と同じように、-gオプションを付けてコンパイル。で、以下のようなシェルスクリプトを用意した。 #!/bin/sh sudo opco…

valgrindとdddの練習

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>…

std::sortに全順序以外を指定すると死亡

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>…

Haskellでエラトステネスの篩

優先順位つきキューを用いたエラトステネスの篩の変形がある。 優先順位つきキューの削除と挿入のコストを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…

Hello, kernel world!

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 := …