AtCoder abc333 参加メモ

Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333） - AtCoder

B - Pentagon

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

int main() {
  string s,t; cin >> s >> t;
  auto f = [&](string s) {
    int x = s[0]-'A', y = s[1]-'A';
    int d = abs(x-y);
    return d > 2 ? 5 - d : d;
  };

  cout << (f(s) == f(t) ? "Yes" : "No") << endl;
  return 0;
}

C - Repunit Trio

#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;
  vector<ll> x = { 1 };
  REP(i,11) x.push_back(x.back()*10+1);

  set<ll> st;
  auto dfs = [&](auto self, ll tot, int cnt) -> void {
    if (cnt == 3) { st.insert(tot); return; }
    for(auto v: x) { self(self,tot+v,cnt+1); }
  };

  dfs(dfs,0,0);
  auto it = st.begin();
  REP(i,n-1) it++;
  cout << *it << endl;
  return 0;
}

D - Erase Leaves

#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 g(n,vector<int>());
  REP(i,n-1) {
    int u,v; cin >> u >> v;
    u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  auto dfs = [&](auto self, int i, int p) -> int {
    int res = 1;
    for(auto v: g[i]) {
      if (v == p) continue;
      res += self(self,v,i);
    }
    return res;
  };

  vector<int> s;
  for(auto v: g[0]) s.push_back(dfs(dfs,v,0));
  sort(s.begin(),s.end());

  s.pop_back();
  int ans = 1;
  for(auto v: s) ans += v;
  cout << ans << endl;

  return 0;
}

E - Takahashi Quest

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

  vector g(n, vector<int>());
  vector<int> potion(n); // potion[i] := ポーションを i に拾ったら 1
  REP(i,n) {
    if (t[i] == 1) g[x[i]].push_back(i);
    if (t[i] == 2) {
      if (g[x[i]].size() == 0) { cout << -1 << endl; return 0; }
      potion[g[x[i]].back()] = 1;
      g[x[i]].pop_back();
    }
  }

  vector<int> ans;
  int mx = 0, sum = 0;
  REP(i,n) {
    if (t[i] == 1) {
      ans.push_back((potion[i] ? 1 : 0));
      if (potion[i]) { sum++; mx = max(mx,sum); }
    }
    if (t[i] == 2) sum--;
  }

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

tic40さんのトヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）での成績：2207位
パフォーマンス：1144相当
レーティング：1048→1058 (+10) :)
#AtCoder #トヨタ自動車プログラミングコンテスト2023#8（ABC333） https://atcoder.jp/users/tic40/history/share/abc333?lang=ja 

AtCoder abc325 参加メモ

KEYENCE Programming Contest 2023 Autumn（AtCoder Beginner Contest 325） - AtCoder

B - World Meeting

全探索。0時〜23時の時間を決め打ってその時間に最大何人参加できるかを計算する

#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> w(n),x(n);
  REP(i,n) cin >> w[i] >> x[i];
  int ans = 0;
  for(int t = 0; t <= 23; t++) {
    int sum = 0;
    REP(i,n) {
      int now = (t + x[i]) % 24;
      if (now >= 9 && now <= 17) sum += w[i];
    }
    ans = max(ans,sum);
  }
  cout << ans << endl;
  return 0;
}

C - Sensors

dfs で連動しているセンサーをチェックする

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

const vector<P> moves = {
  {-1,-1}, {-1,0}, {-1,1},
  {0,-1}, {0,1},
  {1,-1}, {1,0}, {1,1}
};

