naoya_t@hatenablog

いわゆるチラシノウラであります

DFT(離散フーリエ変換)とNTT(数論変換:整数(剰余環)を用いたDFT)

先日ARC埋めの一環でATC001のC問題(高速フーリエ変換)を解いたのだけれど、こういう畳み込み問題はDFT(discrete Fourier transform;離散フーリエ変換)の代わりに NTT(number-theoretical transform;数論変換)という "整数(剰余環)を用いたDFT" でも解けるらしい。

そこで、math314氏の「 任意modでの畳み込み演算をO(n log(n))で - math314のブログ」の解説と実装例*1を追いながら自分で実装して試してみた。こないだcomplex<double>で自分で書いてみたやつ(→ATC001)とほぼ同じことをしているように見える。これは面白い。

(ここでは解説はしないので、詳しくはmath314氏の元記事を参照して頂ければと思います)

*1:動かすには何箇所か修正が必要

続きを読む

Kindle Oasis(第9世代)を買った話

我が家にKindle Oasis(第9世代)がやってきました。

TopCoder Algoのレーティングが黄色に復帰した後に届いたので黄色復帰祝っぽくなりましたが、ぽちった時点ではそういうイベントが来るのは予期していませんでした。
f:id:n4_t:20180603140544j:plain:w400
f:id:n4_t:20180603140827j:plain:w400
f:id:n4_t:20180603140932j:plain:w400

続きを読む

例題で学ぶ微分方程式:1.1 常微分方程式と相図

なんとなく「時代は微分方程式だよなあ」と思って先日オライリーの「例題で学ぶ微分方程式」を買いました。
www.oreilly.co.jp

本書ではMathematicaでプログラムが書かれているので、これをPythonでというかJupyter notebook (scipy+matplotlib) で置き換えながら読み進めようと思います。

というか、jupyter notebookをgist経由でブログに埋め込むテストです。

続きを読む

6log6≠6log6

先日のこどふぉ#484のB問題(agwたんから聞いた)
B. High School: Become Human

xとy(それぞれ1以上10^9以下の整数)が与えられてx^yy^xの大小を比べるだけの問題。

y\log xx\log y の比較に置き換えれば簡単なはずなんだけど、ローカルでは何の問題もないのにサーバ上ではあたかも6log6≠6log6であるかのような振舞いをする。
これは(数学の問題と見せかけて)コンパイラの最適化の地雷をどう避けるかという問題。

// サーバ上だとx=y=6でなぜか落ちる
#include <bits/stdc++.h>
using namespace std;
int main() {
  int x,y; cin>>x>>y;
  double lx=log(x)*y, ly=log(y)*x;
  if (lx == ly) cout << "=" << endl;
  else if (lx < ly) cout << "<" << endl;
  else if (lx > ly) cout << ">" << endl;
  return 0;
}
続きを読む

Coursera: Robotics: 1. Aerial Robotics〈修了〉

全6部から成るCourseraのRobotics特別講座

  • Aerial Robotics
  • Computational Motion Planning
  • Mobility
  • Perception
  • Estimation and Learning
  • Capstone

の第1講 Aerial Robotics(4週間コース)を受講しました。ドローンに関する講座です。
f:id:n4_t:20180508220849j:plain

ドローンは安全性の問題や法整備など課題は多いし実社会での応用はまだまだこれからなのかなと思いますが、物流・農業・建築・災害救助をはじめ様々な分野での活用が期待されています。未来を感じます。

この講座では、クワッドローター(推進に4つの回転翼を用いるドローン)の飛行を制御するのに必要な物理学(力学)が学べます。最終週の課題では、空中の与えられた経由点のリストから飛行コースを計画し、計画した軌道に沿った飛行に必要な推力やモーメントの計算を行うプログラムを実装します。*1
f:id:n4_t:20180508133512g:plain

プログラミング実習ではMATLAB*2を使います。Webで使えるアカウントが1ヶ月無料でもらえる*3のでそれを使います。

講義は全編英語で行われています。(英語字幕可、日本語字幕はいまのところ無し)
先生の英語は若干訛りがあるけれどゆっくり目に話してくれているように思いますし、比較的聞きやすい英語だと思います。
TAの女性が担当している補足資料のビデオは綺麗な英語で聞きやすいですけれど割と早口です。

剛体力学(剛体の回転とかモーメントとか角運動量とか慣性テンソルとか)が分からない、あるいは苦手な人は先にさらっておくか、力学の教科書を手元に置いての受講をおすすめします。*4

*1:下のGIFアニメーションは最終週の課題で実装したプログラムに適当なコース(通過したい空中の点のリスト)を与えてみたシミュレーション結果です((GIFアニメを吐き出すようにシミュレータを若干改造しました。

*2:以前Andrew Ng先生の機械学習の講義Octaveを触ったことがあるのでなんとなくそんな感じかなと思って臨みました。でも課題であらかじめ与えられるプログラムファイルは手元のOctaveで動かせるかと思ったら動きませんでした。

*3:期限に間に合わなくて次月に繰越になってもまたもらえます

*4:物理学・力学については高校物理レベル+α の知識、具体的にはセンター試験の物理は満点取ったけど大学では力学とか電磁気学の授業をちょっと覗いただけで単位は取ってないはず…ぐらいの知識で講義に臨んでの感想です。

続きを読む

DL4US (Deep Learning for all of us) 修了

東大松尾研監修のディープラーニングのオンライン講座 DL4US を受講し、無事修了しました。
f:id:n4_t:20180424113723p:plain
内容の大部分は書籍やCourseraの講義、普段の業務などで既知のものでしたが、知識を更新しながらコードに落として確認していく作業は有益でした*1。最後の辺り、GANやVAE、深層強化学習の辺りは概念的には知っていましたが実際にコードを書いてみるのは初めてで楽しかったです。最終レポートの提出期限は2回延長されたのですがその締切時刻に間に合わず日が変わってからの投稿になってしまいましたがacceptして頂けました。(ありがとうございます)

*1:この分野は進化がとても速いので定期的に知識をアップデートしていく必要がありますね。

続きを読む