2026-06-15

ABC462 C++解法メモ(D)

atcoder

先日、2026/6/13(土)に開催されたABC462(AtCoder Beginner Contest 462)のD問題を自分なりに整理し、図とともにC++コードを掲載します。

D - Accomplice

殺人事件の犯人候補から、容疑者と犯行時刻を絞り込み、組み合わせの数を考える問題です。犯行場所は館で、犯人は二人で犯行には $D$ 単位時間かかったということがわかっています。犯人二人は $D$ 単位時間の間同時に館にいる必要があります。 $N$ 人の犯人候補が館に入った時刻 $S$ と館から出た時刻 $T$ はわかっています。この条件から犯行時刻と犯人の組み合わせの数を求める問題です。

まず犯人となる候補の組み合わせを考えようとしました。 $i$ 番目の人が犯人と仮定した場合、 $S_i$ から $T_i$ の間に誰と共犯になり得るかを考えればいいのではという考えです。愚直に実装するなら $i$ 番目の人を基準に $j > i$ となる $j$ 番目の共犯者と犯行時刻 $S_i$ から $T_i$ の間で $D$ 単位時間を取れるかどうかの組み合わせとなりそうです。犯人の組み合わせを考えるだけで、 $O(N^{2})$ 、さらに時刻の組み合わせまで考えると大変なことになりそうです。

そこで考え方を変えて、犯行開始時刻を基準に考えてみました。犯行開始時刻を基準に考える場合、犯行開始時刻 $x$ は整数なので最大でも $10^{6}$ 通り以下となります。各犯行時刻に対して少ない計算量で犯人候補の組み合わせ数を求められたらOKそうです。

犯行開始時刻 $x$ で犯人になり得る人というのは、言い換えると、時刻 $x$ から時刻 $x + D$ まで館にいる人、さらに言い換えると、時刻 $x$ 以前に館に入り、時刻 $x + D$ 以降に館を出た人になります。この条件を満たす犯人候補が２人以上いたら犯行可能な時間ということになります。その時の犯人の組み合わせは、可能な人が $k$ 人いた場合 ${}_k C_2 = \frac{k(k-1)}{2}$ で計算できます。

つまり、時刻 $x$ に犯行開始できた人の組み合わせは、時刻 $x$ 以前に館に入り、時刻 $x + D$ 以降に館を出た人の人数がわかれば計算できます。

時刻ごとに人の出入りをシミュレーションすれば良いのです。

時刻 $x$ になった時に入る人がいれば追加する。ただし、時刻 $x + D$ より前に出る人はそもそも犯行不可能なので追加しない
館にいる人を数える
$x + D$ に出ていく人がいれば人数を減らす

私はこれを優先度キュー（C++ではpriority_queue）を二つの待ち行列として実装しました。

待ち行列１：まだ館に入っていない人を入る時刻で昇順にソートした待ち行列
待ち行列２：館にいる人を出る時刻で昇順ソートした待ち行列

入力例１でシミュレーションの動作を見てみます。 $N=3, D=2$ です。

まず、３人を館に入る時刻 $S$ で昇順ソートした待ち行列１を作ります。各時刻で待ち行列１の先頭の人の $S$ が時刻 $x$ と一致するかどうかを確認します。先頭の人が時刻 $x$ に館を出ない場合は先頭だけを確認すれば良いので、 $O(1)$ で確認することができます。最初の人が館に入るのは時刻9なので、時刻８までこの状態が続きます。

時刻9の時点で初めて先頭の人が館に入ることになります。そこで待ち行列１から先頭の人を取り出します。 $O(\log N)$ 。その人を館の中に入れ、出る時刻を基準とした待ち行列２に追加します。この時点で時刻9から時刻11(=9+2)まで館の中にいる人は一人なので、犯行は不可能です。

次に時刻10の時点を考えます。待ち行列１にS＝10の人がいるため館の中に入ります。この人は出る時刻は12(10+2)以降なので、一旦館の中に入れます。この人は出る時刻が12で元々いる人より早いため待ち行列２の先頭に挿入します。 $O(\log N)$ 。この時点で時刻10から時刻12(=10+2)の間にいた人は２人になるので、犯行が可能となり、組み合わせの合計を一つ増やします。

組み合わせを増やした後に $x + D$ に館を出た人を館から出します。つまり、12(=10+2)に出た人として、入ったばかりですが、先頭の人を館から出します。ここでの実装は待ち行列２の先頭の人の出る時刻が $x + D$ に一致するかどうかを確認します。 $O(1)$ 。これで時刻10の処理は完了です。

次に時刻13では待ち行列１の先頭の人の $S$ が13で、かつ出る時刻 $T$ が15(=13+2)より大きいので館の中に入れます。この人は出る時刻 $T$ が元いる人より大きいため、待ち行列２の最後尾に入れます。この時点で時刻13から15の間にいた人は２人なので、犯行可能な組み合わせを１増やします。同様に時刻14,15もその時刻から+2した時刻までは館内に2人いたことになるので、それぞれ犯行可能な組み合わせを1増やし、合計4になります。

