[PGBattle2022] ましゅまろ
[HP] https://products.sint.co.jp/pg_battle
52分100点でした。ドキドキした。
[Q] https://pgbattle2022.topsic.org/examinations/results/4952
[A]
文字列の付け替えをした
int main(){
cincout();
string S;
cin >> S;
string T = S.substr(3);
cout << "8190" << T << endl;
}
[B]
問題をちゃんと読まず、+-*/全部くるかと思った。
解答をリストにいれて、全部同じか最終確認。
int main() {
cincout();
ll N;
cin >> N;
vector<ll> res; // = でえられる結果のリスト
ll val = 0;
ll n = 0;
char p;
rep(i, N * 2 + 1) {
if (i % 2 == 0) { // 数字入れ
cin >> n;
val += n;
} else { // 記号入れ
cin >> p;
if (p == '=') {
res.emplace_back(val);
val = 0;
}
}
}
res.emplace_back(val);
// = がすべて同じかどうか確認
bool ok = true;
ll ans = res[0];
for (auto v : res) {
if (v != ans) {
ok = false;
break;
}
}
if (ok) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
[C]
サンプル確認し始めたときに、順位が同じ場合を考慮する必要があって、心臓がはねた。
ll ans[200020];
int main() {
cincout();
ll N, P, Q;
cin >> N >> P >> Q;
vector<pll> V;
rep(i, N) {
ll a, b;
cin >> a >> b;
V.emplace_back(a * P + b * Q, i);
}
sort(rall(V));
ll pre = -oo;
{
ll cnt = 1;
ll dup = 0;
for (auto [val, i] : V) {
if (val == pre)
++dup;
else
dup = 0;
ans[i] = cnt - dup;
pre = val;
++cnt;
}
}
rep(i, N) { cout << ans[i] << endl; }
}
[D]
・考察
1. N=8でbit全探索かpermutationかと思うけど、実際は88要素だった。
2. 半分全列挙を考える。
3. 足が0~10本, カニみそとるとらないで、11*2 = 22通り。Nを半分ずつ取るので、22^4 = 234256通りのデータなら、間に合いそう。
4. map[うまさの総和] = 何通りで管理。
ll A[11];
ll B[11];
ll half;
// 半分全列挙
map<ll, mint> get_map(ll L, ll R) {
map<ll, mint> P;
P[0] = 1;
for (ll i = L; i < R; ++i) {
map<ll, mint> T;
ll a = A[i];
ll b = B[i];
rep(j, 11) { // 足が0-10選ぶ
rep(k, 2) { // カニみそ0-1 22^4 = 234256
ll add = a * j + b * k;
for (auto [a, b] : P) {
ll aa = add + a;
if (aa > half) continue;
mint val = COM(10, j); // 足10本のうち、j本とる取り方
val *= b;
T[aa] += val;
}
}
}
swap(P, T);
}
return P;
}
int main() {
COMinit();
cincout();
ll N;
cin >> N;
ll sum = 0;
rep(i, N) {
ll a, b;
cin >> a >> b;
sum += a * 10 + b;
A[i] = a;
B[i] = b;
}
// おいしさの総和が奇数だったらダメ
if (sum % 2 == 1) {
cout << 0 << endl;
return 0;
}
half = sum / 2;
// 半分全列挙 map[おいしさ] = 何通り
map<ll, mint> P = get_map(0, N / 2);
map<ll, mint> Q = get_map(N / 2, N);
mint ans = 0;
for (auto [a, b] : P) {
if (a > half) continue;
ans += b * Q[half - a];
}
cout << ans << endl;
}
この記事が気に入ったらサポートをしてみませんか?