← 記事一覧に戻る

[AtCoder ABC 306] 振り返り

2025/8/29
AtCoder

https://atcoder.jp/contests/abc306/tasks

B - Base2

  • 問題文をそのまま実装すれば良いが、long longは-2^63 ~ 2^63-1までの範囲なので使えない
  • unsigned long longを使って答えを格納する
  • 冪乗の求め方は、forループで2を乗算していく方法もあるが、ビットシフトを用いる方が記述量少なく済む

C - Centers

  • 自分アプローチ
    • Aiをマップのkey、添字をvalueとするマップを作成
    • そのマップから添字の真ん中の値とAiの値のペアとなる配列を作成
    • ペア配列をソートして添字を出力
  • 別アプローチ
    • 数値が何回出現したかを管理する配列を用意
    • 2回目に現れたら出力用配列にpush_backすると添字の昇順に格納されるのでそのまま出力できる

D - Poisonous Full-Course

  • 動的計画法を用いて解ける
  • 料理iを食べる or 下げるした時にお腹の状態を0, 1で表した時の美味しさの総和の最大値をDP配列で管理する
  • 最初はお腹を壊していない & 美味しさは0という条件でスタートさせる
  • i番目の料理が0（解毒剤入り）か1（毒入り）かで遷移方法が変わる

Claude Codeによるまとめ

AtCoder ABC 306のB〜D問題を振り返りました。

  • B問題（Base2）: 2進数から10進数への変換問題。unsigned long long型とビットシフト演算を活用することで、大きな数値でも効率的に処理できます
  • C問題（Centers）: 配列内で各数値が2回目に出現する位置を求める問題。マップを使ったアプローチと、出現回数を管理する配列を使うアプローチの2通りの解法があります
  • D問題（Poisonous Full-Course）: 動的計画法の典型問題。お腹の状態（正常/壊れている）を状態として持ち、各料理を食べるかどうかの選択で最大の美味しさを求めます

今回のコンテストでは、データ型の範囲、効率的なデータ構造の選択、動的計画法の状態設計といった重要な概念を学ぶことができました。