晴。
昨晩は明け方まで AOJ をやっていた。そんなになるとは思っていなかったのだが、この問題を Ruby で解いていて詰まってしまったのである。グラフの単一始点最短経路問題なので、まずはふつうに幅優先探索で実装したのだが、なんとメモリオーバーになってしまった。何か爆発的に経路が多いらしい。なので、確信はなかったけれど、ダイクストラ法に切り替えて実装する。それに手間どって時間を喰った。けれども、今度はタイムオーバーなのである。ちょっと Ruby では無理なのかも知れないが、まだダイクストラ法で優先度付きキュー(二分ヒープ)を使って実装するという方法などが残っている。しかしこれはやったことがないので、簡単に実装というわけにはいかない。まあできるとは思うが、疲れたのでさすがにそこで寝ました。だんだんむずかしくなってきて、少しずつしか進まない。これなどはどうやってもタイムオーバーで、Ruby で解けた人は誰もいないという有り様である。コードは正しいと思うのだが。これでも苦労したのだけれどなあ。
ダイクストラ法はノードの確定のさせ方がいろいろあるので、自分のやり方はまだ必ずしも効率的でない(毎回全ノードから探索している)。もっとも効率的な確定のさせ方はどうしたらよいか考える余地が(だいぶ)ある。
#
一時、雪。
NML で音楽を聴く。■ショパンのポロネーズ第五番 op.44 で、ピアノはラザール・ベルマン(NML、MP3)。
■モーツァルトのピアノ協奏曲第二十三番 K.488 で、ピアノは田部京子、指揮は小林研一郎、日本フィルハーモニー交響楽団(NML)。コバケンはふつうによい。田部京子さんはよくわからないのだが、自分のもっていない感受性をもっている可能性大。田部さんの CD はたくさん出ているな。
モーツァルト:ピアノ・ソナタ 第11番、ピアノ協奏曲 第23番
- アーティスト: 田部京子(Pf),モーツァルト
- 出版社/メーカー: オクタヴィア・レコード
- 発売日: 2016/11/18
- メディア: CD
- この商品を含むブログを見る
#
夕食後、アランを読みつつ寝てしまう。深夜起床。またアランを読む。