時刻15で犯行可能な組み合わせを数えたのちに、時刻17(=15+2)で館を出る人がいるため、待ち行列２から先頭の人を館の外に出します。以降は、館の中には１人以下しかいないため、これ以上犯行可能な組み合わせはありません。

以上のシミュレーションで、犯行可能な組み合わせは４と求まりました。この入力例では館の中に同時に２人までしかいませんでしたが、館の中に $k$ 人いた場合は ${}_k C_2$ で組み合わせを増やすようにすれば、一般化できます。

それぞれの処理の計算量は大きく見積もって以下になります。

待ち行列１を作成 $O(N\log N)$
各時刻で待ち行列１の先頭の人の入る時間を確認 $O(10^{6})$
各時刻で待ち行列１から先頭の人を取り出す $O(N\log N)$
各時刻で待ち行列２に追加 $O(N\log N)$
各時刻で待ち行列２の先頭の人の出る時間を確認 $O(10^{6})$
各時刻で待ち行列２から先頭の人を取り出す $O(N\log N)$
各時刻で人数を数え、組み合わせを計算 $O(10^{6})$

最大でも $O(10^{6} + N\log N)$ ( $N \le 2 \times 10^{5}$ )なので十分間に合います。

以下が実装です。

using ll = long long;

int main() {
  int N, D;
  cin >> N >> D;
  // 館に入る待ち行列
  priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>> Q1;
  for (int i = 0; i < N; i++) {
    int S, T;
    cin >> S >> T;
    Q1.push({S, T});
  }
  // 館から出る待ち行列
  priority_queue<int, vector<int>, greater<int>> Q2;
  ll count = 0;
  for (int x = 0; x <= 1000000; x++) {
    // その時刻に館に入る人を館に入れる
    while (!Q1.empty() && Q1.top().first == x) {
      if (Q1.top().second >= x + D) Q2.push(Q1.top().second);
      Q1.pop();
    }
    // 犯行可能な組み合わせを数えて加算
    if (Q2.size() >= 2) {
      ll n = Q2.size();
      count += n * (n - 1) / 2;
    }
    // 組み合わせを数えてからx+Dに館から出る人を館から出す
    while (!Q2.empty() && Q2.top() == x + D) {
      Q2.pop();
    }
  }
  cout << count << endl;
}

2026-03-01

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

atcoder

昨日、2026/2/28(土)に開催されたABC447(AtCoder Beginner Contest 447)で解けた問題(A,B,C,D)を自分なりに整理し、図とともにC++コードを掲載します。 C,Dは公式とは違う解法です。

atcoder.jp

A - Seats 2

N席の座席にM人が隣あわずに座れるかの問題です。A問題にしては難しかったです。 M人が隣あわずに座れる最小の座席数を考えます。具体例として３人で考えてみます。oを座る位置、xを空席とすると、以下のように端に座り、かつ間が一席ずつの場合が最小となります。

oxoxo

これをM人で考えると、M人分の座席とM-1個の空席が必要になるため、合計は2M-1席になります。Nが2M-1以上であれば座れることになります。そのまま実装します。

