数列の平均とミディアンについて

前回の日記で始める宣言した競プロですが、あまり上達してないけど、AtCoder だけ継続してます。

先日、 AtCoder で次のような出題があり、解けなかった。 C: Linear Approximation - AtCoder Beginner Contest 102 | AtCoder

解説 (Editorial - AtCoder Beginner Contest 102 | AtCoder) を読むと、

b を Bi の中央値にするのが最適であることがわかります

とだけ書いてあり、なんでそうなるのか分からなかった。証明を試みたけど、すぐには思いつかず、あきらめた。ところが数日後、Coursera の画像処理のコースを見ていたら、同じような話が出てきて、驚いた。以下のコースの3週目の6個目の動画あたり。

Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital - Duke University | Coursera

これによって、以下の2つの性質を知ることになった。今まで知らなかったことに驚き。もしくは、学んだけど忘れたのかも。 高校の数学で出てきそうな内容ではあるけど、証明に微分使ったほうが簡単なので出てこないか? 統計力学の授業とかでも習っててもおかしくなさそう。

性質1

数列 {a_i} と数 {b} に対して、

{ \sum (a_i - b)^{2} }

を最小にする {b}{a_i} の平均値となる。

これは{\sum (a_i - b)^{2}}{b}微分して0になるという条件から出てくる。

性質2

数列 {a_i} と数 {b} に対して、

{
\sum |a_i - b|
}

を最小にする {b}{a_i} のミディアンとなる。

こちらは絶対値が入っていて微分可能でない部分があるのではないかとか考えたが、 和を2つに分けてしまって微分してしまえば良いっぽい。

{a_i} は小さい順にソートされているとしても一般性を失わないので、{i=1...m} のとき {a_i \lt b}{i=m+1...N} のとき {a_i \geq b} とすると、

{
\sum _{i = 1}^{N} |a_i - b| = -\sum _{i = 1}^{m} (a_i - b) + \sum _{i = m+1}^{N} (a_i - b).
}

これを {b}微分して 0 になるという条件から、

{
m - (N -m) = 0 \Rightarrow m = \frac{N}{2}.
}

{m}{N} の半分の位置にあるということは、つまり {b}{a_i} のミディアン。

以上、雑な証明だと思うけど、納得した。物理学科卒なので細かいことは気にしない。こういう証明モドキですらやってみるのは何年ぶりか。。

参考文献

ミディアンの方は自力では最後まで行けなかったので、適当にググって以下を見つけた。

Jupyter で書いてからブログに転載したけどはてなTeX の書き方がめんどうなのでもうやらない。 http://nbviewer.jupyter.org/github/pn11/benkyokai/blob/master/statistics/mean_and_median.ipynb

競プロはじめました

これまで CodeIQ (最近終了したことを知った) とか Paiza のスキルチェックとかはたまにやってたけど、昨日初めてリアルタイムのコンテストに参加してみた。AtCoderで参加したけど、昨日は bitFlyer が主催する特別なイベントだったみたいで、レギュラーなやつを経験しないままそれに参加することになってしまった。

コンテストはこちら。

bitflyer2018-qual.contest.atcoder.jp

問題 → https://bitflyer2018-qual.contest.atcoder.jp/assignments
解説 → https://bitflyer2018-qual.contest.atcoder.jp/editorial

Python でやってみて、5問中2問正解して1300人くらい中925位だった。

Aについては一応正解だったけど解説をみるともっと簡単に書けたっぽい。Bはそのまま書くだけなので解説と似たような感じになった。Cについては手元では正解できるコードを書いたけど、時間オーバーだった。三重ループになってしまったので筋は悪いだろうなと思ってはいたけど、解説を見てなるほどとなった。4問目は NumPy を使って書いたけど、そもそも与えられたテストケースでもメモリオーバーになる(1000000000 x 1000000000 の場合)。数を数えるだけなので、全部の画素の情報は取っておく必要はないとは思ったけど、ギブアップ。解説に累積和というのを使うと書いてあったので、勉強しよう。Eは問題文は読んだけど、疲れたし頭痛かったのでギブアップ。

今日もあるっぽいので挑戦してみよう。リアルタイムだと集中して取り組めるし、頑張るとちゃんと解説読む気になるので良い。

以下、提出したコード。

AtCoder 2018/06/02

PDFtkでPDFを分割しためも

PDFから特定のページを抜き出したりとかは、Mac だったらプレビューでやるんだけど Windows だと手軽にできそうな GUI アプリがなさそうなので PDFtk でやってみた。

PDFtk はこちらからダウンロード。

www.pdflabs.com

GUIツールもインストールされるようだが、こちらは無料ではほとんど何もできなそうなので、当然コマンドラインを使う。インストールした時点でPATHが通っているので、PowerShellなどで pdftk -h とすると使い方がでてくる。その中で、

Remove page 13 from in1.pdf to create out1.pdf
         pdftk in.pdf cat 1-12 14-end output out1.pdf
         or:
         pdftk A=in1.pdf cat A1-12 A14-end output out1.pdf

という箇所があり、だいたいこのようにすれば分割できる。今やりたいのは Kindle にメールで送るには大きすぎるPDFファイルを分割して送るということなので、例えば100ページごとにしたかったら、

pdftk test.pdf cat 1-100 output out.pdf

とすればできた。PDFが100ページない場合はエラーになるので、1-end とする。

あと縦書きの PDF を Kindle で開くときにめくる方向が逆になるという問題に対して、逆順の PDF をつくるというハックがあるが、これは以下のようにしてできる。

pdftk test.pdf cat end-1 output reverse.pdf

コマンドが直感的なのが良い。自分がもし作る側だったら、無駄に combine, split, remove, reverse とかのコマンドを実装してしまいそうだけど、それらは上に書いたように全て cat でできる。なるべく少ないコマンドで色々なことをできるようにしている感じで、見習いたい。

PDFtk について調べてたら、CPDFというのもあるらしい。

CPDF:メッチャ多機能なPDFのコマンドライン・ツール | PDF

これも非商用なら無料で使える。そのうち試したい。

追記 (2018/03/18)

PDFをトリミングしたくなって、PDFtk ではできなそうだったので、早速 CPDF を使ってみた。

community.coherentpdf.com

バイナリを落としてくれば使える。手持ちの自炊文庫本PDFでは、

.\cpdf.exe -crop "5mm 10mm 90mm 130mm" in.pdf -o out.pdf

とすると良い感じに余白がなくなった。

Macから決まった時間にLINEに通知を送る

1年ぶりくらいにやろうとしたらハマってしまったのでめも。ほぼ at コマンドのせい。

LINE Notify の設定

これについては LINE の中の人がとても分かりやすくかいて下さっているので簡単。以前つくったアクセスキーは再表示できないので忘れてたら新しく作る。

developers.linecorp.com

at コマンドの使い方

上記のリンク先にある curl コマンドを、 at コマンドで決まった時間に実行したい。まず、 at コマンドでジョブを登録しても Mac ではデフォルトではジョブが実行されない *1 ので、有効化する。以下のリンク先を参照。

blog.hello-world.jp.net

リンク先にあるように、有効化するコマンドは以下。

sudo launchctl unload -F /System/Library/LaunchDaemons/com.apple.atrun.plist
sudo launchctl load -F /System/Library/LaunchDaemons/com.apple.atrun.plist

既に過ぎた時間にジョブが登録されていた場合、上記のコマンドを実行した途端に一気にジョブが流れるようで、LINEに通知が鬼のように来た。

もう一つのハマりポイントは at コマンドの難しさ。定期的に行うジョブは cron に登録したり、何分後に実行とかの場合は sleep を使ったりすることも多く、 at はあまり使う機会がないためかいつまで経っても慣れない。とりあえず私の環境では以下のような感じなら動いた。

at -m -f notify_me.sh "0:00 022318"

notify_me.sh に LINE に通知するコマンドが書いてある。 -m オプションは結果をメールするためのもの。時刻の指定が難しく、間違うと「garbled time」とかって怒られる。ネット上の情報だと時刻の文字列はどこに書いても動くようだったが、 Mac だと一番最後に書かないと動かない? つまり、

at "0:00 022318" -m -f notify_me.sh 

ではダメだった。

*1:FreeBSDの仕様?

Windows で Hyper-V が有効だと VirtualBox が動かない

タイトル通りだけど、経緯は以下のような感じ。

症状:Windows 10 Pro 64 bitで Virtual box で Ubuntu 16.04 LTS の VM (64 bit) を作ろうとしたところ、作れなかった。

did2memo.net

ここに書いてあるような感じ。この方のブログはよく参考にさせていただいているので、今回もこの通りにやってみたけど、だめだった。

その後以下を見つけた。

picworld.jp

Docker for Windows を入れたときに、 Hyper-V を有効にしたのを忘れてた。ということは、Docker と VirtualBox は同時に使えないんだな。VirtualBox にはそのくらいはチェックして教えて欲しい。32 bit なら作れそうに見えるのもよろしくない(選択したところで結局は作れない)。

あと、以下に載っている CPU-Z とか、Virtual Checker とか覚えておくと便利そうだなと思った。

ja.stackoverflow.com

社会人1年目の今年買ったもの

という名のアフィ記事。

電子機器編

よく使ってる順?

GARMIN vivosport

