AtCoder abc324 参加メモ

AtCoder ABC

Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324) - AtCoder

B - 3-smooth Numbers

2 と 3 で割れるだけ割った結果が 1 であれば Yes

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

int main() {
  ll n; cin >> n;
  while(n%2 == 0) n/=2;
  while(n%3 == 0) n/=3;
  cout << (n == 1 ? "Yes" : "No") << endl;
  return 0;
}

C - Error Correction

条件1 と 4 は文字列の長さが一致して、かつ違いが1文字以下の場合で判定する

条件2 と 3 はまず文字列の長さの差が 1 である必要がある(挿入か削除を1度だけ行うため)。あとは文字列を先頭から比較して、一致しないときはずらすようにして比較すれば、判定できる

#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;
  string t; cin >> t;

  vector<int> ans;
  REP(i,n) {
    string s; cin >> s;

    // 条件 1,4
    auto f1 = [&]() {
      if (s.size() != t.size()) return false;
      int d = 0;
      REP(i,(int)t.size()) if (s[i] != t[i]) d++;
      return d <= 1;
    };

    // 条件 2,3
    auto f2 = [&]() {
      if (abs((int)t.size() - (int)s.size()) != 1) return false;
      bool flag = false;
      if (t.size() < s.size()) { flag = true; swap(t,s); }
      int p = 0;
      REP(i,(int)t.size()) {
        if (p < (int)s.size() && t[i] == s[p]) p++;
      }
      bool res = p >= (int)t.size()-1;
      if (flag) swap(t,s);
      return res;
    };
    if (f1() || f2()) ans.push_back(i+1);
  }

  cout << ans.size() << endl;
  for(auto v: ans) cout << v << " ";
  return 0;
}

D - Square Permutation

1013 未満の平方数を列挙する。平方数の 1〜9 の数の出現数が同じであり、S に含まれる 0 の数 >= 平方根に含まれる 0 の数 のとき S の並び替えで達成できる。

#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() {
  int n; cin >> n;
  string s; cin >> s;
  vector<int> cnt(10);
  REP(i,n) { cnt[s[i]-'0']++; }

  int ans = 0;
  REP(i,3162278) {
    ll x = (ll)i*i;
    vector<int> now(10);
    while(x) { now[x % 10]++; x /= 10; }
    bool ok = true;
    for(int j = 1; j <= 9; j++) if (cnt[j] != now[j]) ok = false;
    ok = ok && cnt[0] >= now[0];
    if (ok) ans++;
  }

  cout << ans << endl;
  return 0;
}

E - Joint Two Strings

前と後の両方から部分列をどこまで含んでいるか調べて、前から見て i 文字目までの部分列を含んでいるとき、後ろからみて n-i 文字以上の部分列を含んでいる文字列はすべて条件に一致する。累積和を使って合計を求めた。

#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() {
  int n; cin >> n;
  string t; cin >> t;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  int ts = t.size();
  vector<int> m(ts+1);
  REP(i,n) {
    int p = ts-1;
    for(int j = s[i].size()-1; j >= 0; j--) if (s[i][j] == t[p]) p--;
    m[p+1]++;
  }

  vector<int> cs(ts+2); // 累積和
  REP(i,ts+1) cs[i+1] = cs[i] + m[i];
  reverse(cs.begin(),cs.end());

  ll ans = 0;
  REP(i,n) {
    int p = 0;
    REP(j,(int)s[i].size()) if (s[i][j] == t[p]) p++;
    ans += cs[ts-p];
  }
  cout << ans << endl;
  return 0;
}

雑感

C が実装ややこして焦る。 E は逆から累積和取る処理がうまくいかずに詰まる。 なんとかデバッグ間に合って終了5分前に AC。F は手がつけられず。

tic40さんの日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）での成績：1588位
パフォーマンス：1295相当
レーティング：1144→1160 (+16) :)
#AtCoder #日本レジストリサービス（JPRS）プログラミングコンテスト2023（ABC324） https://atcoder.jp/users/tic40/history/share/abc324?lang=ja