USB C ケーブル タイプc 1M/2M 各２本 PD対応 60W超急速充電 断線防止 高速データ転送 Type-C to Type-Cケーブル for iPhone 16/15 Pro/Plus/Pro Max MacBook iPad Galaxy Sony Google Pixel 7a等USB-C各種対応
￥899 (2025年4月28日 13:05 GMT +09:00 時点 - 詳細はこちら価格および発送可能時期は表示された日付/時刻の時点のものであり、変更される場合があります。本商品の購入においては、購入の時点で当該の Amazon サイトに表示されている価格および発送可能時期の情報が適用されます。)
ここ3年ほど競技プログラミング(競プロ)に取り組んでいます。
競プロというのは、与えられた問題をプログラミングを用いて解いてその結果を競うものです。大学受験の数学の問題みたいなものを想像してもらうと分かりやすいと思います。
先日、社内の勉強会で競プロについて紹介する機会があり、競プロのコンテストのジャンルやどういった問題が出題されるのかといった基本的な事柄を紹介することで布教を試みました。この記事では、そういった内容については簡単な紹介に留め、私のこれまでの競プロへの取り組み方や、やってみて感じたことについて書いてみたいと思います。一社会人が競プロに対してどのような思いを持って参加しているかの参考になれば幸いです。
ちなみに、私は基本的にAtCoderのコンテストに参加しているため、この記事の内容はAtCoderのルールなどを前提としています。競プロについてのより詳細な情報を知りたい方はAtCoderのこちらのページ1を参照ください。
- 大学は文系 (高校数学は数2Bまで)
- 競プロを始めた時点ではSE歴7年目くらい
- 業務では主にC++,Javaを使用
- 競プロの使用言語はRust (最初の半年くらいはC++でしたが、途中でRustに乗り換えました)
- 競プロ歴: 3年くらい
- 現在のレートは、 アルゴ:水、ヒューリスティック:黄 2
AtCoderでは大きく分けてアルゴコンテストとヒューリスティックコンテストの2種類のコンテストが開催されています。以下ではそれぞれのコンテストの概要について簡単に紹介します。
アルゴリズムコンテスト
アルゴリズムコンテストは数学やアルゴリズムの知識を問われる問題が出題され、問題の厳密解を求めることが要求されます。
問題の種類は色々ありますが、基本的には、愚直に解くと制限時間内に解を求めることができないような問題を、なんとか工夫して計算量を改善するみたいな感じの問題が多いと思います。
問題の難易度に応じて点数が決まっており、総合得点(同点の場合は提出時間の早い人が上位)により順位が決定します。
問題の紹介
参考までに、計算量改善のイメージがしやすいような問題をABCの過去問から簡単に紹介します3。
数列$A_1,..,A_N$が与えられるので、$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i – A_j|$を求めよ ($N\leqq2\times10^5$)。
愚直解
愚直に解くと以下のようなコードになりますが、計算量は$O(N^2)$であり、実行時間制限(2sec)に間に合いません。
ans = 0
for i in range(0, N):
for j in range(i+1, N):
ans += abs(A[i] - A[j]);
print(ans)
改善版
実行時間制限に間に合うように改善したものが以下のコードです。2重ループが1重ループになっており、ソートを含めると計算量は全体として$O(N\log N)$となっています。
コードの内容を簡単に説明すると、Aをソートすることで絶対値を外せるようにし、各要素が足し引きされる回数を考えることでループを一つ減らしているようなイメージです。もう少し詳細な解説を聞きたい方は公式の解説放送を参照ください3。
A = sorted(A)
s, ans = 0, 0
for j in range(0, N):
ans += A[j] * j - s;
s += A[j]
print(ans)
ヒューリスティックコンテスト
ヒューリスティックコンテストでは厳密解を求めることが難しいような問題において、なるべく良い解（スコアが高い解)を求めることが要求されます。スコアがより高い人が上位になります。
問題の紹介
実際のコンテストの問題は設定が複雑なことが多いので、ここでは巡回セールスマン問題について説明します。巡回セールスマン問題というのは、複数の都市を訪問し出発地点に戻るときの移動コストが最小のものを求める問題です。
この問題は、頂点数が多い場合には現実的な時間内に厳密解を求めることが難しくなります。一方で、ヒューリスティックなアプローチをとることで、頂点数が多い場合でもそこそこの時間でそこそこの解を求めることができることが知られています。
素朴なアプローチ
まず素朴なアプローチとして、「訪問する都市の順番をランダムに作成しその時の移動コストを計算する」ことを何度か繰り返し、その中でコストが最小のものを採用する、というアプローチが考えられます。確率の問題になりますが、運が良ければそれなりに良い解を引ける可能性があります。
山登り法・焼きなまし法4
もう少し賢いアプローチとして、山登り法・焼きなまし法といった手法を利用することができます。これは、「訪問する都市の順番の一部を入れ替え(状態遷移)、移動コストが改善されていればその遷移を受け入れる」ことを繰り返すという手法です。少しずつ状態を変更していくことで確実に少しずつ移動コストを改善していくことができ、ランダムに解を生成するよりも良い解を作ることができるようになります。
ここではざっくりとしか説明できませんが、以下のような点に工夫の余地があり、この辺りを改善していくことでスコアに差が付いてくることになります。
- 遷移の方法
- スコアが改善されているかどうかの評価方法
- 遷移をなるべく多く繰り返すための性能改善
アルゴリズムコンテストへの取り組み
水色になるまで
基本的に毎週土曜日にAtCoderで開催されているABCに参加しています。ABCコンテストというのは初心者~中級者くらいを対象にしたコンテストで、現在はA-Gの7問が出題されています。
コンテストに参加する以外に、普段は過去のコンテストの問題を練習として解いています。水色になるまでは基本的にC,Dくらいまでの問題を埋めていました。
ABCコンテストは、A・Bがプログラミングができれば解ける問題、C・Dは初等的なアルゴリズムやデータ構造を使うような問題が出題される印象です。
C・Dくらいだと、普通の人がぎりぎり思い付けるか、思い付けないにせよ解説を見てアハ体験できるくらいの難易度で、私はこれくらいの難易度の問題を解いているのが一番楽しいです。普通にプログラムを書けるという人が解いてみて面白く感じるのもこの辺りの問題かなと思います。私は水色になるまでの1年間でこのあたりのレベル帯までの問題を1300問くらい解いているようでした5。
この難易度帯で出てくる名のあるアルゴリズムとしては例えば以下のようなものがあります。6
- 全探索 (DFS,BFS,bit全探索など)
- 二分探索
- 簡単な動的計画法 (DP)
- ダイクストラ法、ワーシャルフロイド法 (最短経路問題)
- クラスカル法 (最小全域木問題)
- 累積和
- グラフ、木
覚えるべき名のあるアルゴリズムはそれほど多くないのですが、これらの使い方に無数の名もなき典型があります。そういったことを覚えていくことで解ける問題が増えていくことが競プロをやっていて楽しい点の一つかなと思います。
このレベル帯の問題で自分が知らない知識が問われることはほぼなくなってきます。そのため、ぱっと見で解けない問題に遭遇したときは、ゼロから考えるというよりも、自分の知っている何かしらのアルゴリズムを適応できるんだろうなという観点で考えることができるようになっている気がします。また、アルゴリズム自体は知っていても適応するための工夫の方法に自分にとっての新しさがあったりするので、そういった点に気付く過程も面白いし、まだまだ勉強の余地があるなと思います。
水色以降
水色になってからはABCコンテストのE・F問題を解く練習をしています。E・F問題くらいになると、複数の典型を組み合わせる問題や数学的考察が必要な問題が増える印象です。
これくらいの難易度になると、私にはなかなか自力では解法を思い付けず、解説を見ても簡単には理解できず、頑張って理解できたと思っても数週間経つと忘れてしまうという感じで停滞気味です。
おそらく難しい問題に対して自分が納得いくまで考え抜く思考力や問題を抽象化して典型として自分の中に落とし込む力が不足しているんだろうなと思います。自分の人間性や根底の性格がレートに反映されているようで恥ずかしい限りですが..まだまだ青までの遠い道のりを感じます。
難しい問題を解けるようになるための練習
自分にとって解けない問題を解こうとするとき、普通は以下のようなステップを踏むのかなと思います。
- 自分で考えてみる
- 解説を見て解法を理解する
- 理解したことをもとに自分で実装する
- 新しいアルゴリズムやデータ構造が必要だったのであればそれをライブラリ化したりする
- 類題を解く
私の経験上、自分で解けない問題は残念なことに解説を見てもだいたい簡単には理解できないことが多いです。そのため、解説をヒントにしながら改めて自分で考えたり、公式解説以外の解説記事を探したりして理解していく必要があります。解説を理解した上で問題を解けるようになるために、1日くらいは平気でかかります。それに加えて、データ構造などの中身を理解してライブラリ化したり、類題を解いたりしていると、合計で1週間くらいかかることも多いです。私は途中で面倒になって諦めちゃうことも多いですが(だから強くなれないのですが)、強い人たちがこういったことを繰り返しているのかなと思うと頭が上がりません。
ヒューリスティックコンテストへの取り組み
ここ1年くらいはヒューリスティックのコンテストにも積極的に参加しています。アルゴリズムコンテストはある程度前提知識が必要で、それなりにやり込まないと満足行くくらい勝てるようになるのは難しい印象です。一方で、ヒューリスティックは前提となる知識もそれほど多くなく、ちょっとした閃き、分析力、実装力があればアルゴが強い人にもそれなりに勝てることもあるので、やっていて楽しいです。
また、私は数学的な考察よりもプログラミングパートが好きなので、そういう面もヒューリスティックに向いているのかなという気がします。
アルゴの難しい問題は「こんなの天才でないと初見で解けるはずない」という気持ちになることが多いですが、 ヒューリスティックの問題は解説を見ると「なんでこんな簡単なことが思いつかなかったんだ」という気持ちになることが多いです。
逆に、そういった簡単なアイデアを思い付くことができればそれなりの順位を取ることができたりします。複雑なことを色々やるよりも、シンプルなアイデア一つでスコアが改善されたり実装が楽になったりするのは実務にも通じるところがあって勉強になります。
上位陣の解法や参加記などを見ていると、自分の書いているコードがどのような特性をもっているか、どこに課題があるか、などの分析がすごく緻密だなと思います。例えばchokudaiさん(AtCoderの社長)のこの記事7などは思考過程が可視化されていてすごく参考になりました。
私が大雑把にしか捉えられていなかったことを分解して具体的化できており、それに対する課題や対応策を検討できているように見えます。こういうところが強さの秘訣なのかなと思いますし、仕事でも役に立つ考え方だなと思います。
最近は生成AIの競プロの実力が上がっており、アルゴリズムコンテストにおいては完全に私よりも強くなっています。ただし、ヒューリスティック問題においては、問題が複雑なこともあり、問題を丸投げするだけで良い解が得られることは今のところ少ないです。しかし、データ分析に使ったり、ツールの作成をお願いしたり、複雑な実装をお願いしたり、部分問題の解き方を聞いたり、それなりに実装方針をこちらで定めて意図を持って質問したりするなど、上手に使うとめちゃくちゃ役に立つ丁度良い感じの関係性になっていて、生成AIを使う練習として役に立っている実感があります。
マスターズ選手権に出場した話
今年は会社でメンバーを募って第二回マスターズ選手権8に参加し、決勝に行くことができました。経験者は私だけで、事前にあまり準備する期間もないという状況でしたが、予選では2人にはヴィジュアライズツールの作成やアイデアを出してもらったりして貢献してもらいました。
生成AIが使えることもあり、経験者でなくとも充分貢献できるような環境になっていることを実感しました。もしまた機会があれば決勝の模様をお伝えしたいと思います。
(鉱石(a)を拾って穴(A)に落としていく様子です)
実装スピード、正確性が上がった
簡単な問題を速く解く練習をたくさんしたり、重実装問題でも複雑にならないように解き方を工夫したり、コーナーケース9に引っかからないように注意する癖が付いたりしたことで、実装スピードや正確性が上がったと思います。
仕事で実装スピードがボトルネックになることは稀ですが、ちょっとしたコードのプロトタイピングがスムーズにできたり、実装方針をイメージしやすくなったりしたことは、仕事でも役に立っている気がします。
謙虚になった
毎週コンテストに参加して悔しい思いをし、自分より圧倒的に実装力や思考力がある人がたくさんいる現実を突きつけられ、それがレートとして可視化されるので、自分の実力や才能を客観視でき謙虚になりました。
それなりにプログラミングに自信があるという人も競プロをやっているとどこかのタイミングでは壁にぶつかると思うので、今のままプログラミングばかりしていて良いのか、その他の能力も伸ばしていったほうが良いのか考え直す良い機会にもなるのかなと思います。
新しいことを勉強できることが楽しい
新しいアルゴリズムやデータ構造を勉強できることが純粋に楽しいです。競プロをやっていると、こんな問題がこんな計算量で解けるんだという小さな感動がたくさんあります。累積和を求めておくことで区間和がO(1)で求まるとか、区間更新・区間和取得がO(logN)でできるとか、木の2点間の距離がO(logN)で求まるとか、フィボナッチ数列の第N項がO(logN)で求まるとか、今でも初めて知った時の感動を思い出せるほどです。
資格試験の勉強や読書でも新しいことを勉強できますが、それらと比較すると、競プロは最初に自力で問題を解こうとしているぶん、その解法や発想が自分にはこれまでなかったものであるということが自覚しやすく、それが感動に繋がっているのかなという気がします。
覚えた知識が身になっている
資格試験で覚えたことはすぐに忘れちゃいがちですが、競プロでは解法を覚えるだけでは不十分で、実際に自分で使えるようになるまで定着させることが必要です。自転車の乗り方を覚えるみたいな感覚に近いです。そのため、付け焼き刃でなく本当に自分の実力が向上したということが自覚しやすく、それが楽しさや達成感みたいなものに繋がっている気がします。
これまでの競プロへの取り組み方や思いを書いてみましたがいかがでしたでしょうか。競プロに興味のある人に参考になっていれば幸いです。
個人的な思いとしては、長くレートが停滞してしまっていることもあり、社内の勉強会やこの記事を書くことで何か打開するきっかけになればいいなと思いもありました(具体的には、競プロを布教することで、誰かハマってくれたりこっそりやっている人が見つかったりして、誰か私に競プロを教えてくれ！という思惑がありました)。またもう少し強くなった暁にはここで報告させてもらいたいと思います。
USB C ケーブル タイプc 1M/2M 各２本 PD対応 60W超急速充電 断線防止 高速データ転送 Type-C to Type-Cケーブル for iPhone 16/15 Pro/Plus/Pro Max MacBook iPad Galaxy Sony Google Pixel 7a等USB-C各種対応
￥899 (2025年4月28日 13:05 GMT +09:00 時点 - 詳細はこちら価格および発送可能時期は表示された日付/時刻の時点のものであり、変更される場合があります。本商品の購入においては、購入の時点で当該の Amazon サイトに表示されている価格および発送可能時期の情報が適用されます。)