前からGPSと心拍付き腕時計がほしかったけど、京都マラソンに当選したタイミングでこれが発売してくれたので即買いした。小さいので腕時計と両方つけて会社に行っている。GARMIN コネクトの Android App が使いにくい以外は特に不満はない。特に必要ないけど、スマホの通知を送るのがやろうとしてもできない。そもそも対応してないのかな? → できました。でも割りと頻繁に調子悪くなる。
もともとは GPS は付いていないものの、会社につけていっても違和感なさそうな NOKIA Steel HR を買おうと思ってたんだけど、Withings から Nokia になって HR (心拍付き) だけなかなか発売されなかったので、これになった。結果的にはこっちを買って良かった。

HUAWEI Mate9

三木谷割で購入。これまで型落ちスマホばかり使っていたので、初めてスマホを手にした2011年以来、6年ぶりにハイエンド級の端末になった。 Nexus 5 からの乗り換えだったので、Pure android が恋しい。EMUI は電池の持ちとかが良いっぽいけど自由度が少ない。せっかく良い端末を買ったのに細かいところでストレスを感じる日々。
2018/02/07追記: 最近 Android 8.0, EMUI 8.0 へのアップデートが来たけど、バックグラウンドタスクを邪魔するおせっかいがさらに進んでいる気がする。

なおカバーについてはこれが安かったのに高級感があるし良かった。

確認しないで買ってしまったけど、ちゃんと後ろ側の指紋センサーの部分も穴が空いてる。これで定期を家に忘れることが少なくなった。(先日携帯ごと忘れたけど)

HHKB Professional 2 無刻印 US配列

入社してすぐ買って会社で毎日使ってる。Apple Magic Keyboard 2を持っていこうと思ってたけどセキュリティ的に有線のほうが好ましいっぽかったので見栄で無刻印買ってみた (Magic Keyboard 2 は有線接続もできるけど)。3万円の価値があるのか今でも分からないが、たしかに他のキーボードよりは気持ちいいし、長持ちしてくれるならそんなに高い買い物でもないのかも。プログラマは道具にこだわる人が多いのかと思ったけど、うちの会社にはほとんどそういう人はいなかった。むしろそういう人は研究者のほうが多い感じ。

Nintendo Switch

発表されたときは特に興味なかったんだけど、発売されてゼルダの評判が良いので欲しくなってしまった。 10月11月はかなりの時間をハイラルで過ごした。最近DLC第二弾が配信されたけどあんまりやってない。

HUAWEI MateBook

買ったのは一応今年だけど社会人になる前の1月ごろ。夏に液晶が壊れてファーウェイに送ったらすぐに新品が送られてきた。それ以降は大丈夫そう。ペンで入力するデバイスが欲しくて、Windows なら iOSAndroid よりも便利かなとか会社でも Windows だしとか思って買ったけど、Windows なので結局使いにくかった。たまに Mac 使うと使いやすさに感動する。 基本的にハードよりもOSについての不満しかないけど、ハードに関して言えばキーボードカバーが日本だと JIS しか売ってないっぽいのが辛い。

Macbook Air バッテリー

2012年に買った Macbook Air、バッテリーが死んでいたので据え置きにしてたけど、モバイル用に使ってた Macbook (12インチの初代) を手放したのでバッテリーを換装して復帰してもらった。カバーのネジを外すのが難しくて一本なめてしまって苦労した(けっきょくヤスリで溝を掘った)。バッテリー交換にも最初失敗したみたいで、返品しようかと思ったけど、ケーブルの配線をちゃんとしたらようやくできた。バッテリー持ちが良くなったは良いものの、もう持ち歩くことはないかと思ってステッカーめちゃくちゃ貼ってるので、持ち出すのが少しはずかしい。 あと、これ買った当時はJISキーボード派だったのでMBAの配列もJISだけど設定はUSになってる。結果、印字と入力が一致せず気持ち悪いので、以下のシールを買ってみたけど貼らずに半年くらい放置してる。

ブラックアウトステッカー for Mac 15mm(MBA/MBP~2015 JIS用)

ブラックアウトステッカー for Mac 15mm(MBA/MBP~2015 JIS用)

Google Home mini

「ご存知 AmazonGoogle の喧嘩によりアフィリンクなし」

前の記事に書いたようにサイバーマンデーで買ったけども、正直あまり使ってない。毎朝天気を尋ねるのもすぐ飽きる。IFTTT をまだ設定してないのでやらねば。mini は音質が微妙というネットの記事を読んだけど、耳が肥えていないので気にならなかった。

家電編

思いついた順。電子機器は海外メーカーのばかり買ってるけど、家電については意外と日本企業のを買ってた。

Kyocera 電池式コーヒーミル

