【AtCoder】ABC 431 C - Robot Factory

C - Robot Factory

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

AtCoder

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

問題概要

高橋くんは、頭パーツを $1$ 個と体パーツを $1$ 個組み合わせてロボットを $1$ 体作ることができる。 しかし、ロボットは頭パーツの重さが体パーツの重さより大きいと倒れてしまう。

現在、高橋くんは頭パーツを $N$ 個と体パーツを $M$ 個持っていて、 $i$ 番目の頭パーツの重さは $H_i$ グラム、$i$ 番目の体パーツの重さは $B_i$ グラムである。

高橋くんは、持っているパーツを適切に組み合わせることで、倒れないロボットを合計 $K$ 体作りたい。 この目標を達成することができるか判定せよ。

制約

• $1\le N\le2\times10 ^ 5$
• $1\le M\le2\times10 ^ 5$
• $1\le K\le\min\lbrace N,M\rbrace$
• $1\le H _ i\le10 ^ 9\ (1\le i\le N)$
• $1\le B _ i\le10 ^ 9\ (1\le i\le M)$
• 入力はすべて整数

考察

直感的に、頭のパーツは軽い方から、体のパーツは重い方から順にそれぞれ $K$ 個を選び、その中から軽い順に貪欲に組み合わせていくのがよさそうだと考えられる。

これは実際に証明できて、この方法で $K$ 個のロボットを作ることができるのならば、答えはYes、そうでなければNoである。

なお、頭のパーツは昇順に、体のパーツは降順にソートして先頭から組み合わせるわけではないことに注意。

実装例

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, K;
12.    cin >> N >> M >> K;
13.    vector<int> H(N), B(M);
14.    rep(i, 0, N) cin >> H[i];
15.    rep(i, 0, M) cin >> B[i];
16. 
17.    sort(all(H));
18.    sort(all(B));
19. 
20.    rep(i, 0, K)
21.    {
22.        if (H[i] > B[M - K + i])
23.        {
24.            cout << "No" << endl;
25.            return 0;
26.        }
27.    }
28. 
29.    cout << "Yes" << endl;
30.    return 0;
31.}

Submission #70771741 - TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431)

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

AtCoder

実装時間: 5 分

コメント

今回は割と思いつきやすい貪欲法で解くことができた。

作るロボットの個数が固定されておらず最大化を考えるパターンであれば、二分探索も有効そう。