Programming
PerlとC++は世界一。 #!/usr/bin/perl srand(time); my $a = 0; my $b = 0; for(my $i = 0; $i < 1000; $i++) { (rand(2)<1 ? $a : $b) += 1; } print "$a, $b\n" #include <cstdio> #include <cstdlib> #include <time.h> int main(int argc, char **argv) { srand((unsigned)time(NU</time.h></cstdlib></cstdio>…
はじめてのあいおーあい。ろくに確認もせずテストデータにとりあえず投げた結果玉砕し、その後しょーもないことで時間を潰した。練習量が足りない。死にたい。 problem IPSJの雑誌とテレビの両方で見かけたので解いてみようと思った。問題の名称がどう見ても…
今日は結局何も書けなかったのでボゾソート(ボゴソートの仲間)を適当に書いた。 #!/usr/bin/ruby1.9.1 # -*- coding: utf-8 -*- class Array def bozo_sort! defined? yield or return bozo_sort!{|a,b|a<=>b} until (1...size).inject(true){|s,i|s && yiel…
今日から少し、典型DPを扱ってみようと思う。最長共通部分文字列(longest common substring)と最長共通部分列(longest common subsequence)。前者は連続という条件つきで、後者は連続でなくても順序が維持されていればよいというもの。 前者はO( (n+m)min(n,…
分散化の場合のイメージと大分違うような気がするけど、直感レベルでの話しかしてないからよくわからない。 まあなんで僕が(n/log n)倍かというと、実際並列アルゴリズムが大体そんな感じっぽいから。 畳みこみ(最大値や総和)の計算 O(n) → O(log n) ソート …
という気がしてきたので、文字列検索の有限オートマトン化をしてみた。…普通にこれでいいじゃん！有限オートマトンの生成にかかる時間およびメモリはn=キーサイズ,c=文字の種類とおいてO(cn)なので、そこで少し遅れをとるけど、検索が非常にシンプルで高速(…
だが解説は面倒なのでしない。 maketableさえ覚えればsearchはそれと形が似ているので簡単そう。 #include <cstdio> void kmp_maketable(const char *key, int *table) { table[0]=-1;table[1]=0; int i=2,j=0; while(i==0 || key[i-1]) { if(key[i-1] == key[j]) { </cstdio>…
最低限だけ書くと次のようになる。 CXXFLAGS = -O2 -Wall LDFLAGS = -lm all: hello # In Windows, it may be "hello.exe" clean: $(RM) hello CXXFLAGSは、C++コンパイラに対する引数。Cコンパイラに対する引数はCFLAGS。最適化や警告、インクルードディレ…
「四角に切れ」とは以下のような問題である。 あるサイズの格子(将棋盤タイプ)が与えられる。 マスには数字が書かれているか、書かれていない。 格子全体を長方形の集合に分割する。 全ての長方形にちょうど1つずつ数字が入り、かつ長方形の面積がその数字と…
UbuntuのGCCとかでこういうのが出る。 解説 「scanfの戻り値を使ってないよ」→つまり、scanfが失敗した場合について考えてないコードを書いてるから気をつけろという警告。 対策1 scanfの戻り値を検査する。 scanfの戻り値は、成功した変数の数、もしくは-1…
概要 番号つきの区間の集合が与えられ、被らない最大個数の区間集合を求める。ただし最大個数の区間集合が複数通りある場合、辞書順で小さいものを選ぶ。 手法 被らない最大個数の区間集合を求める問題は、簡単なDP(区間をendで整列し、ranges[upper_bound(r…
piがHaskellで組んでこれより速くCで組めるわけないとか挑発されたので、つい… 性能 12*34*5+6*7-8*9 = 2010 のような小町算を生成します。 (1*2/3-4*56)/(7-8)*9 = 2010 のような、括弧を使うものも生成します。 2-(3-4)のような右結合は、等価の左結合、つ…
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか の問題を解いてみた。アルゴリズマーとしてはこの程度の問題20分で書けないとパソコン甲子園とかで辛いなあと思うのですが、40分でできました。頭を使って解けるかどうかは知りませんが、知識…
某Hiroaki Softwareが、Win32APIコードをcuコードに混ぜてコンパイルしようとして妙なエラーに巻きこまれたらしいので調査したら、CUDAのコンパイラであるところのnvccはクソであることが判明した。具体的には、CreateWindow()中に一行コメントを書こうとし…
Objective-Cとは SmalltalkのOOPをC言語にくっつけた、Mac王国の公用語。 Objective-C++とは Objective-CとC++をとりあえず一緒にした謎言語。 Objective-C++0x(造語)とは Objective-C++でC++0xを有効にした超言語。 Install(Ubuntu) % sudo aptitude instal…
バイトニックソート(bitonic sorter)は、並列処理に適した「ソーティングネットワーク」という種類のソートアルゴリズムで、直列での時間計算量はO(n log^2 n)ですが、最大nで並列できて、その結果O(log^2 n)で計算できるようになります。 マージソートの類…
/* ヒープソート(heapsort) ヒープ構造を用いたソート方法 特徴 1. 「その場」(in place)で実行できる(マージソートやバケットソートは別の配列が必要になる) 2. 最悪でもO(n log n)で実行できる(クイックソートの最悪ケースはO(n^2)) 3. かっこいい 4. 安定…
前回の記事でやった強連結成分分解とトポロジカルソートの結果を利用してDPすればいいだけ。 ただし、この過程ででてくるDFSを再帰でそのまま実装するとスタックオーバーフローを起こす。おそらく自前スタックで書けということだろう。 変数をスタックに移す…
Spaghetti Sourceにワンパスでできるプログラムがあったので読んだ。 http://www.prefield.com/algorithm/graph/strongly_connected_components.html グローバル変数 num[]…訪問順(time) low[]…代表元リンク S、inS…成分未確定頂点のスタック(inSはスタック…
あけましておめでとうございます。このブログは通常営業となりました。 概要 http://turi2.net/blog/724.html http://d.hatena.ne.jp/nitoyon/20070629/four_operations_implementation_in_javascript 多倍長での除算がこの前うまく実装できなかったので、復…
ユークリッドの互除法を考える。 数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であってたっぽいです。