int main() {
  int N, M;
  cin >> N >> M;
  if (N >= 2 * M - 1)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

B - mpp

英小文字で構成される文字列Sから一番出現頻度が多い文字を削除した文字列を出力する問題です。 Sに含まれる26種の英小文字の数を数えて最大個数のものを除外した文字列を作ります。最大個数となる文字種が複数ある場合はすべて削除する必要があります。そこで、最大個数となる文字種を判定するのではなく、最大個数を覚えておき、文字列を再構成する際に、最大個数となるものは連結しないことで実現します。

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

int main() {
  string S;
  cin >> S;
  vector<int> C(26, 0);
  for (auto& s : S) C[s - 'a']++;
  int max_n = 0;
  for (auto& c : C) max_n = max(max_n, c);
  string SS;
  for (auto& s : S) {
    if (C[s - 'a'] != max_n) SS += s;
  }
  cout << SS << endl;
}

C - Insert and Erase A

二つの文字列S,Tが与えられ、Sに対して'A'を削除または追加してTに一致させる場合の、削除と追加の合計回数の最小値を求める問題です。編集距離に近いのですが、'A'しか編集できないため簡単になります。

まず、'A'以外は削除、追加、入れ替えが発生しないため、'A'を無視して左から順にSからTに対応付けしていけばよいです。この時点でマッチングできなければTに変換できないことになります。

次に、先ほどマッチングした'A'以外の文字の間に存在する'A'同士も左から順にマッチングしていきます。

そうすると、S,Tそれぞれに、マッチングされなかった'A'が残ります。Sに残った'A'は削除対象で、Tに残った'A'は追加対象になります。この削除対象と追加対象の数の合計が操作数の最小値になります。

これを実現するためには、S,Tそれぞれを操作するインデックスi,jを用意、それぞれ0からスタートし、以下の処理をS,Tのどちらとも最後の文字まで進めます。また、操作回数を数えるcountを0で初期化しておきます。

S[i]とS[j]が一致していたら削除も追加もしなくていいので、マッチングしたとして、i,jを1進める(図中緑)
一致しなかった場合は以下のいずれかの処理
- S[i]が'A'ならS側に'A'が余分にあるのでSのインデックスiだけを１進める、同時に操作回数countを1増加(図中青)
- T[j]が'A'ならT側に'A'が余分にある(Sに'A'が足りない)のでTのインデックスjだけを１進める、同時に操作回数countを1増加(図中赤)
- S[i]もT[j]も'A'以外の場合は、マッチングできていないのでSからTに変換できないとして終了

以下の通りに実装しました。コンテスト中は意識していなかったのですが、上図の終端の点線四角部分はC++では終端文字'\0'が格納されており、読み取ってT[i]==T[j]の判定をすることはOKでした。意識していなかったのでちょっと危険でした。

int main() {
  string S, T;
  cin >> S >> T;
  int count = 0;
  int i = 0, j = 0;
  while (i < S.size() || j < T.size()) {
    if (S[i] == T[j]) {
      i++;
      j++;
    } else if (i < S.size() && S[i] == 'A') {
      count++;
      i++;
    } else if (j < T.size() && T[j] == 'A') {
      count++;
      j++;
    } else {
      count = -1;
      break;
    }
  }
  cout << count << endl;
}

D - Max Straight

'A','B','C'のみから構成される文字列Sの中で、ABCという順番で最大何個の組み合わせを作れるかという問題です。

以下の考え方で左から順に組み合わせを作り数を数えればOKです。 - Aはできるだけ左から取ってくる - Bは上のAより右側で一番左側を取ってくる - Cは上のBより右側で一番左側を取ってくる

以下の通り実装します。

'A','B','C'の位置をそれぞれ昇順にリストに格納
以下を満たすABCの位置を見つける
- 残っている'A'一番左の位置を取得
- 残っている'B'の位置で上の'A'の位置より右側で一番左の位置を取得
- 残っている'C'の位置で上の'B'の位置より右側で一番左の位置を取得
ABCの組み合わせが見つかったらカウンタを１増やす
次の'A'の位置で同様のことをする

C問題と似たような実装になりました。

int main() {
  string S;
  cin >> S;
  vector<int> A, B, C;
  for (int i = 0; i < S.size(); i++) {
    auto s = S[i];
    if (s == 'A') A.push_back(i);
    if (s == 'B') B.push_back(i);
    if (s == 'C') C.push_back(i);
  }
  int a = 0, b = 0, c = 0;
  int count = 0;
  while (a < A.size() && b < B.size() && c < C.size()) {
    if (B[b] < A[a])
      b++;
    else if (C[c] < B[b])
      c++;
    else {
      a++;
      b++;
      c++;
      count++;
    }
  }
  cout << count << endl;
  return 0;
}

2026-02-22

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

atcoder

昨日、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個使います。

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

使う数Bより一番古い日の在庫が多い場合は、一番古い日の在庫からB個使用して終わり
そうでないなら、一番古い日の在庫をすべて使いキューを削除、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;
}

2026-02-15

ABC445解法メモ

atcoder

昨日、2026/2/14(土)に開催されたABC445(AtCoder Beginner Contest 445)で解けた問題(A,B,D)を自分なりに整理し、C++コードを掲載します。多くの人がそうだったように私もC問題を誤読して時間をかけても解けませんでした。 D問題は公式解説より効率が悪いですが、なんとかACできました。

atcoder.jp

A - Strong Word

二文字以上の文字列が与えられ、先頭の文字と末尾の文字が同じか判定する問題です。二文字以上なので、例外など気にせずにそのまま0番目とsize-1番目を比較しました。実装は以下の通りです。

int main() {
  string S;
  cin >> S;
  if (S[0] == S[S.size() - 1])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

B - Center Alignment

奇数文字数の文字列がN個与えられ、その最大の長さのものに合わせて、足りないところは前後を同じ数の"."で埋めて出力する問題です。問題文を読んでもよくわからなかったのですが、サンプルを見てわかりました。

以下の処理を実装しました。

一番長い文字数を見つけてmax_sとする
各文字列で(max_s-size)/2の長さの"."を前後に付けて出力する

文字列がすべて奇数文字数なのでmax_s-sizeは必ず偶数になり、前後に同じ数の"."を付与することでmax_sサイズになります。

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  int max_s = 0;
  for (auto& s : S) {
    cin >> s;
    if (max_s < s.size()) max_s = s.size();
  }
  for (auto& s : S) {
    int k = (max_s - s.size()) / 2;
    string dot = "";
    for (int i = 0; i < k; i++) dot += ".";
    cout << dot << s << dot << endl;
  }
}

D - Reconstruct Chocolate

縦Hブロック、横Wブロックの板チョコを分割してできたN個のピースを並び替えて、元の大きさに復元する問題です。分割の仕方として、ブロックの境界で分割し長方形の二つに分割すること、分割した片方はそれ以上分割しないことが条件です。

