[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;
}