はてなブックマーク

2. ウェーブレット行列 ウェーブレット行列とは、長さ $n$ の 1次元の $b$ bit 整数配列に対して、$O(nb)$ の時間の前処理を行うことで以下のような区間クエリを求められるデータ構造です。 Quantile(L, R, k) : 配列の区間 $[L, R)$ の中で、$k$ 番目に小さい値を答える RangeFreq(L, R, x, y) : 配列の区間 $[L, R)$ の中で、値域が $[x, y)$ の要素数を答える 単純に考えると、どちらの操作も計算量は $O(R-L)$ になりそうですが、ウェーブレット行列はこれらのクエリを、区間の長さや中身、答えにかかわらず $O(b)$ の時間で答えることができます。 更に、メモリ使用量に関しても十分省メモリに実装することができ、真面目に実装すると $nb + o(nb)$ [bit] のスペース、つまりもともとの数列を表す

こんにちは、TumoiYorozuです。 現在は東京大学の博士 1 年生をしています。私は中学 1 年の頃からプログラミングをやっていて、特にアルゴリズムが大好きです。AtCoder をはじめとする 競技プログラミング にも取り組んでいて、高校生のときは情報オリンピックにも参加し、大学生のときは ICPC 国際大学対抗プログラミングコンテストに参加していました。現在はこれらの裏方をしています。 今回の記事では、 全くプログラミングを触れたことが無いような中高生を対象に 主にAtCoderや情報オリンピック、ICPCへの参加を考えている方を想定した C++を入門する際に最適な、ブラウザで使用できるコード実行エディタ を制作した話と紹介です！ 良ければこの記事の LGTM、また GitHubリポジトリ の Star よろしくお願いします！ 制作物 こちらのページになります！ Simple C+

周波数領域とか，周期的・非周期的　とか良く分かりませんね． 今は分からなくてもいいですが，このような特性の違う変換があるということを覚えておけば良いです． フーリエ級数展開から説明をするのが一般な気がしますが，今回は直接離散フーリエ変換の解説をします．（個人的にはフーリエ級数展開よりも離散フーリエ変換の方が理解しやすいと思います） 2.直交基底 ところで，次のグラフの紫色の点の座標は答えられますか？ なんてことはない，すぐに $\left(\begin{matrix}x\\y\end{matrix}\right) = \left(\begin{matrix}4\\7\end{matrix}\right)$ と答えられるでしょう． しかし，グラフの端に書かれている軸が $x, y$ 軸とは明示されていないため，ひねくれた座標系のとり方をすると $\left(\begin{matrix}x\\

なんと GbE は HDD よりも遅い． このHDDの記録は自宅にあった WD Blue 5400RPM を適当に Crystal Disk Mark で計測したものです．特にハイエンドHDDというわけではありませんがHDDよりもGbEの方が遅いのです． 更に業務PCや逸般の誤家庭などで，HDDやSSD数枚でRAIDで組んだり，NASだけどNVMe SSDで構成しているような場合は 10GbE でもネットワークがボトルネックになります． 例えば映像クリエイターで動画素材をサーバーに置いた状態でレンダリングをするレンダークラスタをお持ちの方や，サーバーいじりや機械学習などで大量のデータが入ったVHDをNASに置いて運用しているなどの状況ではモロにこのGbEがボトルネックになります． 我が家の場合はサーバーに置いた動画データやVHDのコピーや，デスクトップPCのバックアップをサーバーに転送して