int main() {
  int h,w; cin >> h >> w;
  vector<string> s(h);
  REP(i,h) cin >> s[i];

  vector visited(h,vector<bool>(w));
  auto dfs = [&](auto self, int i, int j) -> void {
    if (visited[i][j]) return;
    visited[i][j] = true;

    for(auto [di,dj]: moves) {
      int ni = i+di, nj = j+dj;
      if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
      if (s[ni][nj] == '.') continue;
      self(self,ni,nj);
    }
    return;
  };

  int ans = 0;
  REP(i,h) REP(j,w) {
    if (s[i][j] == '.' || visited[i][j]) continue;
    dfs(dfs,i,j);
    ans++;
  }

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

D - Printing Machine

#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;
const ll LINF = numeric_limits<ll>::max();

int main() {
  int n; cin >> n;
  map<ll,vector<ll>> mp;
  REP(i,n) {
    ll t,d; cin >> t >> d;
    mp[t].push_back(t+d);
  }

  ll t = 0, ans = 0;
  priority_queue<ll, vector<ll>, greater<ll>> q;
  auto f = [&](ll k) {
    while(t < k && q.size()) {
      ll now = q.top(); q.pop();
      if (t <= now) { ans++; t++; }
    }
  };

  for(auto [k,v]: mp) {
    f(k); t = k;
    for(auto nv: v) q.push(nv);
  }
  f(LINF);
  cout << ans << endl;
  return 0;
}

雑感

D 問題でバグらせてしまい、大幅にロス。E は十分に時間があれば解けた問題だったなあ。悔しい

tic40さんのキーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）での成績：1994位
パフォーマンス：1090相当
レーティング：1160→1153 (-7) :(
#AtCoder #キーエンスプログラミングコンテスト2023秋（ABC325） https://atcoder.jp/users/tic40/history/share/abc325?lang=ja 

AtCoder abc324 参加メモ

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

10¹³ 未満の平方数を列挙する。平方数の 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 

AtCoder arc166 B - Make Multiples

B - Make Multiples

公式解説 を元に解いたのでメモ。

#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;
template<class T> void chmin(T& a, T b) { a = min(a,b); }

int main() {
  ll n,a,b,c; cin >> n >> a >> b >> c;
  vector<ll> x(n);
  REP(i,n) cin >> x[i];
  ll ab = lcm(a,b);
  ll ac = lcm(a,c);
  ll bc = lcm(b,c);
  ll abc = lcm(ab,c);
  vector<ll> r = { 1, a, b, ab, c, ac, bc, abc };

  auto f = [](ll x, ll y) -> ll { return (y - (x%y)) % y; };

  vector dp(n+1,vector<ll>(1<<3,2e18));
  dp[0][0] = 0;
  REP(i,n) REP(bit,1<<3) REP(j,(int)r.size()) {
    chmin(dp[i+1][bit | j], dp[i][bit] + f(x[i],r[j]));
  }

  cout << dp[n][(1<<3) - 1] << endl;
  return 0;
}

AtCoder arc166 A - Replace C or Swap AB

A - Replace C or Swap AB

公式解説 を元に解いたのでメモ。

解説を見てもなかなかシュッと実装できなくて難しい

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

int main() {
  int t; cin >> t;
  REP(_,t) {
    int n; string x,y;
    cin >> n >> x >> y;
    x += 'C'; y += 'C'; // 番兵
    n++; // 番兵分を +1
    map<char,vector<int>> mx,my;

    auto check = [&]() -> bool {
      int diff = my['A'].size() - mx['A'].size();
      // X の A の数が多ければ false
      // Y の A の数が多いときは X の C のよりも差分多ければ false
      if (diff < 0 || (int)mx['C'].size() < diff) return false;

      // X の C を早く出現するものから A に置き換える
      REP(i,diff) mx['A'].push_back(mx['C'][i]);
      sort(mx['A'].begin(),mx['A'].end());
      // 両者の A の出現位置を調べる
      REP(i,(int)my['A'].size()) if (my['A'][i] < mx['A'][i]) return false;
      return true;
    };

    bool ok = true;
    REP(i,n) {
      mx[x[i]].push_back(i);
      my[y[i]].push_back(i);
      if (y[i] == 'C') {
        ok = ok && x[i] == 'C' && check();
        mx.clear(); my.clear();
      }
    }
    cout << (ok ? "Yes" : "No") << endl;
  }
  return 0;
}

AtCoder abc323 参加メモ

UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323) - AtCoder

B - Round-Robin Tournament

それぞれ勝った回数をカウントして、回数の多い順に sort する。

勝ち数が同じ場合には番号の早い順となるため注意。

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

int main() {
  int n; cin >> n;
  vector<int> cnt(n);
  REP(i,n) {
    string s; cin >> s;
    REP(j,n) if (s[j] == 'o') cnt[i]++;
  }

  vector<P> p(n);
  REP(i,n) p[i] = { cnt[i], -(i+1) }; // 勝ち数が同じ場合は番号の早い順
  sort(p.rbegin(),p.rend());

  for(auto [_,v]: p) cout << -v << " ";
  return 0;
}

C - World Tour Finals

他のプレイヤーの総合得点を上回るまで、貪欲に得点の高い問題から解いていけば良い。

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

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(m);
  vector<string> s(n);
  REP(i,m) cin >> a[i];
  REP(i,n) cin >> s[i];

  vector<int> score(n);
  REP(i,n) {
    REP(j,m) if (s[i][j] == 'o') score[i] += a[j];
    score[i] += (i+1);
  }

  vector<P> p(m);
  REP(i,m) p[i] = {a[i],i};
  sort(p.rbegin(),p.rend());
  vector<int> order(m);
  REP(i,m) order[i] = p[i].second;

  int mx = *max_element(score.begin(),score.end());
  REP(i,n) {
    int ans = 0;
    for(auto j: order) {
      if (score[i] >= mx) break;
      if (s[i][j] == 'o') continue;
      score[i] += a[j];
      ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

D - Merge Slimes

貪欲にサイズの小さいスライムから合成していく

#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;
  map<ll,ll> mp;
  REP(i,n) {
    int s,c; cin >> s >> c;
    mp[s] += c;
  }

  int ans = 0;
  for(auto [size,cnt]: mp) {
    mp[size*2] += cnt/2;
    ans += cnt % 2;
  }
  cout << ans << endl;
  return 0;
}

E - Playlist

DP で解いた。

• dp[i][j] = 時刻 i のときに j:0(1番目), j:1(1番目以外) の曲が流れているときの確率

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

int main() {
  int n,x; cin >> n >> x;
  vector<int> t(n);
  REP(i,n) cin >> t[i];

  // dp[i][j] := 時刻 i のときに j:0(1番目), j:1(1番目以外) になる確率
  vector dp(x+2,vector<mint>(2));
  mint r = (mint)1/n;
  REP(i,n) dp[min(x+1,t[i])][i == 0 ? 0 : 1] += r;

  REP(i,x+1) REP(j,n) REP(k,2) {
    if (dp[i][k] == 0) continue;
    dp[min(x+1,i + t[j])][j == 0 ? 0 : 1] += dp[i][k]*r;
  }

  cout << dp[x+1][0].val() << endl;
  return 0;
}

雑感

C で凡ミスして2WA、E は方針はすぐたったが、確率計算がうまくあわなくてかなりロスした。 確率や期待値問題、どうしても苦手意識がある

tic40さんのユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)での成績：1824位
パフォーマンス：1266相当
レーティング：1133→1147 (+14) :)
#AtCoder #ユニークビジョンプログラミングコンテスト2023秋(ABC323) https://atcoder.jp/users/tic40/history/share/abc323?lang=ja 

