ABC446 C++解法メモ(A~D)

昨日、2026/2/21(土)に開催されたABC446(AtCoder Beginner Contest 446)で解けた問題(A,B,C,D)を自分なりに整理し、図とともにC++コードを掲載します。 今回のC,D問題は素直に実装できるものでした。

atcoder.jp

A - Handmaid

文字列Sの先頭を大文字から小文字に変えて、先頭に"Of"(オーエフ)を付与する問題です。 はじめ"0f"(ゼロエフ)を付与してしまい、時間をロスしました。 大文字を小文字にするところは、公式解説ではtolower関数を使っていましたが、私は使い方を覚えていなかったため、大文字の'A'を'a'に変換するときの数字としての差を計算して加算するやり方で実装しました。tolower,toupperを覚えようと思います。

cpprefjp.github.io cpprefjp.github.io

int main() {
  string S;
  cin >> S;
  S[0] = S[0] + 'a' - 'A';
  cout << "Of" << S << endl;
}

B - Greedy Draft

N人の客がM本のジュースから好きなものを選ぶ問題です。 客はそれぞれL個の希望リストを持っていて、自分の番に残っているジュースの中から一番希望順位の高いものを選びます。希望リストに残っていなければ水を選び-1を出力する問題です。

ジュースの番号毎に選ばれたかどうかのフラグを配列で持っておいて、リストの中で最初に出てくる選ばれていないものを出力します。

以下のように実装しました。

int main() {
  int N, M;
  cin >> N >> M;
  vector<bool> Done(M, false);
  for (int i = 0; i < N; i++) {
    int L;
    cin >> L;
    bool done = false;
    for (int j = 0; j < L; j++) {
      int X;
      cin >> X;
      if (!done && !Done[X - 1]) {
        Done[X - 1] = true;
        done = true;
        cout << X << endl;
      }
    }
    if (!done) cout << 0 << endl;
  }
}

実装する際に２個バグを入れてしまい、時間をロスしてしまいました。

一つ目は、Xをfor文の中で一つずつ標準入力で取得しているのですが、選ぶものが見つかった時にbreakしてしまい、L個入力処理ができていなかったことです。

二つ目はNとMを逆にしてしまったことです。

どちらもよくやるミスなので、今後気をつけたいと思います。

C - Omelette Restaurant

卵を使うレストランで毎日以下のことをして、最後の夜に残っている卵の数を答える問題です。

• 朝：A個の卵を仕入れる
• 昼：B個の卵を使用する
• 夜：D日以上経過した卵をすべて処分する

いくつか重要な制約があります。

• 昼に卵が足りないことはなかった
• 処分するのはD日間以上たったもの、前日の朝仕入れたものは次の日の夜には1日以上たっているため、D日以上前のものは処分する

まさにFIFO(First-In, First-Out)ですね。キューで管理します。

今回私は、以下の考えで解きました。

• (a) 朝に入荷日を書いた卵のパックにその日入荷した卵を入れておく
• (b) 昼に入荷日の古いものから必要な卵を使う
• (c) 夜にD日前の卵をパック毎処分する

(a),(b),(c)の実装方法を図を用いて説明します。

(a) 朝に入荷日を書いた卵のパックにその日入荷した卵を入れておく

毎朝、入荷日と卵の個数をペアとしてキューの末尾に追加します。 図では朝の行が該当し、その日の入荷する卵を日付を記入したパックに入れて末尾に追加します。

(b) 昼に入荷日の古いものから必要な卵を使う

ここがちょっとめんどくさいところです。 昼には日付の古いものからB個使っていきます。 B個使う時に、特定の日の在庫だけで使えるのか、複数日に跨って使うのかを両方ケアする必要があります。

1日目の昼は、1日目の在庫の数(7)が使う数(1)より大きいため、在庫から1つ使い、在庫の数を１減らせばOKです。2日目の昼も同様です。

3日目の昼は、3個使いたいのですが、2日目の在庫の数(2)だけでは、足りない分を3日目の在庫(3)から1個使います。

これを一般化すると、以下のようになります。

1. 使う数Bより一番古い日の在庫が多い場合は、一番古い日の在庫からB個使用して終わり
2. そうでないなら、一番古い日の在庫をすべて使いキューを削除、Bからその個数を引いた残りの個数でもう一度1に戻る

実装では、Bがゼロになるまで、キューの先頭から処理していきます。

(c) 夜にD日前の卵をパック毎処分する

昼の処理をした後、夜になったら、卵のパックの日付を確認して、現在よりD日前までパック毎処分します。図では、2日目の夜にD日(1日)前の1日目の在庫をパック毎処分しています。

