【AtCoder】ABC 460 C - Sushi

2026-06-08

AtCoder/ABC/C問題 AtCoder/ABC/300点問題 AtCoder/灰Diff AtCoder/NoviSteps/3Q AtCoder/貪欲法競技プログラミング

C - Sushi

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 192 / NoviSteps: 3Q / 配点: 300 点

問題概要

寿司の材料として、 $N$ 個のシャリと $M$ 個のネタがあり、 $i$ 番目のシャリの重さは $A_i$ 、 $j$ 番目のネタの重さは $B_j$ である。

寿司を $1$ つ作るためには、 $1$ つのシャリと $1$ つのネタを組み合わせる必要があるが、ネタの重さはシャリの重さの $2$ 倍以下である必要がある。また、 $1$ つのシャリやネタを複数の寿司に使うことはできない。

作ることのできる寿司の個数の最大値を求めよ。

制約

$1 \leq N, M \leq 2 \times 10^5$
$1 \leq A_i, B_j \leq 10^9$
入力される値はすべて整数

考察

条件を満たすならば、重さの軽いシャリと重さの軽いネタから順に組み合わせていくのが最適である。

したがって、シャリとネタをそれぞれ重さの昇順にソートしてから、ネタについて重さの軽いものから順に、条件を満たすシャリを探していくいう貪欲法で解くことができる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.// ======================================== //
8. 
9.int main()
10.{
11.    int N, M;
12.    cin >> N >> M;
13.    vector<int> A(N), B(M);
14.    rep(i, 0, N) cin >> A[i];
15.    rep(i, 0, M) cin >> B[i];
16. 
17.    sort(all(A));
18.    sort(all(B));
19. 
20.    int i = 0, ans = 0;
21.    rep(j, 0, M) {
22.        while (i < N && !(B[j] <= 2 * A[i])) i++;
23. 
24.        if (i < N) {
25.            ans++;
26.            i++;
27.        }
28.        else {
29.            break;
30.        }
31.    }
32. 
33.    cout << ans << endl;
34. 
35.    return 0;
36.}

Submission #76418096 - AtCoder Beginner Contest 460

Submission #76418096 - AtCoder Beginner Contest 460

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実装時間: 10 分

コメント

そういえば最近回転寿司に行ってないような気がする。