AtCoder ABC 308 - 振り返り

B - Default Price

• 色とその値段を表すマップを作成して色に対応する値段を加算していく

C - Standings

• Ai/(Ai+Bi)を求めてそれを大きい順にソートするが、成功率が同じ場合は番号の昇順なのでpairを用いた
• pairのfirstに成功率、secondに負の番号を格納することでpairの配列を降順にソートしてやればok
• 成功率をdoubleで表現すると誤差が生まれてwaとなってしまう罠
  • long doubleを用いるとこれを回避できる
• long doubleを用いても誤差はつきまとう
• 比較部分を工夫することで整数型を比較すれば良くなる
• Ai/(Ai+Bi) > Aj(Aj+Bj)をAi(Aj+Bj) > Aj(Ai+Bi)と変形させる
• ↑の比較条件で比較すればok

比較関数

// a, bを比較して大きい順に並べる
auto cmp = [&](int a, int b) -> bool {
  return A[i]*(A[j]+B[j]) > A[j]*(A[i]+B[i]);
}

vector<int> ids(N);
for (int i = 0; i < N; ++i) ids[i] = i;
stable_sort(ids.begin(), ids.end(), cmp);

Claude Codeによるまとめ

AtCoder ABC 308のB, C問題を振り返りました。

• B問題（Default Price）: マップを使った基本的な実装問題。商品の色と価格の対応をマップで管理し、各商品の価格を加算していきます

• C問題（Standings）: 成功率でのソート問題。浮動小数点の誤差を避けるため、分数の比較を整数演算に変換する工夫が必要です

  • Ai/(Ai+Bi) > Aj/(Aj+Bj) を Ai*(Aj+Bj) > Aj*(Ai+Bi) に変形
  • これにより除算を避け、整数の乗算のみで比較可能に

今回の問題では、浮動小数点演算の精度問題への対処法と、効率的なデータ構造の選択が重要なポイントでした。特にC問題では、数学的な変形により精度問題を回避する典型的なテクニックを学ぶことができました。

Created by Claude Code