ユークリッドの互除法を考える。 数a,bが与えられる。 1. 最初はx=a, y=bとする。 2. xをyで割った余りにする。 3. yをxで割った余りにする。 4. 2に戻る。 5. xかyが0になったときに、もう一方が最大公約数である。 ここで、この数x,yを、別の方法で表現す…

qsort.hqq9+ +h+hqhqq output Hello, world! Hello, world! +h+hqhqq Hello, world! +h+hqhqq ++hhhqqq 概要 クイックソートを40文字以内で、と誰かさんに言われたのでHQQ9+を作った。 もうそのネタ飽きたとかいうな。 hqq9+.rb acc = 0; src = $<.read src.…

正確には、RiemannZetaをDirichletのL関数に置きかえた「拡張リーマン予想」(一般化されたリーマン予想、GRH)が証明されると、暗号解読の鍵となる、とかそんなのらしい。例えば、拡張リーマン予想が証明されると、Miller-Rabin素数判定法による決定的な素数…

まずは140文字で要約: 情報オリンピックで使う言語はC++ > Java > C。特にCはライブラリの不足が激しい。ヒープとか覚える気がないならCはやめたほうがいい。Javaが有利なのは多倍長と幾何だがあまり出ない。その他の点ではC++が良い。つまりC++がおすすめ。…

パソコン甲子園のコンテスト形式は、明らかにICPC(国際大学対抗プログラミングコンテスト、International Collegiate Programming Contest)を意識してるじゃないですか。だから、パソコン甲子園って名前をやめて、JKPC(日本高校対抗プログラミングコンテスト…

UnionFindのコードを書けるようにした。去年の本選5番はPriorityQueueを使う方法が想定されているが、UnionFindでも解ける(とhosがいってた)ので、試してみた。PriorityQueueのコードも書いた。殆ど同じ。 #include <algorithm> #include <climits> #include <cstdio> #include <iostream> #include <utility></utility></iostream></cstdio></climits></algorithm>…

benchmark of 10,000,000 number's input time ( yes 100 | ./a.out ) Optimization Flags | number |iostream| stdio ---------------------+------------+--------+------ CXXFLAGS="" | 100 | 9.830 | 3.664 CXXFLAGS="-O2 -Wall" | 100 | 10.006 | 3.831…

主に漸化式で与えられる問題を解くのに使われる動的計画法(DP)。DPとメモ化再帰の定義を、フィボナッチ数列を計算するプログラムを例にして考える。 /* 「フィボナッチ 再帰バージョン」 * フィボナッチ数列を漸化式の通りに実装したもの * この計算ではO(1.…

C++での解答例。 問題1 /* * JOI 2010 予選 問題1 C++解答例 by qnighy */ // 問題: // レシート // http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t1/2010-yo-t1.html // 豆知識: // iostreamは遅いので、僕はstdio.hを使っています。 // c…

本選いくひとはよろしくね。6番はDPであってたっぽいです。

たいへんよくできました＠Ruby1.9 def fun(n, s) s.scan(/#{"(.)"*n}/).transpose.map &:join end p fun(3, "123123123") 時間とか測ってないけどわりと一瞬だったんじゃないかな。http://ameblo.jp/programming/entry-10001721422.html

開始早々サーバーが激重で問題を開くのに15分以上かかった。結局18時までに延長となった。 SSLを使うようになってた他、内部システムをいろいろ変更しているようなので、まあいろいろあったんだろう。 見たかんじ、ブラウザから定期的にサーバーにアクセスが…

シードなので受けなくてもいいのですが、 二年連続で満点だったのに、去年は満点とれず悔しかったので今年は満点が目標です。

例えば仕分けで、スパコンの担当者の説明は上手でなかったとして、 「世界一になることが重要なのか、スパコンの目的は他にあるのではないか」 という説明不足の指摘だったとしたら適切だと思うけど、 どう考えても、「予算減らせ」って意味だったし、 「科…

テレビでやってたやつ。 円柱状の物体、というか所謂コインを積んでいって、倒したら負けというゲーム。あのゲームの、現時点での置ける範囲を計算するシミュレーションを作ってみた。A simulation program for "Coin Tower", a coin-stacking game. — Gist …

今年の僕は紅白を見ることにします。たぶん。去年はアニソン三昧とかしてましたけどね。淡路…

君にはPerl6という最愛の恋人がいるだろ？

「Googleのアカウント以外でログインできる機構を作る方法」を模索しなければいけないと思った。といっても僕にはそれをするだけのリソースがない。

仕「世界一である必要はあるのか。二位では駄目なのか」 俺「オリンピックで金メダルが要らないとでも言うのか」 仕「オリンピックは参加することに意義があるのだ」あ…れ…？

はてなパーカー欲しい！ ブラックが欲しいです。GoogleのTシャツに重ね着したいです。

パソコン甲子園の問題1が綺麗に書けたで賞を今さらやってみた #include <stdio.h> int main() { while(1) { int i, hands[5], count[3]={0}, states[]={2,3,1}; for(i=0;i<5;++i){ scanf("%d", &hands[i]); if(!hands[i])return 0; hands[i]--; count[hands[i]]=1; } </stdio.h>…

だめです。賞金の額が違います。 チームと結果 プログラミング部門P04、筑波大学附属駒場高等学校、チーム名「18.039リットル」。 三位。なお本校から本選出場したもう一つのチーム、「rand()」は優勝。 id:JAPLJのところは準優勝。上位3チームがなんかデジ…

俺達のパソコン甲子園は終わりました。賞金もらえるといいな。会津若松ワシントンホテルに泊まりました。インターネットが使えます。幸せ。まだ日付は越していませんが、昨日の敵は今日のダチです。ということでid:JAPLJを無理に誘い、Goを勉強しました。 イ…

最近アルゴリズムやってません。死にます。でも足掻きます。パソコン甲子園の問題は、明らかに体力ゲーというか、速度と正確さが競われるというか、女子学院の算数の入試問題みたいで今から心が折れます。あと環境にVimが入ってないらしいですね。VimとEmacs…

Cプリプロセッサメタプログラミングで、文字列系泥沼関数型プログラミング - 簡潔で覚えやすいタイトルを3秒で思いつく程度の能力を何気なく公開したところ、大量のブックマークをつけていただきました。みなさんありがとうございます。ブクマコメには、変態…

色的に。Windows ロゴ - Google 検索

今年の文化祭で書いた記事です。 - C言語といえば、いやなイメージ、過去の遺産といった感じがあるかもしれません。C言語のネガティブな側面というと、やはりポインタやメモリ管理などが難しい、ということが思いつくかもしれません。しかし、C言語のポイン…

IE6 IE7以降 Firefox、Opera、Safari、Chromeなど テキストブラウザ IE5.5以前、Netscape の5つに分類すればいいと思う。

SSLは、以下の3つをごちゃ混ぜにしている。 身分証明 同一性証明 暗号化 身分証明が必要なのが厄介というか、許せない。身分証明は不要で暗号化だけあればいい場面を知ってるでしょ。Googleは信用していいけど、友人、身内や、自分さえ信じちゃいけない、と…

OSASKは形式上オープンソースっぽいだけでオープンソースだなんて概念これっぽっちも継承してないし、今回の騒動はそのことを確認したに過ぎないので別に良いんじゃないんでしょうかね。 ↑2009/11/07追記オサスクドット ジャパン： おさゲなニュースと雑談サ…