ABC 302 振り返りメモ

A問題 - Attack

問題概要

• 体力Aの敵に対して、1回の攻撃でBのダメージを与える
• 敵を倒すのに必要な攻撃回数を求める

学習ポイント：除算の切り上げ処理

初期アプローチ

ll ans = a/b;
if (a%b!=0) ans++;

• a/bで小数点切り捨てされるため、余りがある場合は+1する必要がある
• ただし、ちょうど割り切れる場合は+1は不要

より良い実装方法

ll ans = (a+b-1)/b;

• 切り上げは(a+b-1)/bの切り捨てと同じ
• この方法だと条件分岐が不要でシンプル

補足

• 切り上げ計算のテクニックは競技プログラミングでよく使われる
• (a+b-1)/bはceil(a/b)と同じ結果になる（整数演算の場合）

---

B問題 - Find snuke

問題概要

• H×Wのグリッド上で”snuke”という文字列を探す
• 8方向（縦・横・斜め）のいずれかに並んでいる場合を見つける

アプローチ比較

自分のアプローチ

• ‘s’のマスを見つけたら、周囲に’n’があるかチェック
• 同じ線上に”uke”もあるか判定
• 枠外判定（0≤行<H、0≤列<W）も必要

模範解答のアプローチ

• 各マスを起点として、8方向全ての直線上の文字列をチェック
• それが”snuke”かどうかを判定
• よりシンプルで実装しやすい

実装のポイント

// 8方向の移動ベクトル
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

---

C問題 - Almost Equal

問題概要

• N個の文字列が与えられる
• 適切に並び替えて、隣り合う文字列の差が1文字だけになるようにできるか判定

アプローチ

• 順列全探索を使用
• 全ての並び順を試して条件を満たすものがあるかチェック

計算量

• 順列全探索の計算量：O(N!)
• Nが小さい場合（N≤8程度）なら実行可能

実装の注意点

vector<int> order(N);
iota(order.begin(), order.end(), 0);  // 0,1,2,...,N-1で初期化

do {
    // 順列に対する処理
} while (next_permutation(order.begin(), order.end()));

• next_permutationを使う時は配列を事前にソートしておく必要がある
• そうしないと全ての順列を生成できない

---

D問題 - Impartial Gift

問題概要

• 高橋君と青木君にそれぞれプレゼントを選ぶ
• 価格の差がD以下になるようにしたい
• 価格の和を最大化する

解法アプローチ

• 差分がD以下となる条件を保ちつつ、要素を減らしていく
• 貪欲法：大きい値から見ていく

実装手順

1. 両方の配列をソートする
   • 計算量：O(N log N + M log M)
2. 大きい方から順に、条件を満たすペアを探す
3. 配列の末尾へのアクセスは**O(1)**で効率的

補足：配列の特徴

• 末尾要素へのアクセス・削除：O(1)
• 先頭要素の削除：O(N)（要素のシフトが必要）
• ソート済み配列を使うことで効率的な探索が可能

---

全体的な学習ポイント

1. 数学的なテクニック

   • 切り上げ計算：(a+b-1)/b

2. 探索アルゴリズム

   • グリッド探索：8方向への移動
   • 順列全探索：next_permutationの活用

3. 計算量の意識

   • N!は急激に増加するため、Nが小さい場合のみ使用可能
   • ソートしてから処理することで効率化

4. 実装の工夫

   • 配列の特性を活かした実装
   • 境界条件の適切な処理