AtCoder abc322 参加メモ

AtCoder Beginner Contest 322 - AtCoder

B - Prefix and Suffix

問題文通りに愚直にやる

#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,m; cin >> n >> m;
  string s,t; cin >> s >> t;

  auto t1 = t.substr(0,n);
  auto t2 = t.substr(m-n);
  int ans = 3;
  if (s == t1 && s == t2) ans = 0;
  if (s == t1 && s != t2) ans = 1;
  if (s == t2 && s != t1) ans = 2;
  cout << ans << endl;
  return 0;
}

C - Festival

二分探索でやると楽

#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,m; cin >> n >> m;
  vector<int> a(m);
  REP(i,m) cin >> a[i];
  for(int i = 1; i <= n; i++) {
    auto it = lower_bound(a.begin(),a.end(),i);
    cout << *it - i << endl;
  }
  return 0;
}

D - Polyomino

ポリオミノはそれぞれ 回転(4) x 置く位置(4x4) = 64 通り置くパターンがある(重複やグリッドからはみ出るケースも含む)。それが3つあるため全探索すると 64³ 通り。これなら全探索でいける。

実装が重くプログラミング力が試される問題だった。

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

int main() {
  vector p(3,vector<string>(4));
  REP(i,3) REP(j,4) cin >> p[i][j];

  auto rorate90 = [&](vector<string> &s) -> void {
    auto t = s;
    REP(i,4) REP(j,4) t[i][j] = s[3-j][i];
    s = t;
  };

  auto reset = [&](vector<P> &v) -> void {
    int minx = INF, miny = INF;
    for(auto [x,y]: v) {
      minx = min(minx,x);
      miny = min(miny,y);
    }
    for(auto& [x,y]: v) { x -= minx; y -= miny; }
  };

  // pa[i][j] := i番目のポリオミノを (j+1)*90 度回転させたときの座標の集合
  vector pa(3,vector(4,vector<P>()));
  REP(k,3) REP(r,4) {
    rorate90(p[k]);
    REP(i,4) REP(j,4) if (p[k][i][j] == '#') pa[k][r].emplace_back(i,j);
    reset(pa[k][r]); // 左上に詰める
  }

  auto dfs = [&](auto self, int i, vector<vector<bool>> now) {
    if (i == 3) {
      REP(ni,4) REP(nj,4) if (!now[ni][nj]) return false;
      return true;
    }

    bool res = false;
    for(auto npa: pa[i]) {
      REP(ni,4) REP(nj,4) {
        auto nnow = now;
        bool ok = true;
        for(auto [x,y]: npa) {
          auto check = [&]() -> bool {
            int nx = x+ni, ny = y+nj;
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) return false;
            if (nnow[nx][ny]) return false;
            return nnow[nx][ny] = true;
          };
          ok = ok && check();
        }
        res = res || (ok && self(self,i+1,nnow));
      }
    }
    return res;
  };

  bool ans = dfs(dfs,0,vector(4,vector<bool>(4)));
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}

