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

続きを読む

TCO18 Algorithm Round 2A

6/3 1:00am JST
起きていられたので出た。

oxx 231.65pt 271st (Room27:12位)
1497→1517 (+20)
f:id:n4_t:20180604005202p:plain:w400
レート反映めちゃ遅かった(11:30am過ぎに確認できた)けど上がったし黄色に復帰したので良しとする

200位までに入れば通過(&Tシャツ?)だったらしい。
(50人ぐらいだと思ってた)

続きを読む

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

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

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

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

続きを読む

〈ARC埋め〉ARC 098 E - Range Minimum Queries

先日のARC098のE問題が通せてなかったので再挑戦。

  1. 最小を決める
  2. それ未満のものを捨てる(というかそれ未満のものが壁になっていくつかの区間に分かれる)
  3. 分かれたいくつかの区間からそれぞれ貪欲に拾う

というところまでは良かったのだけれど

11 3 5
2 2 2 2 2 1 3 3 3 3 3

のような入力で0を返すやつをずっと書いてておかしいなあと悩んでいた。(←例えば最小を2としたとき、1が壁になって [2 2 2 2 2], [3 3 3 3 3] になって、それぞれ幅3以上だから拾うことができて、小さい順に5個拾うと {2,2,2,2,2} だからmax()-min()=2-2=0、みたいな)

勿論それは間違いで。

続きを読む