概要
Microsoft Copilotのプロンプトを細工して、日本語プログラムを実行させようとする試みです。
問題が、思いつかないので教えてもらった。
Ohisama prompt
競技プログラミングの上達に必要な、 "学ぶべき" アルゴリズムを教えてください。
回答
競技プログラミング（競プロ）は、問題を解くことでプログラミング能力を競う大会です。競プロで上達するためには、様々なアルゴリズムやデータ構造を学び、それらを問題に応用できるようになる必要があります。
競プロで学ぶべきアルゴリズムは、レベルによって異なりますが、一般的には以下のようなものが挙げられます。
- 初級者：全探索、二分探索、深さ優先探索、幅優先探索、動的計画法、ダイクストラ法、ワーシャルフロイド法、クラスカル法、素数判定、べき乗計算、逆元計算、累積和など
- 中級者：座標圧縮、半分全列挙、行列累乗、ダブリング、Grundy数、ローリングハッシュ、平方分割、最大流、最小カット、二部グラフ判定、二部マッチングなど
- 上級者：セグメント木、遅延評価セグメント木、Binary Indexed Tree、Lowest Common Ancestor、Heavy-Light Decomposition、Convex Hull Trick、Z-algorithm、Suffix Array、Segment Tree Beats、Persistent Data Structure、Treap、Link-Cut Tree、Mo's Algorithm、Dynamic Connectivityなど
これらのアルゴリズムやデータ構造を理解するためには、本やウェブサイトなどの教材を利用すると良いでしょう。例えば、以下のような教材がおすすめです。
- 競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術：競プロで必要なアルゴリズム・データ構造・考察テクニックを丁寧に解説した本です。例題や演習問題も豊富にあります。
- レッドコーダーが教える、競プロ・AtCoder上達のガイドライン：AtCoderでレッドコーダー（レーティング2800以上）になるためのガイドラインを書いたウェブサイトです。初級編、中級編、上級編の3つに分かれており、それぞれに必要なアルゴリズムやデータ構造が紹介されています。
- プログラミングコンテストチャレンジブック（蟻本）：競プロでよく使われるアルゴリズムやデータ構造を網羅的に解説した本です。初級から上級までのレベルに応じた問題があります。
これらの教材を参考にして、競プロで学ぶべきアルゴリズムを身につけてください。競プロは、アルゴリズムやデータ構造だけでなく、数学や論理的思考なども必要とします。競プロで上達するには、多くの問題に挑戦し、自分の弱点を克服することが大切です。競プロは楽しくて面白いものですので、ぜひ挑戦してみてください。?
ソース: Bing との会話 2024/2/20
(1) 競技プログラミングの鉄則 アルゴリズム力と思考力を高める77 .... https://honto.jp/netstore/pd-book_31847742.html.
(2) レッドコーダーが教える、競プロ・AtCoder上達のガイドライン .... https://qiita.com/e869120/items/eb50fdaece12be418faa.
(3) 競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77 .... https://www.amazon.co.jp/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E9%89%84%E5%89%87-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%8A%9B%E3%81%A8%E6%80%9D%E8%80%83%E5%8A%9B%E3%82%92%E9%AB%98%E3%82%81%E3%82%8B77%E3%81%AE%E6%8A%80%E8%A1%93-Compass-Books%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%B1%B3%E7%94%B0/dp/483997750X.
(4) レッドコーダーが教える、競プロ・AtCoder上達のガイドライン .... https://qiita.com/e869120/items/acba3dd8649d913102b5.
(5) 『競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める .... https://booklog.jp/item/1/483997750X.
以上。