インターネット

ネットとかブログとかの普及で知らなくていいことを知る機会が増えた気がする。

俺のブログも誰かにとって知らなくていいことを知らせてしまっているのだろうか。

まぁなるようにしかならんかw

たーらーたー

たらったらったらー
たったらーたったらーたったたったらー

今日はICPC国内予選の模擬大会があって、全体で13位でした。

問題が6つあって、3問は解けたのだけど、

あとの1問は妙なバグがあって、1問は終了10分後に完成して、1問は手つかず。


目標は5位だったのだけど、それなら最低でもあと1問は解かなくちゃなぁ。。

んー、、本番は2週間後、、頑張ろう。。

えるとんじょん。

Elton Johnについて俺が知ってることは1つだけ。

オーブンの曲を歌った人。それだけw

Elton John Oven Manual Song
http://jp.youtube.com/watch?v=8GuI4UUZrmw&feature=related

でもこれはすごいと思うわ〜、、

最後盛り上げちゃうところとか天才的、、ほんますごいw

無題

総務省発表、FTTH契約数が1200万件突破。DSLとの差は約55万件に
http://bb.watch.impress.co.jp/cda/news/22197.html

DSLてのはほとんどADSLの数で、FTTHてのは光ファイバーだと思ってもらったらOKです。

いつの間にか光ファイバーが増えてきてるんだねぇ。。

ほんの3年前には、「光ファイバーなんてまだまだ普及は先だろう」って思ってたけど、

