C - Robot Factory Editorial
by 
MMNMM
\(K\) 体の倒れないロボットを作ることができるなら、次のようにして \(K\) 体の倒れないロボットを作ることができることが証明できます。
- 頭パーツを軽いほうから \(K\) 個、体パーツを重いほうから \(K\) 個選び、それら以外をすべて破壊する。
- 残ったパーツを、軽いものどうしから組み合わせてロボットを作る。
証明
軽いほうから \(i\) 番目の頭パーツと軽いほうから \(j\) 番目の体パーツを組み合わせてロボットを作ることを \((i,j)\) で表すこととします（頭パーツと体パーツを軽いほうから並べ替えたこととして、単に \(i\) 番目の頭パーツなどと呼ぶことにします）。
\(K\) 体の倒れないロボットの作り方を \((a _ 1,b _ 1),(a _ 2,b _ 2),\ldots,(a _ K,b _ K)\ (a _ 1\lt a _ 2\lt\cdots\lt a _ K)\) とします。
\(i\le a _ i\) が成り立つので、\((1,b _ 1),(2,b _ 2),\ldots,(K,b _ K)\) としても \(K\) 体の倒れないロボットを作ることができます。
\(b _ i\gt b _ {i+1}\) となる \(i\) が存在しているとき、\((i,b _ i),(i+1,b _ {i+1})\) を \((i+1,b _ i),(i,b _ {i+1})\) に取り換えてもそれらのロボットが倒れないことを示します。
証明
パーツの番号の付け方と、\((i,b _ i),(i+1,b _ {i+1})\) で作られるロボットがいずれも倒れないことから、以下の \(3\) つの大小関係がわかります。
- \(i\) 番目の頭パーツの重さは \(i+1\) 番目のパーツの重さ以下
- \(i+1\) 番目の頭パーツの重さは \(b _ {i+1}\) 番目の体パーツの重さ以下
- \(b _ i\gt b _ {i+1}\) より \(b _ {i+1}\) 番目の体パーツの重さは \(b _ i\) 番目の体パーツの重さ以下
このことから、\((i+1,b _ i),(i,b _ {i+1})\) で作られるロボットも倒れません。\(\quad\Box\)
よって、\(b=(b _ 1,b _ 2,\ldots,b _ K)\) を昇順に並べ替えた列 \(b ^ \prime=(b ^ \prime _ 1,b ^ \prime _ 2,\ldots,b ^ \prime _ K)\) に対して \((1,b ^ \prime _ 1),(2,b ^ \prime _ 2),\ldots,(K,b ^ \prime _ K)\) で作られる \(K\) 体のロボットも倒れません。
ここで、\(b ^ \prime _ i\le i-K+N\) が成り立つので、\((1,N-K+1),(2,N-K+2),\ldots,(K,N)\) でも \(K\) 体の倒れないロボットを作ることができます。\(\quad\Box\)
つまり、上の方法で作られた \(K\) 体のロボットのいずれかが倒れれば No 、そうでなければ Yes を出力すればよいです。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
int N, M, K;
cin >> N >> M >> K;
vector<int> H(N), B(M);
for (auto&& h : H)
cin >> h;
for (auto&& b : B)
cin >> b;
// 軽いほうから並べて
ranges::sort(H);
ranges::sort(B);
// 頭の先頭 K 個と体の末尾 K 個のうち、軽いほうから見て頭のほうが重いペアがあれば No 、なければ Yes
cout << (transform_reduce(begin(H), begin(H) + K, end(B) - K, false, logical_or{}, greater{}) ? "No" : "Yes") << endl;
return 0;
}
N, M, K = map(int, input().split())
H = list(map(int, input().split()))
B = list(map(int, input().split()))
# 軽いほうから並べて
H.sort()
B.sort()
# 頭の先頭 K 個と体の末尾 K 個のうち、軽いほうから見てすべてのペアで体の重さが頭の重さ以上ならば Yes 、そうでなければ No
if all(h <= b for h, b in zip(H[:K], B[-K:])):
print('Yes')
else:
print('No')
posted:
last update: