この記事の目的ダイクストラ法の計算量は、O(ElogV)である。 仮に、エッジの長さが0か1ならばO(E)、つまりエッジの数に比例することになる。 「どうしてそうなるのか全く理解出来ない」と誰でも思うだろう。 優先度キューを使ってBFSで探索していけば、毎回エッジの分だけ分岐があるんだから なんらかの計算量はその分岐がどんどん積み重なっていき、 指数オーダーになってしかるべきだろう。 ふつうの人はそう考える。 どういうメカニズムで探索が省略されているのかなんとなく木を書き出して考えてみても、 なんとなくわかった気になったあとでやっぱりわからんとなる。 それが、ダイクストラ法を題材にしたちょっとした応用問題が出た時に手も足も出なくなる原因である。 グラフがぽいっと渡されて、はいs-t最短距離を計算してくださいと言われたら、 準備していたライブラリに食わせて終わりだが、 よく考えるとグラフ探索

etiles(イータイルズ)というのは、おれが作ってるパズルゲームで、自札のNxNタイルを裏返したり入れ替えたりして、答えにマッチさせるというゲームです。今はTypeScriptとReact-Nativeで書かれています。 インストールお願いします。 https://play.google.com/store/apps/details?id=jp.gr.java_conf.etiles.android 今回は、このアプリをTypeScriptで書き直した話をします。 etiles akira$ tokei src/ -------------------------------------------------------------------------------- Language Files Lines Code Comments Blanks ----------------

Posted on April 25, 2019 |  7 minutes |  Akira Hayakawa URLをすべてカスタムURLに変更しましたこのブログを始めた時、私はアドセンスのことも知りませんでしたし、ブログに広告をつけて収益を得るということなど考えたこともなかったです。それどころか、検索で上位に出そうという考えもなかったです。 しかし偶然にもいくつかの記事はヒットして、それなりに見られるようになりました。特に、日立製作所を退職した時の記事などは、誰かが大企業を辞める度にまた見られるを繰り返す、ロングセラーになっています。どう間違ったか、「拝承します」で検索をかけてくる人もいます。 退職します。拝承 - テストステ論 PVをさらに稼ぐためには、記事が検索の上位に入ることと、それがクリックされる率（CTR）を上げることが必要になります。それがいわゆるSEO対策ですが、今までブ

おれは最近、自分のエディタを開発している。 GitHub - akiradeveloper/ijk: A real editor for real programmers イージックと読む。名前の由来は、easy codingとか、プログラミングで典型的な三重ループのインデックス名だったりとか、こじつけはいくらでもある。しかし実際には、押しやすいことが一番だと思った。ijkは右手の2本だけで瞬時に押せる。viは左右を使わないといけない。emacsとかはeというエイリアスをつけてる人がいるが、これは反則だろう。 なぜ開発を始めたのか。Rustを学習するにあたって、適度な演習問題がほしかったからに他ならないが、今はこれが生き甲斐というかおれの人生そのものだと思うようになっている。おれはエディタに魅惑された。 他にもやらないことは山程あったように思うのだが、朝から晩までずっとエディタのことばかり

私は、このブログやもう1つのブログであるRustコトハジメで記事を書いていくにあたって、Asanaというタスク管理サービスを使っています。これを使ってネタ集めをすると大変便利なので、みなさんに共有します。 Asanaとはウェブブラウザ・スマホから使うことが出来るタスク管理サービスです。以前の職場の同僚が使っていて、やたら推して来るので使い始めたわけですが、今では重宝しています。 https://app.asana.com/ 活用方法記事を書く時に私は、 書きたいことを決める。これはほぼタイトルになるその記事を書くに当たってネタを集める。例えばドキュメントを読んで、引用出来そうなところを集めるという段階を踏みます。 Asanaを使う場合、書きたいことをタスクのタイトルにします。これは思いついた時に、ためらいなく入れてしまいます。その結果、ボツになったり、他の記事にマージされたりすることもある

ダリフラというアニメがちょっと前にTLで賑わってたけど、おれは見たことがない。ただ、歌は聴いた。トリカゴという歌で、女子高生が「学校や社会に縛られたくない。私にはやりたいことがある」と叫んでるような歌だ。歌自体はとても良い歌だと思うのだが、一方で、一般の女子高生になんか「やりたいこと」があるんだろうかと疑問に思ってしまう。 「やりたいこと」というのは、お腹が空いたからご飯を食べたいとか、ましてはヤリたいことではないと信じたい。勉強から逃げたいだなんていうのは論外。それは例えば、汚染された海をきれいにしたいとか、世界中で苦しむ膵臓癌患者を救いたいとか、人生を賭けて取り組む覚悟の出来たテーマであるべきであって、たかだか女子高生程度に見つかってるとはとても思えない。本当にやりたいと思えるようになるためには強い思いを生み出す経験も必要だし、先天的な才能も必要だと思う。日本でいうとAtCoderの社

今日は久しぶりに朝8時に起きることが出来た。これが朝か。少し肌寒く、太陽が眩しい。「新しい朝が来た。希望の朝だ」で始まるラジオ体操の歌があるが、清々しい気分でラジオ体操でもしたくなる。 今日は11時から役所に行き、マイカードの受取と保険の切り替えをする必要がある。色々やるべきこと・やりたいことがある。自分だけの人生がようやく始まったという感じでやる気がわいてくる。どうやら鬱は一晩で治ってしまったらしい。 あの伝説の退職エントリから5年の間にまさか累計4本目の退職エントリを書くことになるとは思わなかった。退職エントリを何度も書いていくうちに、退職した会社がとりわけベンチャーのように小さな会社の場合、名前を出して検索エンジンに引っかかることは迷惑になってしまうことに気づいたため、今回は名前を出さないことにする。報復が目的ではないからだ。しかし名前がないのは不便だから便宜上A社とする。 A社に入