Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに: 統計学の重要性 NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回は統計検定 1 級について記します。 統計検定とは日本統計学会による公認の資格であり、統計に関する知識や活用力を評価するものです。 日常的に大量のデータが溢れている昨今、データ分析や機械学習に対するニーズは最高の高まりを見せています。最近では何も考えずともただデータを入力するだけでデータ分析や機械学習手法を実行してくれるツールも多数出回るようになりました。 データ分析や機械学習を実際に遂行するにあたって、統計学は強力な基
0. はじめに: 「数え上げ」という分野について 「条件を満たすものを数え上げる」タイプの問題にはパズルのような楽しさがあります。そのような問題のうち簡単なものは高校数学の「個数の処理・確率」で学ぶのですが、その先にも奥深い世界が待っています。 例: 数え上げテクニック集 (DEGwer さん) 例: 数え上げおねえさん (ERATO 湊離散構造処理系プロジェクト) 本記事では数え上げ問題を解くと度々登場する「写像12相」について整理します。写像12相の中でも特に高度なスターリング数と分割数をメインに取り上げます。これらのテーマが直接的に登場する問題はあまり多くはないですが、包除原理や動的計画法といった技法を学べる格好の題材です。簡単な部分についても重複組合せなどの教育的要素を多く含んでいます。 そんな事情もあって、chokudai さんも「競プロで使う基礎的な数学は写像12相がわかればと
「他にこんなのがある」というのがあったら是非いっぱい教えてください！ 歴史的に最も古くからある用途は「測量」でしょう。三角関数誕生のキッカケはまさに測量の必要性にありました。比較的日常生活でも見る機会がありそうな用途でしょうか。 ログハウス ケーキカット 震災時の家の傾き推定 現代では「波」としての用途が多いでしょうか。Twitter での様々な人のコメントを見ていても、 おっぱい関数 jpeg 画像 音声処理 といった具合に、波に関する話がかなり多いイメージです。これらの三角関数の使われ方を特集してみます。様々な分野に共通する三角関数の使い方のエッセンスを抽出したつもりですが、これでもかなり分量が多くなりました。摘み食いするような感覚で読んでいただけたら幸いです。 2. 三角関数の 3 つの顔 最初に三角関数には大きく 3 つの定義があったことを振り返っておきます。以下の記事にとてもよく
0. はじめに: クォータニオンについて思うこと はじめまして！ NTTデータ数理システムで機械学習やアルゴリズムといった分野のリサーチャーをしている大槻 (通称、けんちょん) です。 本記事は、東京大学航空宇宙工学科／専攻 Advent Calendar 2018 の 3 日目の記事として書きました。僕は学部時代を工学部 航空宇宙工学科で過ごし、情報理工学系研究科 数理情報学専攻で修士取得後、現職に就いて数年になります。 航空宇宙時代は人工衛星の姿勢制御について関心を抱き、特に磁気センサや磁気トルカを用いた姿勢制御系について研究していました。数理工学へと分野を変えてからも、当時お世話になった先輩方と磁気トルカを用いた姿勢制御手法について共同研究して論文を書いたり、ディープラーニングなどを用いた画像認識技術を追求する過程ではリモートセンシングに関する話題ものぼったりなど、航空宇宙業界とは何
NTT データ数理システムでアルゴリズムの探求をしている大槻 (通称、けんちょん) です。好きなアルゴリズムは二部マッチングです。今回は、歴史の記録に残る最古のアルゴリズムの 1 つとして知られるユークリッドの互除法について書きます。 ユークリッドの互除法は、最大公約数を求めたり、一次不定方程式 $ax + by = c$ に応用したりなど、大学受験でもお馴染みのアルゴリズムですが、整数論的アルゴリズムや数え上げアルゴリズムにおいて根幹を成す重要なものでもあります。 今回の記事では特に、一次不定方程式 $ax + by = c$ の整数解を一般に求めるアルゴリズムとして知られる「拡張ユークリッドの互除法」の理解を目指します。 1. ユークリッドの互除法とは ユークリッドの互除法は、2 つの整数 $a$, $b$ の最大公約数を効率よく求めるアルゴリズムです。本記事では $a$ と $b$
はじめに ついこないだの AtCoder 上のコンテストで出題された問題 AtCoder Beginner Contest 099 C 問題 - Strange Bank が、初心者向けの 300 点問題としては史上最難ではないかということで話題沸騰になりました。 何も考えずに DP (動的計画法) した 辺の長さが 1 の DAG なので BFS でも DP でも Dijkstra でも OK 個数制限なしナップサック問題を復習しないと 全探索 + Greedy でやった といった色んな声が飛び交いました。動的計画法アルゴリズムの設計法などを具体的に学べるすごく教育的な問題だと思ったので、上記の事柄をまとめて整理することを試みます。それにしてもこの問題はコイン両替問題の 1 パターンとして位置付けられますが、色んな取り組み方ができますね。 ABC 099 C - Strange Bank
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
0. はじめに 二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる方が多いと思います。巨大なサイズのデータを扱う場面の多い現代ではそれだけでも十分実用的ですが、二分探索法はもっとずっと広い適用範囲を持っています。 本記事では、二分探索法のエッセンスを抽象化して、適用範囲の広い「二分探索法の一般形」を紹介します。同時に無数にある二分探索の実装方法の中でも「めぐる式二分探索」がバグりにくいと感じているので、紹介したいと思います。 注意 1: 二分探索の計算時間について 二分探索の計算時間について簡単に触れておきたいと思います。例えば「$n$ 個の要素からなるソート済み配列から目的の値を探索する」というよく知られた設定であれば、 単純な
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
本記事を終えた次は？ AtCoder Beginners Selection を終えたら、AtCoder 上の過去問が AtCoder Problems に集大成されていますので、片っ端から埋めるような気持ちで精進していきましょう。本記事の続編として AtCoder 版！蟻本 (初級編) AtCoder 版！蟻本 (中級編) AtCoder 版！蟻本 (上級編) AtCoder 版！蟻本 (発展的トピック編) も執筆しましたので参考にしていただけたらと思います。また、アルゴリズムとデータ構造に関するトピックを集大成した書籍として、 問題解決力を鍛える！アルゴリズムとデータ構造 (通称、けんちょん本) を上梓しました。ぜひ読んでみてください。 1. AtCoder とは AtCoder は以下のコンテストサイトを運営しています。今後常に訪れることになるサイトです: AtCoder コンテスト
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0 はじめに 初級編と中級編に続いて、今度は上級編です。 プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0 はじめに プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほと
はじめに はじめまして。 NTTデータ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 C や C++ を使用しているとしばしばビット演算を行う場面が出て来ます。 計算機リソースが限られている状況では、ビットを用いることでデータ量を少なく済ませたり、計算コストを小さく抑えたりすることができるメリットがあります。 本記事では、ビット演算を用いて実現できる処理について、簡単なものから高度なものまで集大成します。極力わかりやすく頑張って執筆しました。特に前半 4 つはビットの説明の中でもかなりわかりやすい方だと思います。後半の 7 つのテーマは比較的高度なアルゴリズムの話題ですので、フラグ管理やマスクビットについて詳しく学びたい方は前半 4 つを中心に読んでいただいて、後半 6 つは必要に応じて読んでいただければと思います。反対にビットの知識はあってビットを用いたアルゴリズ
はじめに 大きなサイズの問題を扱っていると、元の問題のサイズを半分以下にしたい場面がしばしば登場します。二分探索もそうですし、分割統治法もそうです。 ツリーに関する問題に対しても、サイズを半分以下にしたい場面がしばしば登場します。そんなときに重要な概念になるのがツリーの重心です。 ツリーの重心とは ツリーである頂点を取り除くと、元のツリーは何個かのツリーに分裂します。そのすべての部分ツリーのサイズが元のツリーのサイズの半分以下になるような頂点がツリーの重心です。 なおこの図の場合、もう一つ重心があることがわかります。 一般に、ツリーの重心は 1 個または 2 個になります。多くのツリーでは重心は 1 個だけですが、この例については、2 つの重心を結んでいる枝の両端からなる部分木がともに元のサイズの半分ずつになっています。このような状況が発生する場合のみ、重心が 2 個になります。なお、重心
はじめに ビックデータという言葉が流行ってから数年の歳月が経ち、耳にする機会が大分減ってしまいましたが、現在も大規模データを高速に処理していくことは様々な現場で重要な課題となっています。 今回はその一端として、以下の操作を高速に実現するデータ構造について特集します: 集合に要素 $v$ を挿入する 集合から要素 $v$ を削除する 集合に含まれる $k$ 番目に小さな値を取得する 「挿入」や「削除」を行えるデータ構造というと**リストが真っ先に思い浮かびますが、「$k$ 番目に小さな値を求めよ」と言われると一気に難易度が上がります。ついつい平衡二分探索木を使いたくなるのですが、BIT** や priority_queue で対応できるケースも多いです。BIT や平衡二分探索木の詳細についてはとてもよい資料が多数あるので以下に示します。 BIT BIT については hos さんの資料 Bin
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
