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

Programming

ICFPC参加記

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

IOI2011メモ

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

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

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

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

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

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

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

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

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++ プリプロセッサマクロで…

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…

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使えなくなるディストリによるが

おてがる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>…

遅延評価によるエラトステネスの篩のお話

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

SuperCon2010予選通過報告とソース

去年優勝しましたZATORIKUは今年もSuperCon楽しませてもらいます。二連覇しますよ。期末なのでこれ書いたら寝ます。 解法概要 mが奇数のとき0 そうでない場合、[ [0,1],[1,1] ]^nと[ [1,2],[1,3] ]^(m/2)のしかるべき位置の積 行列累乗はバイナリ法を利用 O(…

僕がScalaに惹かれた理由を4つくらい挙げてみた

静的型付け教 const教 クロージャ教 メソッドチェイン教 まとめ: JavaとC++とRubyの影響

夏の行事の宣伝

JMO夏季セミナー JMO夏季セミナー公式ページ 数学オリンピック財団が主催するセミナー。 数学関係の本がいくつかあり、好きな本を選ぶ。その本を選んだ人と担当のチューターでゼミを行い、最後に発表する。自由時間は遊ぶ。期間:8/22〜28 山梨の清里に篭る。…

ScalaでProjectEuler 1 to 10

#!/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…

Google Code Jam(GCJ) 2010 Online Round 1: Sub-Round C

概要 ぐーぐる先生のプログラミングコンテスト。Online Round 1は150分のSub-Roundが3回開催され、各Sub-Roundから上位1000人が選ばれる。通過者は次のSub-Roundには参加できない。通過しなかった場合は参加しなかった場合と同じく、次のSub-Roundに再挑戦で…

Google Code Jam(GCJ) 2010 Qualification Round

概要 ぐーぐる先生のプログラミングコンテスト。18歳以上だと選ばれてダブリンとか行けるらしい。裏山。入力を得て出力を提出する形式が特徴。つまり、お好みのマニアックな環境(期限なし無料で入手可能なものに限る)でよいらしい。だが俺はC++でいいや… A …

アジア太平洋情報オリンピック(APIO)2010 China

概要 アジア太平洋地域の国々でこっそり開催しているマイナーコンテスト。IOIの形式に則る。今年は5時間3問。その存在感のなさの割に非常に難しいのが特徴。 1. Commando 0から100のn個の整数列が与えられて、これをいくつかの区間に分割する。各区間の和を…

Ubuntu 10.04でQt Creatorが異常に重くなる現象の回避

ヘルプが悪さをしているらしい。qtcreator-docとqt4-docを削除すればよい。 sudo aptitude remove qtcreator-doc qt4-doc根本的な解決をするまではこれで対処。

TopCoder MM59

概要 はじめてのまらそんまっち 4921.0000 + 3924.0000 + 3909.0000 + 5622.0000 + 3230.0000 + 6120.0000 + 1640.0000 + 2810.0000 = 23083695.0096位Rating: NON-RATED → 1397(blue) (+1397)上出来です 問題 棚に高さ10の底板を複数とりつける。底板の上に…

TopCoder SRM469 Div1

概要 75.00 + 0.00(Failed System Test) + 0.00(Unopened) + 0.00 = 75.00553位Rating: 1782(yellow) → 1669(yellow) (-113)くそう… 250 TheMoviesLevelOneDivOne 映画館に広い座席(縦横それぞれ10億)がある。いくつかの席は予約されている。 John and Brus…

TopCoder Member SRM 468 DIV1

Overview 140.04 + 295.34 + 0.00(Opened) + 0=435.38 167th in Div1 SRM Rating: 1698 → 1782(+84) なんかRating自己記録更新っぽ 250 Easy 携帯のT9入力を考える。 アルファベットにはそれぞれ1-9の番号の1つと関連づけられる。ある番号列はそれに合致する…

TopCoder SRM 466 DIV1

Overview 145.00 + 235.33 + 0(Unopened) + 0 = 380.33283rdSRM Rating: 1648 → 1698(+50)とりあえずyellow残留やたー… 250 Easy 0、または約数を奇数個もつような数(leading zeroもあり)が当選ナンバーである。今あるナンバーの桁を書き換えて当選ナンバー…

1年間ほど悩んできた問題が、sudo killall NetworkManagerを打つだけで解決した。死にたい。

問題: Debian(Ubuntu)で無線LANが繋がらない。/etc/network/interfacesとifupで繋ごうとした場合。解決方法: NetworkManagerが邪魔するので殺す。

Ustで対談してきたらしいですよ。

touron, toron makeplex on USTREAM. ComedyUstreamで対談やります! - chokudai Lab blogUstreamで対談してたみたいですね>< - CanI’s Diary僕とかいろいろな人がmakeplexさんとこで対談してきたっぽいです。なかなか面白かったですが、撮ってるときには…

国際情報オリンピック(IOI)の日本代表になりました。

JOI合宿概要 3/19〜25までJOIの合宿があり、20日と21日は4時間3問、22日は5時間3問、23日は5時間4問の問題を解き、その点数の上位4名が代表になりました。代表になったひと: qnighy, JAPLJ, semiexp, utatakiyoshiフィードバックの速さがJMOとの大きな違いで…

情報オリンピック合宿および数学オリンピック合宿に行ってまいります

3/19〜3/25まで情報オリンピック合宿、3/25〜3/31まで数学オリンピック合宿に行ってまいります。情報オリンピックはカナダ大会代表4名、数学オリンピックはカザフスタン大会6名の選抜なのです。情報オリンピックも数学オリンピックも枠が実質増加しているの…

TopCoder HighSchool tournament(TCHS) Round3

Round1はoox、Round2はoooでしたが、今日は調子のってちょっと残念でした。Round3の参加者は250名、残るのは100名。今回はoxxでした。Rating(TCHS): 1616 → 1692(yellow) 250 width*heightの文字の2次元配列が'.'で初期化されていて、これの縁を左上から時計…

1ファイルなC#コードのコンパイル@Linux

短いJavaコードをMakefileでコンパイルする(Antは面倒なので書きたくない)派なので、C#でもやってみた。mono-gmcsとmono-runtimeがあれば十分だと思う。 mono-runtimeにbinfmtsの設定が書かれているはずなので make ./Hello.exe で動作する。 Makefile #!/us…

情報オリンピックは64点でした

勝った!!!!!!!何かに!!!!!!!! (略)採点結果をお知らせします.A ランク (64点)あなたは優秀な成績でしたので,(略)第22回国際情報オリンピック『日本代表選手選考会』(春季トレーニング合宿)に招待いたします.(略)問1 (20点) 内訳 ○,○,○,○…

情報オリンピック2010本選 感想と解説

し ん だ\(^o^)/ 概要 常連がみんな死んだなどと言っている。むごい。いくら凄い人々ばかりだったとはいえ、去年満点を3人だしてしまったので、今回は満点阻止レベルの問題構成になると予想したら、やっぱりそうなった。ちなみに自分は3完。いろいろとヤバ…

GCCのWarning Optionをあるだけ列挙

#ERR = -Werror OPT = -ansi -pedantic-errors $(ERR) -Wall -Wextra -Wformat=2 -Winit-self -Wswitch-default -Wswitch-enum -Wsync-nand -Wstrict-aliasing=1 -Wstrict-overflow=5 -Wsystem-headers -Wfloat-equal -Wtraditional-conversion -Wdeclaratio…

人材獲得作戦の問題を反復深化深さ優先探索で

人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題ほか 反復深化深さ優先探索は、深さ優先探索の深さのリミットを少しずつ増やしながら行う探索で、幅優先探索に近い性質をもつ探索。ゲーム木のように浅くて広い探索木の場合にメモリ効率が良く好ま…