家の近所の会社が作ってる電動ミル。電池式のコーヒーミルは軽く探した感じこれしか売ってない。一回に一人分しか挽けないし、挽くのに5分くらいかかるけど、手で挽くよりは圧倒的に楽。電動ミルはコンセント式面倒なのでこれにしたけど、コンパクトだし、普通の電動ミルより静か。

SHARP ヘルシオ オーブンレンジ

今までクソ安いダイアル式の電子レンジを10年近く使ってきたけど、引っ越しを機に捨てた。無料って言いながら最後に1000円請求してきた廃品回収業者のことは忘れない(退去日近くて面倒なので払ってしまった)。 初めてのオーブンレンジ。ヘルシオ自慢の唐揚げとかもつくれるけど面倒なので一回しかやってない。パンとかピザとかもたまに焼くけどやはり面倒。 ちゃんとしたレンジを買うと掃除が楽だし、開いたときにドアに物置けるしすごいなと思った。

DAIKIN 空気清浄機

こういう場所とる系のものはなるべく部屋にマッチするデザインじゃないときついけど、これが一番マシなデザインだったので。一人暮らしだしもっと小さいのを買おうかと最初は思ったけど、ネットの記事で小さいのも大きいのもそんなに存在感変わらないというのを見て、普通サイズにした。とりあえずつけっぱなしにしているけど効果があるのかは良くわからない。なんか定量的な議論をしたい。

Panasonic セラミックファンヒーター

本当は人感センサーとかも要らないくらいだけど、そこそこシンプルでデザインも良く、コンパクトで使いやすい。一人暮らしの部屋ならこれで十分。リビングから脱衣場に持っていったりするけど軽いので楽ちん。

あと買ったのは卓上掃除機やらモニターアームやらモニター台やら。

ところで以下のような記事を読んだ。

gizmodo.com

Sphero R2-D2 (と BB-8)も買って実家で眠っているので、Swtich と合わせて2つも買っていた。

Sphero スター・ウォーズ R2-D2 APP-ENABLED DROID 【日本正規代理店品】 R201JPN

Sphero スター・ウォーズ R2-D2 APP-ENABLED DROID 【日本正規代理店品】 R201JPN

あとこんな記事も読んだ。

www.engadget.com

音彦って初めて聞いた。日本ではラーメンを音を立ててすすることがラーメン屋への敬意を表すらしい。

Google Home mini を買った

サイバーマンデーGoogle Home が半額になっていたので、 mini の方を買った。サイバーマンデーといいつつビックカメラでは実店舗でも半額になっていた。スマホGoogle Assistant と機能的にはあまり変わらないけど、常に待ち受けてくれるので料理中とか皿洗い中とかには便利。朝起きて「今日はどんな日?」と聴くとと起きやすいかも(そうでもない)。IFTTT が使えるので試してみたい。どんな機能を使っているかそのうち書こうと思う。でもその前に以下の記事のことを思い出した。

この記事は「今さら IFTTT が便利だと分かった」というタイトルでドラフトに入っていて、タイムスタンプは 2/20/2017, 5:42:52 PM となっていた (JST)。なぜ公開してなかったのかよくわからないけど、9ヶ月遅れで公開する。今はもう使っていないのもあるし、情報が古い可能性もある。

使ってるレシピ

Twitter to Evernote

自分のツイートを Evernote に保存 ifttt.com

ファボったツイートを保存 ifttt.com

あと、特定のエリアに入ったときと出たときにツイートするようにしている。「出社なう」とか「退社なう」みたいな感じ。

Todoist to Evernote

完了したタスクを Evernote に記録。やったことを可視化できてやる気になりそう。

ifttt.com

ついでに Google Spreadsheet にも送ってる。

ifttt.com

Evernote to Todoist

特定のタグをつけたノートへのリンクを Todoist に送る。以下の二つを試してみたけど、どちらもマルチバイト文字が文字化けしてしまう。

ifttt.com

ifttt.com

解決するには、ノートのタイトルを英語にするか、Todoist 上でタスク名を変えるか、かな。あるいはこちらの方のようにする。

rankonikki.giren.net

その他

明日が雨だと通知

ifttt.com

宇宙飛行士が宇宙に行くと通知 ifttt.com

もっと自由度が欲しい

IFTTT は組み合わせ次第で色々できて楽しいんだけど、限界もある。例えば1時間ごとに位置情報を取得して Evernote に送るみたいなことをしたかったんだけど、それをするには「時間」+「位置」+「Evernote」の3つが必要で、IFTTT では2つをつなぐことしか出来ないので無理。つまり If This and This Then That とかはできない。 「位置」についても、座標とかは取ってこれなくて、あるエリアにいるかどうかしか分からない。位置情報を使うアプレットはこれ。

ifttt.com

あと Twitter とかのアカウントを複数登録できるようにくらいはして欲しいな。