新・解きたくなる数学の問13チョコレートの分割をやっていて、チョコレートを割るということがイメージできていたので、方針はすぐに立てられました。

www.iwanami.co.jp

分割済みのピースを並び替えようとすると、パターンが非常に多くなり、考えるのが難しくなります。そこで、元の縦H横Wブロックをどう分割したら今のN個にできるかをシミュレーションすることにしました。

縦H'横W'ブロックのチョコレートを分割するときは以下の性質があります。

縦に分割する場合は分割後のブロックはどちらも横はW'ブロックのまま
横に分割する場合は分割後のブロックはどちらも縦はH'ブロックのまま

つまり、縦H'横W'ブロックのチョコレートを分割し、それ以上分割しなかったチョコレートは、横W'ブロックのピースまたは、縦H'ブロックのピースのうちのいずれかになります。

ある縦H'横W'ブロックの時点で次に分割するピースの候補は、残っているピースのうち以下のいずれかになります。

縦がH'ブロックのピースがあれば、それが分割したもの
横がW'ブロックのピースがあれば、それが分割したもの

これを縦H横Wブロックから始めて、分割してできたピースを見つけては、現時点の左上に配置していくということを繰り返していけばすべてを埋めることができます。分割してできたピースは残っているピースのうちから、特定のH',W'を持つピースを探す必要があります。毎回探すと、O(N²)程度になり、間に合わなささそうです。そこで、縦の大きさごと、横の大きさごとに辞書で管理してO(logN)で探せるようにします。

処理の流れを入力例１を用いて図で説明します。

まずはじめに、各ピースを縦サイズごと、横サイズごとに辞書にピース番号を保持します。

次に、元の縦H横Wブロック（4x6）を分割してできるピースを探します。縦が4もしくは、横が6のブロックを先ほどの辞書から探すと、縦4の6番目のピースが該当するので、それを左上に配置し分割したことにします。

分割したらWが2減り、4x4になります。同じように4x4を分割できる、縦4または横4のピースを一つ選びます。ここではピース2を選びます。ということを順に実施していき、HまたはWが0になるまで続けます。

そして最後にピース１から順に配置した場所の左上の位置を出力します。

実装は以下の通りです。

int main() {
  int H, W, N;
  cin >> H >> W >> N;
  vector<pair<int, int>> HW(N);
  map<int, queue<int>> Hmap; // 縦hのピースの番号のリスト
  map<int, queue<int>> Wmap; // 横wのピースの番号のリスト
  for (int i = 0; i < N; i++) {
    int h, w;
    cin >> h >> w;
    Hmap[h].push(i);
    Wmap[w].push(i);
    HW[i] = {h, w};
  }
  vector<pair<int, int>> P(N, {0, 0}); // 各ピースの左上の位置、まだ決まっていない時は(0,0)
  int x = 1, y = 1;
  while (W > 0 && H > 0) {
    // 現在のHと同じhを持つかけらが残っている場合は、それを採用
    if (Hmap.contains(H)) {
      auto& hq = Hmap[H];
      // 処理済みのものをスキップする
      while (!hq.empty() && P[hq.front()].first != 0) hq.pop();
      if (!hq.empty()) {
        int index = hq.front();
        hq.pop();
        auto hw = HW[index];
        // 現時点の位置の左上に埋める
        P[index] = {x, y};
        // 埋めた分のyを進め、Wを小さくする
        y += hw.second;
        W -= hw.second;
      }
      // すべて処理済みならそのHを削除する
      if (hq.empty()) Hmap.erase(H);
    }
    // 現在のWと同じwを持つかけらが残っている場合は、それを採用
    if (Wmap.contains(W)) {
      auto& wq = Wmap[W];
      // 処理済みのものをスキップする
      while (!wq.empty() && P[wq.front()].first != 0) wq.pop();
      if (!wq.empty()) {
        int index = wq.front();
        wq.pop();
        auto hw = HW[index];
        // 現時点の位置の左上に埋める
        P[index] = {x, y};
        // 埋めた分のxを進め、Hを小さくする
        x += hw.first;
        H -= hw.first;
      }
      // すべて処理済みならそのWを削除する
      if (wq.empty()) Wmap.erase(W);
    }
  }
  for (int i = 0; i < N; i++) cout << P[i].first << " " << P[i].second << "\n";
  return 0;
}

公式の解説では、辞書で持つのではなく、H,Wそれぞれで降順ソートして大きいものから配置していました。H,Wと等しいだけではなく、残っているもので一番大きいものを選ぶということに気づくことができませんでしたが、なんとか処理時間は間に合いました。

2026-02-08

ABC444解法メモ

atcoder

昨日、2026/2/7(土)に開催されたABC444(AtCoder Beginner Contest 444)で解けた問題(A,B,C)を自分なりに整理し、C++コードを掲載します。

atcoder.jp

A - Repdigit

与えられた３桁の正整数がゾロ目かどうかを判定する問題です。3桁であることが保証されているので簡単です。入力値を文字列として3文字が一致するかで判定しました。