知らないうちにADSLに並んでるとはねー、、まぁそういう我が下宿も光なわけですが(笑

ほんと科学技術の進歩ってすごいよねー、、目に見えて変わってるのが分かる。。


技術だけじゃなくアルゴリズムとかも結構進歩してるみたいで、、

昨日一昨日と勉強してたsuffix treeっていう「木」を構築するアルゴリズム、

東大の何かの授業のレジュメを見てたら「このアルゴリズムは06年に発表され〜」

みたいなコトが書いてあって。06年て！一昨年やん！っていうw

まぁ最新のアルゴリズムは複雑過ぎてさっぱり分からんかったけど、、

まだまだ未開拓の分野があるのだなーと思うと、、卒論とか修論とか

画期的なもの書けたらいいなー、書きたいなーって思ってきたw


昨日はちょと凹んでたので寝不足だー、、明日創立記念日だからゆっくりしよう☆

…と思ってたもののバイトがあったことを思い出した(笑

大文字山

登ってきました、、サークルで。

大文字山登るのは2回目なんやけど、、めっっっっっっっちゃきれいで☆

写真とか撮ったけど実際に見るのとは雲泥の差。

京大の人とかで見たい人がいたら連れていきますよ、、

30分汗かくだけでほんと最高の景色が。

京都に旅行にくる予定のある人でも誰でも、、まぁ興味がある人は声かけてくださいな☆

ラーメンズ。

ガイシュツならごめんちゃい。

帝王閣ホテル応援歌
http://jp.youtube.com/watch?v=gqZ0hWuqVAQ&feature=related

音と画像とずれてるからその辺適当にw



こっちはかなり本格的。Japan Cultureとかいうシリーズらしい(笑)

Sushi
http://jp.youtube.com/watch?v=0b75cl4-qRE

ハードディスク。

ハードディスクが回転してる状態で中身だけ転がした動画。

まぁ1分に7200回転もしてたらこうなりますわなw
http://jp.youtube.com/watch?v=yISqCAnROh8


関連動画のところにハードディスクの動いてる様子とか、

バカみたいなドミノとかいろいろあるので暇だったら見てみてw

top

1時ぐらいからとある問題を解いてたのです。

さっき解けたところなのです。

配列のサイズ小さすぎて1回Wrong Answer出してしまったけど。

で、同じ問題を解いた人たちの中で、

自分のプログラムがどれぐらい早いのか、とかが分かる分けです。

今回は0.040秒で解けた(プログラムの実行時間)ので、

「おお、、早い方じゃない？」と思って見てみたら、なんと最速。

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&page=problem_stats&problemid=248&category=5

まぁいろいろ書いてあるけど、

とにかくTop20のランキングの一番上にmiracという名が降臨(笑)

まぁそんなに難しい問題というわけでもないのだけど、

この問題を解いた500人の中で最速のプログラムを書けたのだなぁと思うとちょっと感動。

んー、、今日はいい気分で寝れそうですw

サークルの

新歓コンパ行ってきた。

やっぱり飲み会は嫌いだという結論に(笑

バカ騒ぎしながら飲むのが嫌なのか、

大人数で飲むのが嫌なのかよく分からんけど、

とりあえず大人数でバカ騒ぎしつつ飲むのは得意ではないな、、

1次会だけで速攻帰ってきた、、まぁいつも通りってところか。。

少人数でまったりと飲むのならよいのだけどなぁ…。

あー、、社会出たら相当困るんだろうなぁとか思うと(略



今日も練習会をやりました。成績微妙だし参加者2名だけだし、

なんか練習会まとめてる意味あるのかなーとか思い始めてきた。

んー、、ちょとテンション低いなぁ今日…。そぉりぃ。

こんな手がw

N個要素をもつ配列aの中身を全部表示しようと思ったら、

普通は

for(int i=0;i<N;i++)cout<<a[i]<<" ";
cout<<endl;

とか書くけど、

copy(a,a+N,ostream_iterator<int>(cout, " "));
cout<<endl;

とも書けるらしいです。

STLが好きになってきた俺としてはちょと嬉しいw

ユークリッドの互除法

ってのは有名なので聞いたことあるはずー、、というか中学とかでやったような(？)

一応書いとくと、「246と138の最大公約数(gcd)は？」って聞かれたときに、

gcd(246,138)=gcd(246%138,138)=gcd(108,138)=gcd(108,138%108)=gcd(108,30) ...

って求めていく方法です。(上の式でa%bはaをbで割ったあまり、って意味です。)



んでー、、今日問題を解いてて、こんな問題を見つけたのです。

icpc関係の方はtryしてみてね(笑)

http://projecteuler.net/index.php?section=problems&id=134


まぁこの問題は、与えられたp1,p2に対して、

(1000*n+p1)%p2=0

みたいな方程式をみたす最小の自然数nを求める問題になるのですが、

この方程式は中学やら高校やらで習った普通の方程式のように簡単には解けないのです。

何故かというと、、方程式の中に％、つまり「割り算のあまり」が入っているから。

まぁ詳しいことを説明すると面倒なので省略しますが、、

こういう式は変形だけで解ける式ではなくて、

nに1を入れて、割り切れたらn=1が答え。

割り切れなかったら、次はnに2を入れて、割り切れたらn=2が答え。

割り切れなかったら、次はnに3をいれて…

みたいな感じで解かないといけないのです。

いや、訂正。

つい2時間前までそうやって解かないといけないと思っていたのです。


でも上に挙げた問題、こうやって解いたらあまりに時間がかかってどうしようもなくて。

何かいい方法ないかなぁとか思って検索して見たのです。グーグル検索。

頑張って調べましたとも。日本語入れたり英語入れたりしてみましたとも。

10個ぐらいキーワード入れたところでさすがグーグル、見つけてくれました。

http://mathworld.wolfram.com/ModularInverse.html


このページの中に「ユークリッドの互除法で解けるよ☆」って書いてあって、

でも「ユークリッドの互除法って最大公約数を求める奴だよなぁ」とか思って、

今度はwikipediaを引いてみました。

http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95


そしたら何か、「拡張された互除法」とか書いてあるじゃないですか。

んー、、何か聞いたことあるような。

実はすっかり忘れてたんですが、、ユークリッドの互除法には拡張版があって、

(といってもほとんど普通の互除法と同じ)それを使えって話だったんです。

んでこんどは「拡張ユークリッドの互除法」で検索して、、

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html

こんなページを見つけて。。どうやら新潟大学のページみたいですw


これを使ったプログラムを書いたら、一番初めに載せた問題も高速に解けました、、

互除法を使う前は5分かかっても解けなかったのが、なんと0.08秒で解けるようになったというw


んー、、拡張ユークリッドの互除法の話をするつもりでブログを書き始めたのに

その前後の話で書きすぎてしまったなぁ。。

気になる方は上の新潟大学のページを読むか、、miracまで聞いてくださいw


ぐだぐだになったので無理やりまとめてみると、、

(1000*n+p1)%p2=0

みたいな方程式はO(log p2)ぐらいで解ける、と。

n=1の場合、とかn=2の場合、とかがりがりやらなくても解ける、と。

しかもそれはユークリッドの互除法をほんの少しいじるだけでできる、と。

んー、、さらにぐだぐだになった感が否めないな。。

まぁまた今度暇だったら書きます☆



前にプログラムの日記書いたときから25問ぐらい解いた形跡があるので、

目標の200問まであと156問!!　国内大会まであと31日!!

Branch and Bound

今日は5月31日。

亡くなったお婆ちゃんの誕生日だったはず。

そして一番歳の近い従兄弟が結婚式を挙げたとか。

まぁ一番歳が近いといっても9歳ぐらい離れていたと思うけどw

お幸せに☆


今日は東大主催のコンテストに参加させてもらってました。

問題(いつまで残ってるのか分からんけど) http://www.utpc.jp/mjudge/problem_list.cgi

結果 http://www.utpc.jp/mjudge/standings.cgi?cid=0

運良く10位には入ったけど、、あと一問いきたかったなぁ…w



久々今日のラーメンズ。

ラーメンズ　ヨンタウロン　春夏秋冬　あいうえお
http://www.youtube.com/watch?v=PtEuGsGznVA

最初の方はちょっと暇かもしれんけど、、

まぁ伏線張りまくって最後に楽しませてくれる感じのですw

サライ

最近いろいろあって書く気があんまりおこらなかったりで放置してました、、すいません；；

まー今日も遅いし1行だけにするつもりのだけど。

好きな曲。
http://www.youtube.com/watch?v=mDc4f8AJXgQ

合唱が入ったところでゾクゾクッときたw

合唱の「浮かぶ景色が」の「ぶ」のハモリが最高に好き…

何回リピートしたことか、、誰かこの気持ち分かってくれるかなぁ笑

最近といた問題

projectEuler 60　　http://projecteuler.net/index.php?section=problems&id=60
実行時間が20秒かかってしまう。
掲示板見てると早くとくのは結構難しいみたい。

projectEuler 80
100以下の自然数の平方根を100桁求める問題。BigIntegerを使った。

その他
projectEuler 35,63,187,115,114,94,108
書くの疲れた笑”

よほどすごい問題以外は書かなくてもいいかなぁなんて思ってみたりw

あ、projectEuler 108 は解けたのですが、それの発展問題である110が全然解けません。

んー、、アルゴリズム悪くて時間が足りないという感じ。さてどうしたものかー。

りんく；http://projecteuler.net/index.php?section=problems&id=108

問題はすごくシンプルなのになかなか解けなくて、いい問題だと思います☆

9問ぐらいといたのであと181問！(多分w

今日といた問題

projectEuler 94
各辺の長さが整数の、”ほぼ正三角形”のうち、面積も整数のものを求める問題。
12秒ぐらいかかるけどまぁ1分以内なのでOKかと。
場合分けとかして無駄な計算減らしたけど、まだまだ減るのだろうな、、
「正解者が見れる掲示板」があるのでそれを見て勉強したいと思いますw
http://projecteuler.net/index.php?section=problems&id=94

projectEuler 108
ちょと説明しにくいから問題は下のURL見てくださいな。
問題も式も簡単だからと思って単純に実行したらなかなか終わらず、、
いろいろ式を変形してたら別の問題に帰着できたのでそれをときました。
やりごたえのある問題を求める人にはいいのではないだろうか？
http://projecteuler.net/index.php?section=problems&id=108

通算10問。あと190問！笑”

今日といた問題

projectEuler 125 ->これはハマってしまったけど良い問題。おすすめ。
http://projecteuler.net/index.php?section=problems&id=125

projectEuler 123 ->BigIntegerの練習が出来たw以降URL略。

projectEuler 116,117 ->spojのpcv3の1問目とその類題。

projectEuler 65 ->分数の分数の分数の…ってのeを求める問題。面白かったw

projectEuler 58 ->飛び飛びの値を素数判定する必要があったので、
そういう場合にはどうしたらいいのかを考える練習になった。
あとdouble使ったら桁落ちして答えが1つ違ったり笑”
http://projecteuler.net/index.php?section=problems&id=58
−>やっぱ勉強になるやつはURL載せることにするw

projectEuler 91 ->51x51の座標の上に直角三角形が何個作れるか、という問題。
簡単な(といっても俺はハマったけど)幾何問題と言うことで勉強になりました。
http://projecteuler.net/index.php?section=problems&id=91

projectEuler 77 ->素数の和5000通り以上で表せる最小の数は？という問題。
例えば整数10なら「2+2+2+2+2」「2+2+3+3」「2+3+5」「3+7」「5+5」の
計5通りで表せるのだけど、じゃぁどれぐらい大きな数なら5000通りで
表せますか？ということ。答えに相当驚きましたw
プログラム的にはよくある手法を使うだけなので暇な人はどうぞw

てかこれだけ大量に書いたけど誰か読むのかな、、自分用ログってことでw

パソコン起動した時刻と見比べたら全部で２００分ぐらい、、１つあたり25分かぁ
ちょっと…というか難易度の割にかなりかかってるなぁ〜(="=;;)

合計：2008/05/18から8問。

よし。

ここに今宣言します。

8月末までに200問のプログラミング問題を解きます！！

いや、、単なる気まぐれなんですがw

単純に計算して…13+30+31+31=104日残ってるので、、

1日2問。学校とかあると相当きつそう。

まぁ目標は達成するためにあると思うし！



今日のラーメンズ：風と桶に関するいくつかの考察
http://www.youtube.com/watch?v=VlsYNvzTh7w&feature=related

ぎりじん

ここには書こう書こうと思いつつ多分初めてなのですが、、

自分はラーメンズという2人組のコント(というのか？)が大好きなのですw

漫才とかとは全然違って、、知的な遊び感がするところがたまらなく好きでw

んでまぁ今回は俺がラーメンズを知るきっかけになったこの曲。

路上のギリジン-Shou+rt Mix-
http://www.youtube.com/watch?v=LYhuBOOBunU

まぁ元ネタはラーメンズの昔の公演なんだそうですが、、

曲とか作ったのが10代の人だとか。

才能って言っちゃえば楽だけど、、人知れず努力して作れるようになったんだろうなw

まぁ努力の程度は人によるわけですが、、本気でやれば出来る気がするのですよw  

恋だなんて

いやー、、突然何をっていう話なんですけどねー笑”

誕生日に「今年こそ平澤がいい女に巡り会いますように」って

メールを送ってきた先輩がいるのだけど笑”

それってどーよっていう笑”

なんか一昨日ぐらいお店のBGMにかかってたLovers popってCDを買って、、

さっきから聞いてたらこんな気分になってきましたとさw

まぁ他にも何かあった気がするけどー、、忘れた忘れた笑”

んー、、とりあえず脇目もふらずに走れるようになりたいなー☆☆

最近

いろいろやることあって時々さっきの日記みたいな状態になってます笑

んー、、どうしたもんだかなぁ。。

とりあえず明日の中間発表を終えたら何とかなると思うので、、

頑張らない程度に頑張ります。

息抜きも大事よね〜w

無題

もー無理ーっ！！  

昨日。

夢を見ました、、あまりの衝撃に目が覚めました、、

その後30分ぐらい寝れませんでした笑”


現実に起こりそうなことが夢になるって聞いたこともあるし、

現実に起こり得ないことが夢になるって聞いたこともあるし、

さてどうしたものだか笑”


普段夢を覚えてないので、たまに見る夢がすごく気になるんだよねぇ…w

続々SPOJ

んー、、あれから全然解けてないですw

他の人が自分よりいい解を出したら自分のポイントが減っちゃうんだよねぇ。。

ということで現在5位。2問ぐらい解けそうなのがあるんだけどなかなかどうして解けない。。

今もパソコン君はフル稼働中、、バックグラウンドで地道に計算してくれてるのだけど、、

それでもなかなかどうして答えが出ない。んー、、どうしたもんだかなぁ・・・

４位きたーーーーーーーっ！！！！

http://s02.megalodon.jp/2008-0511-1609-18/https://www.spoj.pl/ZFUN08/ranks/
ゴールデンウィークからやってたspojのコンテストで、、暫定ながら4位になりましたっ☆

文字認識がなかなか難しいようで、なかなか解いてる人がいなかったのです。

４時間ぐらいがりがりソースを書いて、ちょっと処理をしたら、かなりいい成績が、、

というか今まで文字認識を解いてる人の中で2位になってしまいましたw

もうちょっと頑張ったら１位の人も抜けるかなぁと…頑張ってみますw

続spoj

10位に返り咲きました、、やっほい☆

http://s04.megalodon.jp/2008-0509-2353-35/https://www.spoj.pl/ZFUN08/ranks/
今日解いた問題で面白かったのは、、ぷよぷよみたいに消していく系のゲーム。

適当に書いてsubmitしたらそれなりに点がもらえたから楽だった笑

これ=>https://www.spoj.pl/ZFUN08/problems/JAWB/


圧縮の方は思ってたより難しくてどうしたものか。。

ここにあるzipファイルの中身を圧縮しなさいと−>https://www.spoj.pl/ZFUN08/problems/ARJ/


明日はサークルのプール講習です、、

1回生に教えるのも今年で最後か、、がんばろw