ユークリッドの互除法を考える。 数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 …