int main() {
  string S;
  cin >> S;
  if (S[0] == S[1] && S[1] == S[2])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

B - Digit Sum

N以下の整数の各桁の和がKになるものの個数を求める問題です。 1〜Nまで順番にすべての整数で、各桁の合計を計算し、Kと一致する者の数を数えればOKです。整数を10で割った余りが一番下の桁の値なので、10で割って桁をずらしながら各桁の数値を取得します。以下のように実装しました。

int main() {
  int N, K;
  cin >> N >> K;
  int sum = 0;
  for (int i = 1; i <= N; i++) {
    int n = i;
    int k = 0;
    while (n > 0) {
      k += n % 10;
      n /= 10;
    }
    if (k == K) sum++;
  }
  cout << sum << endl;
}

C - AtCoder Riko

"AtCoderりこ"という言葉のせいで理解に時間がかかりました。棒として整理します。

長さLの棒が何本かあり、そのうち何本かを２分割した、という状態が正整数列Aです。２分割しなかったものもあるようです。正整数列Aが与えられたときに元の棒の長さLとして取りうる値を昇順に出力するという問題です。

以下のふた通りで考えます。

すべて２分割した場合
２分割されなかった棒がある場合

まず１を考えます。すべて２分割したということは、分割後の棒の数は必ず偶数になります。その上で、各棒は別のどれかとペアになり、その長さの合計がすべてのペアで同じになります。

元の長さLの棒を２分割した時に片方が短くなるともう片方は長くなります。そのため、整数列Aでペアを作る場合、一番短い棒と一番長い棒、2番目に短い棒と2番目に長い棒・・・というようにペアとなります。棒の長さでソートして両端からペアを作っていけば良いです。すべてのペアで合計が同じになれば、それが元の長さLになります。合計が同じにならないのであれば、このパターンでの長さLは存在しません。

次に２を考えます。２分割されなかった棒がある場合、その棒の長さは分割した他のすべての棒より必ず長くなります。分割した棒は元の棒より短くなるためです。つまり、正整数列Aのうち一番大きい値がLとなり得ます。一番長い棒以外は２分割されたものなので、１の考えですべてペアになるかを確認します。その際に各ペアの長さの合計が分割されなかった一番長い棒の長さLと一致する必要があります。

この１、２でLが見つかったものを昇順にソートして出力します。この考え方では、Lは一つまたは二つ見つかることになります。

実装は以下の通りです。

int main() {
  using ll = long long;
  ll N;
  cin >> N;
  vector<ll> A(N);
  for (auto& a : A) cin >> a;
  sort(A.begin(), A.end());
  bool L1ok = true;
  vector<ll> L;
  if (N % 2 == 0) {
    ll L1 = A.front() + A.back();
    for (int i = 0; i < N / 2; i++) {
      L1ok &= A[i] + A[N - 1 - i] == L1;
    }
    if (L1ok) L.push_back(L1);
  }
  ll L2 = A.back();
  int end = -1;
  for (int i = N - 1; i >= 0; i--) {
    if (A[i] != L2) {
      end = i;
      break;
    }
  }
  if (end % 2) {
    bool L2ok = true;
    for (int i = 0; i < end / 2; i++) {
      L2ok &= A[i] + A[end - i] == L2;
    }
    if (L2ok) L.push_back(L2);
  }
  if (L.size() == 2) sort(L.begin(), L.end());
  for (auto& l : L) cout << l << " ";
  cout << endl;
}

2026-02-02

ABC443解法メモ

atcoder

先日、2026/1/31(土)に開催されたABC443(AtCoder Beginner Contest 443)で解けた問題(A,B,C,D)を自分なりに整理し、C++コードを掲載します。今回はB問題とD問題に悩みましたので、その試行錯誤を中心に記載します。どの問題もサンプルがコーナーケースを網羅してくれている優しい例だったためWAとならずに済みました。

atcoder.jp

A - Append s

与えられた文字列の末尾に"s"を追加する問題で、そのまま実装するだけです。最近のA問題の中では簡単な方だと思います。

int main() {
  string S;
  cin >> S;
  cout << S << "s" << endl;
}

B - Setsubun

季節にちなんだ問題です。今年N歳の高橋くんが毎年歳の数だけ豆を食べ、合計がKを超えるのは何年後かを出力する問題です。 x年後に食べる豆の数は以下で計算できます。

$N + (N+1) + (N+2) + (N+3) + ... + (N+x)$

等差数列の和なので、公式を調べて、Kを超えるxを求めれば一発で出せる！と思ったのですが、和の公式を調べて、不等式を立てた時点で、２次不等式になって、あれ、めんどくさい、となりました。ここで5分くらいロスしてしまったのですが、方針を変えて、素直にループで足していくことにしました。 i年後にN+iを食べてというのを合計がKを超えるまで繰り返します。 N=1,K=10⁸の時が最悪ケースになり、10⁸年後には10⁸+1個の豆を食べるので、Kを超えるため、計算量は多く見積もってO(10⁸)に収まります。

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

int main() {
  long long N, K;
  cin >> N >> K;
  long long sum = 0;
  for (int i = 0; i < 100000000; i++) {
    sum += N + i;
    if (sum >= K) {
      cout << i << endl;
      break;
    }
  }
}

コンテスト終了後に最初の方針の等差数列の和＋2次不等式という高校生でも解けるやり方で実装してみました。

まず、x年後の食べた合計を等差数列の和の公式で数式化します。

$\displaystyle\sum^{x}_{i=0}(N+i) = \displaystyle\frac{(x+1)(N+N+x)}{2}$

これがKを超えることを不等式で表現します。

$\displaystyle\frac{(x+1)(N+N+x)}{2} \ge K$

変形していきます。ここら辺からだんだん嫌な予感が・・・

$\displaystyle\frac{(x+1)(N+N+x)}{2} \ge K$

$\displaystyle\frac{(x+1)(N+N+x)}{2} - K \ge 0$

$(x+1)(N+N+x) - 2K \ge 0$

$x^{2} + (2N+1)x +2N - 2K \ge 0$

2次不等式なので、 $x^{2} + (2N+1)x +2N - 2K = 0$ となる $x$ を求め、不等号で表現します。解の公式を~~思い出して~~検索してして解いてみます。

$x = \displaystyle\frac{-2N-1\pm\sqrt{(2N+1)^{2}-4(2N-2K)}}{2}$ $= \displaystyle\frac{-2N-1\pm\sqrt{4N^{2}-4N+8K+1}}{2}$

2次不等式の $x^{2}$ の係数が正のため下に凸の放物線かつ $x>0$ のため、以下を満たす最小の整数を求めればよいです。

$x \ge \displaystyle\frac{-2N-1+\sqrt{4N^{2}-4N+8K+1}}{2} \space and \space x \ge 0$

実装は以下の通りです。一発で解けるので、計算時間は短いはずですが、式に間違えが入りやすいため、コンテスト本番ではやらなくてよかったです。

int main() {
  long long N, K;
  cin >> N >> K;
  long double x =
      (-2 * N - 1 + sqrtl((long double)(4 * N * N - 4 * N + 8 * K + 1))) / 2;
  cout << max(0, (int)ceil(x)) << endl;
}

C - Chokutter Addiction

Chokutter廃人の高橋くんがChokutterを開いている時間を求める問題です。開いているときに青木くんが来たらChokutterを閉じて、閉じてから時間が100経過したらChokutterを開くという問題です。

サンプルを図示してみました。開いている期間を水色、閉じている期間を赤で色をつけています。

図から以下がわかります。

時刻0から始めて青木くんが来る時間 $A_1$ までは開いている
時刻 $A_1$ に閉じる
時刻 $A_1+100$ に開く
時刻 $A_1 \le t \le A_1+100$ の間に青木くんが来ても何も起こらない

最後の項目を考えると、何も起こらない青木くんの到来を無視すると考えやすくなりそうです。

何も起こらない青木くんの到来を無視して、閉じるべき時だけを残して新しく $A_i$ として、 $A_i$ から $A_{i+1}$ の間に開いている時間を考えます。開いているのは $A_{i}+100$ から $A_{i+1}$ の間なので、 $A_{i+1}-(A_{i}+100)$ が開いている時間になります。これに、時刻 $0$ から時刻 $A_{1}$ までと、最後の青木くんの到来から時刻 $T$ までも加えることで求めることができます。

実装は以下の通りです。

int main() {
  using ll = long long;
  ll N, T;
  cin >> N >> T;
  if (N == 0) {
    cout << T << endl;
    return 0;
  }
  vector<ll> A;
  ll prev = -100;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    if (a - prev <= 100) continue;
    prev = a;
    A.push_back(a);
  }
  // 初めて青木くんが来るまで
  ll sum = A[0];
  for (int i = 1; i < A.size(); i++) {
    sum += A[i] - A[i - 1] - 100;
  }
  // 最後の青木くん到来から時刻Tまで
  sum += max<ll>(0, T - A[A.size() - 1] - 100);
  cout << sum << endl;
}

