まえがき
普段は業務で TypeScript（Node.js）を使いバックエンド開発をしている3年目のエンジニアです。
AIの進化が加速する中で、「自分の実装力が全然上がっていないな」と感じることが増えてきました。
特に、ロジックを考える瞬発力/思考力が以前より落ちている実感があり、これはまずい と思ったのがきっかけです。
そこで、改めて実装力を鍛えるために、競技プログラミング（AtCoder）を始めることにしました。
実は1年ほど前に興味本位で数回コンテストに出たことはあるのですが、継続できずに終わっていました。
どうせやるなら業務にもシナジーがある方が良いと思い、使用言語はTypeScriptで挑戦してみようと思います。
目標は、まずは 緑コーダー（Rating 800以上）になることです。
ちなみに、緑コーダーのレベル感は以下の通りです（引用元：AtCoderの色別に期待できる能力）。
Rating 800以上（緑）
様々なアルゴリズムやデータ構造を、与えられた課題に対し適切に適用することが出来ます。問題の言い換えなどが必要な高難度の問題には対処できないことが多いです。
コーディングの安定感、速さに信頼がおけます。計算量への意識も高く、ボトルネックとなる箇所において、実行時間がとても遅いプログラムを書いてしまう、などといったことも少なくなります。
業務上よく発生する複雑な処理は、これくらいの難易度までの処理が多いため、解ける/解けないという視点においては、職種によってはこのレーティングを上限と見て良いです。一方、速さや正確さにはまだまだ先があります。
競技者としては、この色を目標に1年以上取り組んでいる人も多く存在します。素養がなければこの色に到達するのはかなり難しく、一定の競技者の目標となるのがこの色です。1000問程度の過去問を解いても到達できないユーザも多数います。
このシリーズでは、アルゴリズムとデータ構造を体系的に学び直しながら、緑コーダーを目指す過程を記録していきます。
最初のテーマは「全探索（Brute Force）」です。
というか、ブルートフォース攻撃って、ここから来ていたんですね...(いまさら)
全探索とは
そもそも全探索とは名前の通り、
考えられるすべてのパターンを一つずつ試して、条件を満たすものを探す方法。
と定義されるようです。
競プロを始める上で最初に必ず身につけておくべき基本中の基本のアルゴリズムらしいです。
全探索の学習において、ABC(AtCoder Beginner Contest)087のB問題が非常に良問だそうなので、今回はこの問題を解いていきたいと思います。
ABC087B
問題文
あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。
これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。
制約
- 0 ≤ A, B, C ≤ 50
- A + B + C ≥ 1
- 50 ≤ X ≤ 20,000
- A, B, C は整数である
- X は 50 の倍数である
入力
入力は以下の形式で標準入力から与えられる。
A
B
C
X
出力
硬貨を選ぶ方法の個数を出力せよ。
最初に思いつく解法は、素直に500円, 100円, 50円の枚数を0~上限で試して、合計X円になればカウント。
~~ Scannerクラスは省略 ~~
function solve() {
const sc = new Scanner();
const [A, B, C, X] = sc.nextInts(4);
let output = 0;
for (let i = 0; i <= A; i++) {
for (let j = 0; j <= B; j++) {
for (let k = 0; k <= C; k++) {
if (500 * i + 100 * j + 50 * k === X) output++;
}
}
}
console.log(ans);
}
if (require.main === module) solve();
これだとシンプルですが、オーダーは 51^3 ≒ 130,000回 です。
これをもっと競プロ的に考えると、「50円の枚数は500円の枚数と100円の枚数が決まれば自動的に決まる」ので、ループではなく式に置き換えられます。
例えば、
X = 600、i = 1枚（500円）、j = 0枚（100円）のとき、
i = 1, j = 0 → 残金 = 600 - 500 = 100
となり、残金 / 50 = 2 で50円の枚数をループではなく式で求めることができます。
これにより3重ループから2重ループに改善できたので、オーダーは 51^2 ≒ 2,600回 まで減らせました。
先ほどのコードにこの改善を加えると、
~~ Scannerクラスは省略 ~~
function solve() {
const sc = new Scanner();
const [A, B, C, X] = sc.nextInts(4);
let output = 0;
// 500円の枚数上限を決める
for (let i = 0; i <= Math.min(A, Math.floor(X / 500)); i++) {
const remAfter500 = X - 500 * i;
// 100円の枚数上限を決める
const jMax = Math.min(B, Math.floor(remAfter500 / 100));
for (let j = 0; j <= jMax; j++) {
const rem = remAfter500 - 100 * j;
// 残金が50円何枚分かを割り出し、配られた50円の枚数以内であればカウント
const k = rem / 50;
if (k <= C) output++;
}
}
console.log(output);
}
if (require.main === module) solve();
こんな感じになりました。
実務でも計算量を常に意識した実装を心がけたいですね。
最後に
全探索アルゴリズムは主にABCのB問題で出題されることが多いようです。
今回の問題はとても分かりやすかったので、他にも全探索問題を探して実践してみます。
AIに聞くと、他にもより数学的な解法を教えてくれますが、まずは一般的な解法で解ける問題を増やしていきます。
次回は「貪欲法」あたりを勉強しようかなと考えています。
お釣り問題・区間スケジューリングなど、 局所最適を積み重ねる 考え方を TypeScript で手を動かしながら掴みます。