はてなブックマーク

はじめに ついこないだの AtCoder 上のコンテストで出題された問題 AtCoder Beginner Contest 099 C 問題 - Strange Bank が、初心者向けの 300 点問題としては史上最難ではないかということで話題沸騰になりました。 何も考えずに DP (動的計画法) した 辺の長さが 1 の DAG なので BFS でも DP でも Dijkstra でも OK 個数制限なしナップサック問題を復習しないと 全探索 + Greedy でやった といった色んな声が飛び交いました。動的計画法アルゴリズムの設計法などを具体的に学べるすごく教育的な問題だと思ったので、上記の事柄をまとめて整理することを試みます。それにしてもこの問題はコイン両替問題の 1 パターンとして位置付けられますが、色んな取り組み方ができますね。 ABC 099 C - Strange Bank

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

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 1. はじめに 今回は実務プログラミングにおいて知らず知らずのうちに遅いコードになっていそうな例をいくつか挙げて、それを計算量の観点から高速化してみたいと思います。 2. 計算量を意識することにどんな意味があるか 身近な例として、Qiita Contribution ランキングの作成を考えてみましょう。ランキングを作成するためには、各ユーザーの Contribution 数を大きい順に並び替える処理、すなわちソートが必要になります。 Qiita ユーザー数は現在およそ $30$ 万人です。標準ライブラリの sort を用いれば、それほど

競技プログラミングサイト AtCoder へ参加するためのチュートリアル記事 AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ の補足資料ですが、この記事単体でも読めるようになっています。 はじめに for 文を 1 回回してできる処理は、しばしば線形探索といった名前で呼ばれていて、応用情報技術者試験などで頻出のテーマでもあります。本記事を読めば、応用情報に出題される線形探索の問題たちをスラスラと解けるようになると思います。 線形探索は最も基本的なアルゴリズムの 1 つですが、すべての基礎となる極めて重要なアルゴリズムです。世の中の多くの問題はとりあえず「全探索」すれば解が得られることが多いですが、全探索テクニックの最も基本的なものが「線形探索」です。まずは線形探索に習熟することが、アルゴリズム学習の第一歩と言えるでしょう。 それでは、線形探

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

0. はじめに 二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる方が多いと思います。巨大なサイズのデータを扱う場面の多い現代ではそれだけでも十分実用的ですが、二分探索法はもっとずっと広い適用範囲を持っています。 本記事では、二分探索法のエッセンスを抽象化して、適用範囲の広い「二分探索法の一般形」を紹介します。同時に無数にある二分探索の実装方法の中でも「めぐる式二分探索」がバグりにくいと感じているので、紹介したいと思います。 注意 1: 二分探索の計算時間について 二分探索の計算時間について簡単に触れておきたいと思います。例えば「$n$ 個の要素からなるソート済み配列から目的の値を探索する」というよく知られた設定であれば、 単純な

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

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

言語別の競技プログラミング入門資料たち それでは各言語別の入門資料たちをまとめて行きます。 Python 最近は Python で競プロを始める人が激増しています！ データ分析や機械学習において Python がメジャーな言語となったことから、Python を学びたいという方は大勢いるでしょう。Python を勉強したいというモチベーションで AtCoder を始める方も多いと聞きます。計算実行速度の観点からは C++ に比べて不利な感があるので、ARC E 問題以上の難易度に挑むようになったら C++ などの速い言語も覚えていく必要が生じますが、AtCoder 500 点問題までの難易度帯であれば概ね通せるようです。今後 Python で書かれたアルゴリズム解説資料などが充実して行くといいなと思います。 AtCoder に登録したら解くべき精選過去問 10 問を Python3 で解いて

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

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

午後の選択問題が 4 問選択になったのは、私自身が受験した平成 27 年度秋季以降のことです。それまでは 5 問選択でした。 4. 「午前」「午後」それぞれの対策 午前について 午前に関しては、応用情報も基本情報も大きな違いはないです。 多くの方が繰り返し述べているように、本番の問題の半分近くは過去問の使い回しです。仮に 40 % が過去問と同一でそこで 40 % 分得点できたとすると、残りの 60 % 分の問題のうち 1/3 の 20 % 分だけ正解できれば合格です！ 過去問を何年分解けばよいかというのは多くの方が気になるところだと思います。私自身は試験本番 (平成 27 年度秋季) の 2 年前周辺 (平成 25 年度周辺) の過去問の 3 回分を解いて本番に臨んだのですが、10 回分を解けばより安心だと思います。なお、3 回分解くときに直近の 3 回分ではなく 2 年前のセットにした

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 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具

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 つは必要に応じて読んでいただければと思います。反対にビットの知識はあってビットを用いたアルゴリズ

はじめに ビックデータという言葉が流行ってから数年の歳月が経ち、耳にする機会が大分減ってしまいましたが、現在も大規模データを高速に処理していくことは様々な現場で重要な課題となっています。 今回はその一端として、以下の操作を高速に実現するデータ構造について特集します: 集合に要素 $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 つのカテゴリ間で最適なマッチングを構成していく問題です。実

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

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに はじめまして。NTTデータ数理システムでリサーチャーをしている大槻 (Ken) です。 人間と雑談を行うチャットボットを作ることに関心を抱いています。 最近あちこちでチャットボットを耳にするようになりましたね。 Microsoft の女子高生AIりんなや、LOHACO のマナミさん、リクルートテクノロジーズの A3RT Talk API など、様々なチャットボットが盛んに開発されています。その勢いから 2016年はチャットボット元年だったとも言われているほどです。ディープラーニング業界でも自然言語処理系の研究が急速に増えており