D - Pawn Line

NxNマスの各列に一つ駒があり、その駒は上にのみ１マスずつ動かせるという条件です。元の駒の状態から何回か動かして、隣の列のコマとの行の差が１以内になるには、最低何回動かすかという問題です。

入力例を図示してみます。はじめに駒があった位置にoを置き、条件を満たすように動かす位置を矢印で表現しています。

これを実現するアルゴリズムを考えます。

【案１】左から順に処理

左右の隣のコマよりも下にあったら上に動かすというのが基本的な考え方です。まず考えたのが、左の列から順に処理するという考えです。下図左のように列１から順に左右が自分より上にあればそこの一つ下まで移動するということをやっていけば最小回数が求められます。しかし、下図右のように列５から逆順に処理をすると列５を動かした後に列４が動くことになり、十分に動かすことができません。逆順でできないということは、逆順のパターンが入力されたらできないということなのでこのやり方はNGです。

これは、後から隣の駒が動くことが原因です。そこで、移動先の目標とした隣の駒が後から動かないようにします。その時点で位置が確定しているものを移動先の目標にします。駒は上にしか動けないため、一番上にある駒はこれ以上動かしたら他の駒から遠ざかってしまいます。つまり、一番上にある駒は動かす必要がないということです。

【案2】上から順に処理