実装では、キューの先頭の要素から日付を確認し、その日付がi(現在の日付)-D以下ならキューから取り除きます。未満ではなく以下になるところが注意です。

以下が実装になります。

void test() {
  int N, D;
  cin >> N >> D;
  queue<pair<int, int>> A; // {日付, 個数}のペア
  // 先にすべてキューに入れておく
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    A.push({i, a});
  }
  for (int i = 0; i < N; i++) {
    int b;
    cin >> b;
    // 使う卵をキューの先頭からb個になるまで取得
    while (b > 0) {
      if (b < A.front().second) {
        // ある日に仕入れた卵の在庫より使う卵が少ない場合はキューは削除せずに在庫を減らす
        A.front().second -= b;
        break;
      } else {
        // ある日に仕入れた卵の在庫より使う卵が多い場合は、使う卵を在庫の分減らしてから、キューを削除
        b -= A.front().second;
        A.pop();
      }
    }
    // 賞味期限が切れたものをキューから削除
    while (!A.empty() && A.front().first <= i - D) A.pop();
  }
  long long sum = 0;
  // キューに残っているものを合計する
  while (!A.empty()) {
    sum += A.front().second;
    A.pop();
  }
  cout << sum << endl;
}

int main() {
  int T;
  cin >> T;
  for (int i = 0; i < T; i++) test();
}

公式の解説は少しだけ違う考え方で、卵のパックに日付を書くのではなく、卵自体に日付を書き、卵一つ一つをキューにしていました。こちらの方が分岐処理が少なく、バグが入りにくそうです。

公式解説を上の実装に合わせて実装したものです。

void test() {
  int N, D;
  cin >> N >> D;
  queue<int> A;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    // 日付を卵の個数だけプッシュ
    for (int j = 0; j < a; j++) A.push(i);
  }
  for (int i = 0; i < N; i++) {
    int b;
    cin >> b;
    // 使用する個数だけpop、足りないことはないのでemptyチェックはなし
    for (int j = 0; j < b; j++) A.pop();
    // 期限が過ぎたものをpop、最終日にemptyになり得るのでemptyチェック必要
    while (!A.empty() && A.front() <= i - D) A.pop();
  }
  cout << A.size() << endl;
}

ここまで言及していませんでしたが、どちらの実装でも事前にすべてキューに追加しています。これは、昼に足りないことがないという制約があるため、次の日の分を使ってしまう場合がないためそうしました。

D - Max Straight

整数列からいくつかの要素を削除し、前に詰めた新しい整数列が、１ずつ増えるようになっているものの最大の長さになるものを求める問題です。

具体例で考えます。

入力

3 4 3 5 7 6 2

からいくつか削除すると

3 4 5 6

とでき、１ずつ増えていく整数列ができます。 これの最大の長さを求める問題です。

要素を削除した後に順番を変えないことがポイントです。 1ずつ増やすということは、ある要素Aiに着目すると、その要素より以前にAi-1となるAj(0<j<i) があれば、それと連続させることができます。

Aj==Ai-1となるjは複数存在する可能性があります。すべてのjを探索するのではなく、その時点での、Ajまで連続した最大値を保持して置けばAiまでの連続数を出すことができます。 例えば3 2 3 4 5の整数列で4番目の要素の4を考えてみます。図の上のように4より前に3はふたつあり、それを両方探索すると複雑になります。必要なのは、図の下のように4が登場するより前の段階で、3は最大何個連続しているかだけになります。

これを実現するには、先頭から順番に、現時点のその要素Aiまで続く最大値を更新していけばいいです。 Ai-1が以前にあった場合は、Ai-1までの最大連続数+1とその時点のAiまでの最大値の大きい方でAiまでの最大値を保持します。

Aをキーとしてその時点のAまでの最大連続数を辞書として、Mに保持し、それを以下の更新式で更新していきます。A-1までの最大値に1を足したものとAまでの最大値の大きい方で更新することになります。C++では辞書に要素がない場合に[]でアクセスしたら既定のコンストラクタで初期化されます。A-1がMにない場合はM[A-1]は0になりますので、そのまま使えます。

M[A] = max(M[A], M[A-1] +1)

全体の実装は以下のとおりです。

int main() {
  int N;
  cin >> N;
  map<int, int> M;
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;
    M[A] = max(M[A], M[A - 1] + 1);
  }
  int max_num = 0;
  for (auto& m : M) {
    max_num = max(max_num, m.second);
  }
  cout << max_num << endl;
}