アルゴリズムの知識がない状態でAtCoderの問題を解いて勉強する方法
はじめに
この記事では、アルゴリズムの知識がない状態で競技プログラミングの問題を解くことを通して、アルゴリズムの勉強をする方法について書き記します。
予め補足しておくと、効率的・体系的にアルゴリズムの勉強をしたい人などには向いていない勉強方法だと思われます。数学パズルのように自力で解いていく楽しさや、自分が思いつかなかった新しい解法で問題を解けるようになっていく楽しさを味わいながら、実践的にアルゴリズムの知識をつけていきたい人向けの記事となります。
この記事で扱う問題は、AtCoderのABC387のD問題です。
勉強方法
0. 過去問を選ぶ
AtCoderでは、過去問を時間無制限でいつでも解くことができます。AtCoder Problemsに過去問のリンク集があるので、そこで問題を探してみましょう。
問題の選び方についてですが、プログラミング初心者はA, B問題。プログラミング経験者でアルゴリズムの知識があまりない人はC, D問題を解くのが良いと思います。
AtCoderでは様々なプログラミング言語で問題を解くことができます。解説はC++がほとんどなので、使えるならC++。使えないなら好きな言語で解いて良いでしょう。私の場合は業務で使っているJavaで解いています。
1. 自力で自由に問題を解く
まずは自力で問題を解いていきましょう。自力で解ければそれでOK。解けなくても、自分で工夫して考えること自体に意味があります。
難しくてなかなか問題が解けなくても大丈夫です。どれだけ粘っても良いですし、頃合いを見て次のステップに進んでも良いでしょう。楽しんだり、自分が納得のいくまで挑戦することが、継続して学習する上で大事なことです。
2. AtCoderの解説を見る
解けても解けなくても、AtCoderの解説は読んでおくことをおすすめします。より効率的な解き方が見つかるかもしれません。
過去問であれば、以下の部分に解説のリンクが表示されるはずなので、そちらをクリックして見てみましょう。
AtCoderの解説へのリンク。もちろんコンテスト本番では表示されないが、過去問を解く際は表示される。
この解説で明確になったことは、BFS(幅優先探索)というアルゴリズムを使って問題を解く必要があるということです。このステップでは、使用するアルゴリズムが分かっただけでも十分です。
ちなみにこの解説ですが、問題を解く上での基本的な考え方は記載してくれるものの、実装の細かい意図については解説してくれません。解説動画は実装しながら話してくれるのでまだ意図を汲み取れますが、動画時間がかなり長いのが欠点です。
その他、変数名が分かりにくい・コード中にコメントが一切書かれていないなど、解説に使われているソースコードは綺麗とは言えないものになっていて、そのまま真似てもどんな処理をしているのか分かりにくくなっています。
また、使用している言語がC++でない場合、そもそも解説のソースコードを理解することが難しいです。問題の解き方に関する基本的な考え方がある程度分かった時点で、次のステップに進みましょう。
3. 生成AIでアルゴリズムとプログラミングでの解き方について質問する
ここが今回の記事のポイントとなる部分です。アルゴリズムの概要や、そのアルゴリズムを使って解く必要のある問題例、自分が使用しているプログラミング言語(私の場合はJava)での問題例の解き方を生成AIで質問することが重要です。
なぜ生成AIに質問するのが重要かというと、以下の条件を全て満たす記事は基本的に存在せず、仮に存在したとしても、生成AIの回答の方が質が高い場合がほとんどだからです。
- アルゴリズム自体の簡潔な解説が書かれている
- 具体的な問題例を出題してくれる
- 自分が使用している言語で、その問題例の解き方を解説してくれる
実際にChatGPTでJavaでの解法について聞いたところ、返ってきたソースコードが以下になります。その時に使用した生成AIのプロンプトは「幅優先探索に関する問題例を、Javaを用いて解いてください。」で、凝ったプロンプトは使用していません。
AIで生成されたJavaのソースコード (長いのでアコーディオンで格納)
import java.util.*;
class MazeSolver {
// 移動方向（上下左右）
private static final int[] dx = {0, 0, -1, 1};
private static final int[] dy = {-1, 1, 0, 0};
public static int bfs(int[][] maze, int startX, int startY, int goalX, int goalY) {
int n = maze.length;
int m = maze[0].length;
boolean[][] visited = new boolean[n][m];
Queue<int[]> queue = new LinkedList<>();
// 初期位置をキューに追加し、訪問済みにする
queue.add(new int[]{startX, startY, 0}); // {x, y, 距離}
visited[startX][startY] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int dist = current[2];
// ゴールに到達したら距離を返す
if (x == goalX && y == goalY) {
return dist;
}
// 上下左右の移動を試す
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 迷路の範囲内かつ通行可能で未訪問ならキューに追加
if (nx >= 0 && ny >= 0 && nx < n && ny < m && maze[nx][ny] == 0 && !visited[nx][ny]) {
queue.add(new int[]{nx, ny, dist + 1});
visited[nx][ny] = true;
}
}
}
return -1; // ゴールに到達できない場合
}
public static void main(String[] args) {
int[][] maze = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0}
};
int startX = 0, startY = 0;
int goalX = 4, goalY = 4;
int result = bfs(maze, startX, startY, goalX, goalY);
if (result != -1) {
System.out.println("最短経路の長さ: " + result);
} else {
System.out.println("ゴールに到達できません。");
}
}
}
変数名の指定や細かいコメントにより非常に分かりやすいコードとなっています。もちろん、ソースコードの解説についても併せて記載してくれるので、どの変数がどの意図で使われ、どのように処理を進めていくのかについて理解しやすくなっています。
ChatGPTによるソースコードの解説。ここまで細かくソースコードの解説を書いてくれる記事はあまり見たことがない。
もちろん、アルゴリズムの詳細な情報を知りたいのであれば、アルゴリズムに関する書籍を読むのが一番です。必要に応じて書籍からアルゴリズムについて学びつつ、問題例とその解答を生成AIで確認し、実装方法を学んでいきましょう。
4. 生成AIの実装を真似ながら、AtCoderの問題にもう一度挑戦する
ある程度解き方が分かったところで、再び問題を解いてみましょう。
このABC387のD問題は、縦移動と横移動を1回ずつ交互に行うという制約が設けられており、その制約を実装に落とし込むのがポイントとなっています。最初の移動は縦横どちらでも良いということにも注意して実装を行うと、うまくいくと思います。
このような解き慣れていない問題を解く上で重要なことが、デバッグをしながら実装するということです。例えば以下の私の解答を見てみると、スタート地点からの距離をdistancesという名前の2次元配列に格納し、どの地点がどの距離になっているかデバッグで視覚的に分かるようにしています。
ABC387 D問題の私のJavaの解答
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
private static int h;
private static int w;
private static char[][] chars;
private static int[] start = new int[2];
private static int[] goal = new int[2];
private static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args) {
var sc = new Scanner(System.in);
h = sc.nextInt();
w = sc.nextInt();
var strings = new String[h];
for (int i = 0; i < h; i++) {
strings[i] = sc.next();
}
sc.close();
// 文字列の配列をcharの2次元配列にする。
chars = new char[h][w];
for (int i = 0; i < h; i++) {
chars[i] = strings[i].toCharArray();
}
// スタート位置とゴール位置を特定する。
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (chars[i][j] == 'S') {
start[0] = i;
start[1] = j;
} else if (chars[i][j] == 'G') {
goal[0] = i;
goal[1] = j;
}
}
}
var result = bfs();
System.out.println(result);
}
private static int bfs() {
int result = 0;
// スタート地点で左右に行く場合をi = 0, 上下に行く場合をi = 1とする。
for (int i = 0; i < 2; i++) {
Queue<int[]> queue = new LinkedList<>();
queue.add(newIntArray(start[0], start[1], 0));
// 既に訪れた地点にtrueを入れて記録する。
var visitedPlace = new boolean[h][w];
visitedPlace[start[0]][start[1]] = true;
// // スタートからの移動距離。(デバッグ用)
// // 配列を初期化すると全ての要素に0が入るので、スタート位置の距離を1として、最後に1を引くこととする。
// var distances = new int[h][w];
// distances[start[0]][start[1]] = 1;
while (!queue.isEmpty()) {
int[] currentLocation = queue.poll();
var y = currentLocation[0];
var x = currentLocation[1];
var distance = currentLocation[2];
if (y == goal[0] && x == goal[1]) {
if (result == 0) {
result = distance;
} else {
result = Math.min(result, distance);
}
}
// 縦移動の場合は上移動がj = 0, 下移動がj = 1
// 横移動の場合は右移動がj = 0, 左移動がj = 1
for (int j = 0; j < 2; j++) {
int nextY;
int nextX;
// 縦移動か横移動か制約を確認し、次の地点を調べる。
if ((i + distance) % 2 == 0) {
nextY = y + move[j][0];
nextX = x + move[j][1];
} else {
nextY = y + move[j + 2][0];
nextX = x + move[j + 2][1];
}
// 道ではない場合false
var flag = nextY < h && nextY >= 0 && nextX < w && nextX >= 0;
if (flag && chars[nextY][nextX] == '#') {
flag = false;
}
// 既に訪れた場所には進まない
if (flag && visitedPlace[nextY][nextX]) {
flag = false;
}
// 進める道であれば、次の探索地点をqueueに加える。
if (flag) {
queue.add(newIntArray(nextY, nextX, distance + 1));
visitedPlace[nextY][nextX] = true;
// デバッグ用
// distances[nextY][nextX] = distance + 1;
}
}
}
}
return result == 0 ? -1 : result;
}
private static int[] newIntArray(Integer y, Integer x, Integer distance) {
return new int[]{y, x, distance};
}
}
このような工夫を入れることで、プログラムが意図しない挙動にならないか確認できます。もし合っていれば、どのような順序でBFSによる探索が進んでいくのかも視覚的に確認でき、更にBFSに関する理解が進むでしょう。
おわりに
アルゴリズムを知らない状態での競技プログラミングを用いたアルゴリズムの勉強法は以上です。まず自由に問題を解き、その後解説を見てアルゴリズムを把握します。そして、生成AIでアルゴリズム自体の解説と問題例・解答例を出してもらい、デバッグをしながら自分で実装していくという流れになります。
生成AIの発展により、少なくとも技術ブログよりは有益な情報が、生成AIに聞くだけで簡単に得られてしまう時代になりました。生成AIは特に、基礎的な理系の知識に関する回答の精度が非常に高いと思うので、このような技術系の学習やエラーの対処法の調査などがしやすくなり、たいへん良い環境になったと思います。
余談: 最新情報を含まないtech系ブログ記事より生成AIの解説の方が良いことについて
余談ですが、私がZennでいうところのtech系の記事を書きたがらない理由も、生成AIの発展によるものです。個人が最新でない技術について記事を執筆しても、生成AIの回答の質以上の記事はなかなか書けません。そのため、読者側が生成AIではなく技術ブログを見るようなインセンティブが働かない時代になったと思っています。
著者側のアウトプットにより頭の整理ができることや技術ブログを書くことで転職で有利になることなどのメリットを活かしつつも、生成AIが苦手だと思われる人の特性が関わる話(勉強法やキャリアパス、スクラムなどの開発手法に関することなど)を取り上げることで、読者側にも一定メリットがある記事を書きたいと個人的に考えています。
Discussion