以下の図のように考えました。駒の中で一番上の行にある駒からスタートし、その左右の駒を自分の一つ下まで持ってきます(a)。同じ行に他の駒があれば同様に左右を持ってくる処理をします。同じ行の駒がなくなったら次の行の駒を順に処理します(b,c)。こうすることで、各駒は左右両隣のうち、最終的に一番上にある駒に引き上げられます。案１と違って、上にある駒はもう位置が確定しているかつ、上の行から順に処理をしているため、各駒は一度しか引き上げられません。アルゴリズムとしてはこれで良さそうです。

で、ここからが実装ですが、実装に悩みました。NxNのマスすべての状態を覚えておくのは計算量的に間に合わないと思われるので、以下の方針で駒がある位置を管理します。

各列毎に現時点で駒がある位置を配列で保持
各行毎に現時点で駒がある列を集合で保持

1.は各列には駒は一つしかないので列サイズの配列を用意して行番号を保持するだけでいいです。駒を移動した時の移動も簡単にできます。

2.は各行には駒が複数列に含まれる可能性があるため、行毎に複数のデータを保持するデータ構造が必要です。また、駒を入れ替えるため、データの挿入・削除が比較的高速にできる必要があります。ということで、実装ではunordered_setを用いました。

以下の処理を実装しました。

上から順にすべての行を確認していく
- その行にある駒の列番号を取得する
- すべての列番号に対して以下を実行
  - 左右が自分より下にある場合は自分より一つ下まで引き上げ、移動量を加算する

void test() {
  int N;
  cin >> N;
  vector<int> R(N); // 列毎に駒がある行番号を管理
  vector<unordered_set<int>> Rows(N); // 行毎にどの列に駒があるかを管理
  for (int i = 0; i < N; i++) {
    int r;
    cin >> r;
    R[i] = r - 1;
    Rows[r - 1].insert(i);
  }
  long long sum = 0;
  // 上から順にすべての行で実行
  for (int i = 0; i < N; i++) {
    // その行にある駒の列番号を取得
    auto cols = Rows[i];
    // 列毎に左右の駒の行を確認し、自分より下にあるなら上に持ってくる
    // 移動した場合は移動料を加算する
    for (auto& c : cols) {
      int left = max(0, c - 1);
      if (R[left] > i + 1) {
        sum += R[left] - i - 1;
        Rows[R[left]].erase(left);
        R[left] = i + 1;
        Rows[R[left]].insert(left);
      }
      int right = min(N - 1, c + 1);
      if (R[right] > i + 1) {
        sum += R[right] - i - 1;
        Rows[R[right]].erase(right);
        R[right] = i + 1;
        Rows[R[right]].insert(right);
      }
    }
  }
  cout << sum << endl;
}

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

後から調べると、priority_queueを用いている人が結構いました。私の場合は上から並び替えるところを自前で実装していることと、すべての行を見ないといけないということで、今回の制約では大丈夫でしたが、制約が厳しくなるとTLEになる可能性があります。priority_queueも勉強したいと思います。

2026-01-25

ABC442解法メモ

atcoder

昨日、2026/1/24(土)に開催されたABC442(AtCoder Beginner Contest 442)で解けた問題(A,B,C,D)を自分なりに整理し、C++コードを掲載します。今回は引っ掛け要素がなく、迷わずに実装することができました。

atcoder.jp

A - Count .

文字列に含まれるjとiを数える問題です。そのまま数えます。

int main() {
  string S;
  cin >> S;
  int sum = 0;
  for (auto& c : S) {
    if (c == 'j' || c == 'i') sum++;
  }
  cout << sum << endl;
  return 0;
}

B - Music Player

音楽プレイヤーがあり、クエリによって音量を上げ下げ、再生・停止を切り替えて、現在再生中かを判定する問題です。音量と再生状態を保持して順番に処理していけば引っかかるところなく実装できました。

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

int main() {
  int Q;
  cin >> Q;
  int volume = 0;
  bool play = false;
  for (int i = 0; i < Q; i++) {
    int A;
    cin >> A;
    if (A == 1) {
      volume++;
    } else if (A == 2) {
      volume = max(0, volume - 1);
    } else {
      play = !play;
    }
    if (volume >= 3 && play)
      cout << "Yes" << "\n";
    else
      cout << "No" << "\n";
  }
  return 0;
}

C - Peer Review

N人の研究者がいて、Mペアの利害関係がある場合に、各研究者に対して利害関係がない人のうち三人にレビューしてもらい、その組み合わせを出力する問題です。

まずは理解するために図を書いてみました。縦軸を自分、横軸を相手として利害関係があるものをo, 自分自身をxとして表にしています。

この表を作り、横方向にoもxもついていない人が、査読者の候補になりそうです。