E - Product Development

DPで解いた。 p <= 5 と小さいため p+1 進数で各パラメータの状態を持つようにした(p <= 5, k <= 5 なので最大でも 6⁵ の状態)

dp[i][j] := i まで見たときの各パラメータの集合が j のときのコストの最小値

#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;
const ll LINF = numeric_limits<ll>::max();

int main() {
  int n,k,p; cin >> n >> k >> p;
  vector<int> c(n);
  vector a(n,vector<int>(k));
  REP(i,n) {
    cin >> c[i];
    REP(j,k) cin >> a[i][j];
  }

  int base = p+1; // base 進数
  int sn = pow(base,k);
  // dp[i][j] := i 個までみたとき、パラメータ集合が j のときの最小コスト
  vector dp(n+1,vector<ll>(sn, LINF));
  dp[0][0] = 0;
  REP(i,n) REP(s,sn) {
    if (dp[i][s] == LINF) continue;
    // 選ばない
    dp[i+1][s] = min(dp[i+1][s],dp[i][s]);
    // 選ぶ
    int x = 1, nex = s;
    REP(j,k) {
      int now = s / x % base; // 現在のパラメータ値
      nex += (min(p, now + a[i][j]) - now) * x;
      x *= base;
    }
    dp[i+1][nex] = min(dp[i+1][nex],dp[i][s] + c[i]);
  }

  int x = 1, t = 0;
  REP(i,k) { t += p * x; x *= base; }
  if (dp[n][t] == LINF) dp[n][t] = -1;
  cout << dp[n][t] << endl;
  return 0;
}

雑感

D問題の実装重くて、ひやひやした。E問題もDPで解く方針はすぐに立てられたものの、パラメータの集合の持ち方が普段と違いすんなりいかなかった。もうちょっと早く解きたいところ。

tic40さんのAtCoder Beginner Contest 322での成績：1311位
パフォーマンス：1415相当
レーティング：1097→1133 (+36) :)
#AtCoder #ABC322 https://atcoder.jp/users/tic40/history/share/abc322?lang=ja