C - Pasta Editorial
by
mechanicalpenciI
高橋君は \(i\) 日目に食べられる麺が複数残っている場合、どの麺を選んでも良いです。
これは高橋君が \(i-1\) 日目まで食事計画が実行できたとして、\(i\) 日目に食事計画を実行できる(長さ \(B_i\) の麺を食べられる)ためには残っている麺の長さの多重集合に\(B_i\)が含まれている事が必要十分条件であり、その多重集合はそれぞれの日に同じ長さの麺のうちのどれを食べても変わらない事から示せます。
この事実から、愚直にシミュレーションを行う事が出来ます。それぞれの日について麺を前から見ていき、その麺がまだ残っており、条件をみたす(長さが \(B_i\) に等しい)ならその日はその麺を食べたことにし、それで \(N\) 日目まで食べる麺が存在したならば Yes , ある日についてその日食べる麺が存在しなかったならば No となります。計算量は \(O(NM)\) であり、十分高速で間に合います。
実装の際には、間違って同じ麺を複数の日で食べたことにしたり、逆に複数の麺を同じ日に食べたことにしてしまったりしないように注意してください。また、分岐におけるミス等によって、No を複数回出力したり、No の後に Yes を出力してしまったりすると、誤答となってしまうので注意してください。
c++ による実装例(シミュレーション):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
int a[1000];
int b;
bool used[1000];
bool found,success;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
used[i] = false;
}
success = true;
for (int i = 0; i < m; i++) {
cin >> b;
found = false;
for (int j = 0; j < n; j++) {
if ((a[j] == b)&&(!used[j])) {
used[j] = true;
found = true;
break;
}
}
if (!found)success = false;
}
if (success)cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
また、これは std::map などのデータ構造を用いてそれぞれの長さの重複度を管理する事で \(O((N+M)\log N)\) で解くことができます。ABC の \(200\) 点問題を解く上でこの知識が必要とされるという事はおそらくないですが、もちろんこの方針でも解くことができます。
c++ による実装例(std::map を用いた解法):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
map<int, int>mp;
int x;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> x;
mp[x]++;
}
for (int i = 0; i < m; i++) {
cin >> x;
if (mp[x] == 0) {
cout << "No" << endl;
return 0;
}
mp[x]--;
}
cout << "Yes" << endl;
return 0;
}
posted:
last update:
