buq’s blog

覚えておきたいけど覚えておけなさそうなことを書きます?

2015-01-01から1年間の記事一覧

k番目要素

数列が与えられ,k番目の要素を求めるという問題がある. 解き方としてクイックソートに類似したものがあり,計算時間の期待値は O(n) である. 参考:Spaghetti Source - k 番目の要素の選択 この問題をとく乱択でないアルゴリズムをしった(上記サイトにも…

ipython notebook のファイルをダブルクリックで開く:訂正記事

ipython notebook のファイルをダブルクリックで開く方法について以前かいた記事のコードが大幅に間違っていたので訂正します.当該ページは訂正済み. 以前下記の記事を書きました: ipython notebook のファイルをダブルクリックで開く @ OS X - buq’s blo…

整数の除算 @ C++

C++

a/b とか a%b の挙動についてメモ. a, b の一方が負である場合は処理系依存(C/C++のバージョンにもよる?)で, 多くの処理系で「実数の割り算の値a/bを0方向に丸める」ということらしい. ただし (a/b)*b + a%b == a は成り立つようになっている. 先日書…

関数オブジェクト @ C++

C++

C++には関数オブジェクトというものがある. class に operator()を適当に定義してやれば作ることができ, これを用いるとパラメタつき関数みたいなものが実現できる. ここではパラメタつき比較関数(二つの引数をとって,前者が後者より厳密に小さいときtr…

ipython notebook のファイルをダブルクリックで開く @ OS X

ipython notebook の .ipynb ファイルをダブルクリックで開きたい人がいます(私です). 他のひともそういうことを考えているみたいです osx mountain lion - Open an ipython notebook via double-click on osx - Stack Overflow 上記のリンクでは Ubuntu …

有限生成錐 ↔ 多面体的錐の証明

有限生成錐は多面体的錐であり,逆も成り立つ,という定理がある.(p.77, 線形代数II 室田+杉原, 丸善出版) 基礎系 数学 線形代数II (東京大学工学教程)作者: 室田一雄,杉原正顯,東京大学工学教程編纂委員会出版社/メーカー: 丸善出版発売日: 2013/10/09メ…

最小費用ソート(ALDS1_6_D)の解法の正当性(メモ)

Minimum Cost Sort (最小費用ソート)という問題がある. 最小コストソート | アルゴリズムとデータ構造 | Aizu Online Judge この問題を解くことができず,また正解コードをみてもその正当性がよくわからなかった. まじめに考えたら正当性の証明ができつ…

San Francisco 日記

実は現地時間の23日から San Francisco に来ている. 忘備録を兼ねていろいろメモしておく. 23日 到着して宿に行くだけでせいいっぱいだった. 初めて Airbnb を使ったり Über を使ったり,そもそもはじめてのUSだったり,わたわたしていたら宿にいたという…

TOEIC 965

受けるとか受けたとかいっていた TOEIC だが,結果が帰ってきた. 思っていた水準+α の得点で満足しています. TOEIC 本番 3/15 - buq’s blogbuq.hateblo.jp TOEIC模試 - buq’s blogbuq.hateblo.jp ある程度の実力があれば,最後に効いてくるのは語彙だと思…

強相補性→双対定理の証明

手元にある最適化の教科書で線形計画法の再勉強をしているのだが,いまいち 書いてある証明が読めない部分があったので自分で証明しなおした.最適化法 (工系数学講座 17)作者: 田村明久,村松正和出版社/メーカー: 共立出版発売日: 2002/04/01メディア: 単行…

UNIX システムでの git レポジトリの置き場所

ipython notebook が大好きで,それが高じて Jupyter で R を使いたくなってきた. git のレポジトリを手元に引っ張ってきてインストールするのだが,そもそも git のレポジトリってどこにおけばいいんだろうか? こういうのは FHS に従って考えればいいらし…

TOEIC 本番 3/15

TOEIC を受けてきた. 今回が初めての受験だったけれど模試パックを3回分やっていたのでそんなに大きなミスは犯さずに済んだと思う. しかしながらやはり本番は自室や喫茶店で模試をやるのとは違うもので,いろいろな発見があった. また,今回けっこう本気…

TOEIC模試

週末は線形計画法の復習で溶かそうと思っていたが,あんまり頭がまわらない感じなのでZ会のTOEICの模試をやってみた. 弱点がわかるTOEIC TEST模試600問作者: Z会編集部出版社/メーカー: Z会発売日: 2010/03メディア: 単行本この商品を含むブログを見る

計算量理論独習用教材

東大の河村先生が計算量理論の独習用問題集を公開されている. Enshu (Computational Complexity)

マインスイーパーは解けるのか GCJ 2008 final C

プログラミングコンテストチャレンジブックプログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: マイナビ発売日: 2012/01/28メディア: 単…