とても久しぶりです！ 1 年ぶりの投稿となりました、大槻 (通称、けんちょん) です。 去年、『AtCoder 版！マスター・オブ・整数』と題して、プログラミングコンテストで出題される整数問題を解くときに有効な考え方を特集する記事を 2 本書きました！ AtCoder 版！マスター・オブ・整数 (素因数分解編) AtCoder 版！マスター・オブ・整数 (最大公約数編) 今回はその続編として、素数を列挙するアルゴリズムであるエラトステネスの篩を特集していきます。なお今回の記事の内容は、競プロへの応用を意識していますが、純粋に数学的興味に沿って読み進めることもできるものになっています。下図は、これから紹介するエラトステネスの篩のイメージ図です。 0. はじめに エラトステネスの篩は、$1$ 以上 $N$ 以下の素数をすべて列挙する方法です。たとえば $20$ 以下の素数を列挙すると、$2,

本記事を終えた次は？ AtCoder Beginners Selection を終えたら、AtCoder 上の過去問が AtCoder Problems に集大成されていますので、片っ端から埋めるような気持ちで精進していきましょう。本記事の続編として AtCoder 版！蟻本 (初級編) AtCoder 版！蟻本 (中級編) AtCoder 版！蟻本 (上級編) AtCoder 版！蟻本 (発展的トピック編) も執筆しましたので参考にしていただけたらと思います。また、アルゴリズムとデータ構造に関するトピックを集大成した書籍として、 問題解決力を鍛える！アルゴリズムとデータ構造　(通称、けんちょん本) を上梓しました。ぜひ読んでみてください。 1. AtCoder とは AtCoder は以下のコンテストサイトを運営しています。今後常に訪れることになるサイトです: AtCoder コンテスト

今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場

2. 共円定石 メジャーなものから超マイナーなものまで、九路盤定石をすべて公開します！！！ 定石 0: 自明パターン 比較的自明な場合として 一直線上 (ルール) 長方形 等脚台形 が挙げられます。いずれも共円であることが自明なパターンですが、このうち等脚台形については、斜め 45 度の等脚台形に注意が必要です。しばしば見逃してしまいます。 余談ですが「斜め 45 度じゃない等脚台形」も一応あります。例えば下図は確かに等脚台形になっています！3 定石 1: 八角形 続いてこれも比較的わかりやすい八角形定石です。内角がすべて $135$ 度になっていて、対称性から共円になることが明快です。しかし右図のように 4 点だけを取り出すと、意外と指摘が難しいことがわかると思います。このような共円をほぼ確実に避けられるようになると脱初心者と言えるでしょう！ 八角形定石のサイズにはバリエーションがあり、

0. はじめに 気軽な気持ちでプログラムを書いたら計算量オーダーが $O(n^2)$ になってしまって処理がメチャクチャ遅い、というのは大変あるあるです (この記事など)。そういった状況を打破するために、古来から $O(n^2)$ なアルゴリズムを $O(n)$ や $O(n\log{n})$ に改良するテクニックは無数に考案されて来ました。逆に本来なら $O(n)$ で終わるはずの処理を雑に実装したために $O(n^2)$ になってしまうトラップも無数に知られています。その辺りの話は以下に特集してみました: 特集！知らないと損をする計算量の話 今回は $O(n^2)$ を $O(n)$ にするテクニックの 1 つであるしゃくとり法について、個人的に思うことを書いて行きます。またしゃくとり法を用いる以下の問題たちを紹介します: AOJ Course The Number of Window

0. ゲームを解くとは 世の中には将棋や、囲碁や、オセロのような複雑で難しいゲームから、マルバツゲームや、割りばしゲームや、立体三目並べのような比較的単純なゲームまで、たくさんの種類のゲームがあります。 この種の二人プレイのボードゲームにはある共通の特徴があります。それは 双方が最善を尽くした場合において、「先手必勝」か「後手必勝」か「引き分け」かが予め決まっている。 そして無限の計算時間と計算機資源さえあれば、それを容易に解析できる。 という点です。このように 「先手必勝」か「後手必勝」か「引き分け」なのかを解析する その必勝手順を求める できれば + α として初期盤面だけでなく、すべての局面について「先手勝ち」か「後手勝ち」か「引き分け」かも特定して最善手も求める という営みが「ゲームを解く」ということであり1、それができたならばそのゲームを「完全に理解した」ということができます。本

1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443

NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると

1. はじめに 今回は実務プログラミングにおいて知らず知らずのうちに遅いコードになっていそうな例をいくつか挙げて、それを計算量の観点から高速化してみたいと思います。 2. 計算量を意識することにどんな意味があるか 身近な例として、Qiita Contribution ランキングの作成を考えてみましょう。ランキングを作成するためには、各ユーザーの Contribution 数を大きい順に並び替える処理、すなわちソートが必要になります。 Qiita ユーザー数は現在およそ $30$ 万人です。標準ライブラリの sort を用いれば、それほどの計算時間はかからないと思います。しかし仮にこれを愚直な sort アルゴリズム (例えば、挿入ソートやバブルソートなど) で実行したら恐ろしいことになります。 愚直なソートは、並び替える要素の個数の 2 乗に比例した時間がかかります。すなわち $n$ を並

NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や

0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実問題で登場する二部マッチングは以下のように多岐にわたります: マッチングアプリで男女のペアを最適化する (「男」と「女」) インターネット広告分野で、ユーザの興味に合う広告を出す (「ユーザ」と「広告」) 企業検索サービスなどで、ユーザの検索履歴に合う企業を

はじめに --- DP は役に立つ はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 巷ではよく「DP なんて実務では使わない」といった言説が定期的に流れますが、そんなことはないです。僕自身この 2 年間で DP が使える実務案件に 3 件くらい関わりました！ それはともかくとして、DP を学び立ての方がよく抱く悩みとして「バリエーションが多すぎて混乱するし、統一的なフレームワークがほしい」というのがあります。確かに DP のバリエーションは非常に多岐にわたるのですが、そのほとんどが以下の 3 つのフレームワークで説明できると思います: ナップサック DP 区間 DP bit DP 今回はこのうちのナップサック DP について、とにかく