AtCoder abc301 参加メモ

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） - AtCoder

B - Fill the Gaps

実際に配列に挿入する必要はなく、愚直に順番に出力していけばよい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];
  REP(i,n-1) {
    cout << a[i] << " ";
    for(int j = a[i]+1; j < a[i+1]; j++) cout << j << " ";
    for(int j = a[i]-1; j > a[i+1]; j--) cout << j << " ";
  }
  cout << a.back() << endl;
  return 0;
}

C - AtCoder Cards

自由に並び替えしてよいため、出現する文字種別が一致すればどうかを調べればよい。

s, t でそれぞれ一致するために足りない文字を @ で補えるかどうか調べる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  const string atc = "atcoder";
  string s,t; cin >> s >> t;
  set<char> st;
  map<char,int> ms,mt;
  for(auto c: s) { st.insert(c); ms[c]++; }
  for(auto c: t) { st.insert(c); mt[c]++; }

  bool ok = true;
  for(char c: st) {
    if (c == '@') continue;
    int d = ms[c] - mt[c];
    if (d == 0) continue;
    if (atc.find(c) == string::npos) ok = false;
    d > 0 ? mt['@'] -= d : ms['@'] -= d;
  }

  if (ms['@'] < 0 || mt['@'] < 0) ok = false;
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

D - Bitmask

ビットが ? のところを貪欲に上から n 以下になるように立てていく

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

int main() {
  string s; cin >> s;
  ll n; cin >> n;

  int sz = s.size();
  ll ans = 0;
  REP(i,sz) if (s[i] == '1') ans += (1LL << (sz-i-1));
  REP(i,sz) {
    if (s[i] != '?') continue;
    ll now = 1LL << (sz-i-1);
    if (ans + now <= n) ans += now;
  }

  cout << (ans > n ? -1 : ans) << endl;
  return 0;
}