1行目を見ると、oもxもついていないのは5,6の2人なので3人の査読者は確保できません。 2行目は4,5,6の3人が査読者の候補になります。3人必要なので組み合わせとしては全員が査読者となるしかなく１通りです。 6行目を見ると利害関係者はなく、査読者の候補は5人います。5人のうち3人を選ぶには組み合わせとして5C3=(5x4x3)/(3x2x1)で計算できます。

ここまでの考え方を一般化してまとめると、以下になります。

i番目の研究者に対する査読者の候補は、研究者の合計Nから利害関係者数と自分を引いた数(kとする)
査読者の組み合わせは、kが3未満なら0、3以上ならkC3

これを実装すればよいです。しかし、ここでデータ数Nの制約を見ると1≤N≤2×10⁵で、上記の表を作成しようとするとN²のメモリが必要になり、メモリの上限を超えそうです。また、表を作ってから人数を数えると、計算量としてもO(N²)となり間に合いません。

もう一度上の考えを見直すと、必要なの"研究者毎の利害関係者の人数だけ"で"誰と誰が利害関係があるか"は必要がないことがわかりました。

そこで、研究者毎に利害関係者を数えるカウンタを用意して、クエリ毎に利害関係者両方の数を1増やせばよいことになります。

でもちょっと待ってください。クエリ毎に利害関係者数を足していくと、クエリに同じ組み合わせの利害関係者があると、2回カウントしてしまい、計算が合わなくなる可能性があります。念のため制約を確認すると、違うクエリでは同じ組み合わせは現れないと明記してありました。

自信を持って以下のように実装しました。

vectorで利害関係者の数を数えるカウンタを用意し、クエリ毎にA,B両方のカウンタを加算
すべてのiで査読者の人数を計算し、組み合わせ数を計算

一点注意が必要なのは、計算のオーバーフローです。最大でNx(N-1)x(N-2)を計算するところがあるのですが、これはintの範囲を超えてしまいます。そこで、値を乗算する前にlong longで保持し、long longで計算するように工夫しました。後からintにして提出してみたら、案の定WAとなりました。

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> I(N + 1, 0);
  for (int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B;
    I[A]++;
    I[B]++;
  }
  for (int i = 1; i <= N; i++) {
    long long n = N - I[i] - 1;
    cout << n * (n - 1) * (n - 2) / 6 << " ";
  }
  return 0;
}

D - Swap and Range Sum

数列Aがあり、クエリ毎に操作する問題です。

1 x:AxとAx+1を入れ替える
2 l r:Al~Arまでの合計を出力する

まず、2つ目のパターンを考えます。区間が毎回違って区間の数列の和を計算することになるので、累積和を使えばO(1)で計算できます。累積和を使う前提で1つ目のクエリをどう操作するかを考えます。

AxとAx+1を入れ替えた時、累積和を作り直すことができればOKです。 AxとAx+1を入れ替えた時に累積和がどう変化するかを考えます。

上の図を見ながら考えると、以下のように累積和の変化がまとめられます。

Ax-1までは全く変化しないため、Ax-1までの累積和は変化なし
AxとAx+1を入れ替えても、Ax+1までの累積和にしてみたら、順番が変わるだけでどちらも合計は変化なし
Ax+2以降も同様に変化なし
Axまでの累積和はx番目の値が変わるため変化する。交換することで累積和はAx減少し、Ax+1増加する。

つまり、現時点のAxとAx+1が必要になります。数列Aを都度Swapすることで、現時点のAx,Ax+1を取得できるのですが、今回は違う実装にしてみました。累積和がわかれば累積和の差分からAx,Ax+1を取得することができます。

以下が実装です。

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<int> A(N);
  for (auto& a : A) cin >> a;
  vector<long long> AS(N + 1, 0);
  for (int i = 0; i < N; i++)
    AS[i + 1] = A[i] + AS[i];
  for (int i = 0; i < Q; i++) {
    int n;
    cin >> n;
    if (n == 1) {
      int x;
      cin >> x;
      auto Ax = AS[x] - AS[x - 1];
      auto Ax1 = AS[x + 1] - AS[x];
      AS[x] = AS[x] - Ax + Ax1;
    } else {
      int l, r;
      cin >> l >> r;
      cout << AS[r] - AS[l - 1] << "\n";
    }
  }
  return 0;
}

tAROの試行錯誤

技術的なことを色々試した過程を記録

ABC462 C++解法メモ(D)

D - Accomplice

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

A - Seats 2

B - mpp

C - Insert and Erase A

D - Max Straight

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

A - Handmaid

B - Greedy Draft

C - Omelette Restaurant

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

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

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

D - Max Straight

ABC445解法メモ

A - Strong Word

B - Center Alignment

D - Reconstruct Chocolate

ABC444解法メモ

A - Repdigit

B - Digit Sum

C - AtCoder Riko

ABC443解法メモ

A - Append s

B - Setsubun

C - Chokutter Addiction

D - Pawn Line

【案１】左から順に処理

【案2】上から順に処理

ABC442解法メモ

A - Count .

B - Music Player

C - Peer Review

D - Swap and Range Sum