AtCoder abc349 参加メモ

Tasks - AtCoder Beginner Contest 349

B - Commencement

英小文字の出現回数を数える。その出現回数毎の回数を数えて、すべて 0 または 2 回であれば Yes

#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; cin >> s;
  vector<int> cnt1(26);
  for(auto c: s) cnt1[c-'a']++;
  vector<int> cnt2(101);
  REP(i,26) cnt2[cnt1[i]]++;

  int ok = 1;
  for(int i = 1; i <= 100; i++) ok &= (cnt2[i] == 0 || cnt2[i] == 2);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

C - Airport Code

S の先頭から T の文字とマッチするものがあるか貪欲に調べていけばよい。文字数が足りない場合は末尾に X を足して、T とマッチすれば Yes

#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;
  REP(i,3) t[i] = tolower(t[i]);

  int now = 0;
  string ns = "";
  for(auto c: s) if (c == t[now]) { now++; ns += c; }

  if (ns.size() == 2) ns += 'x';
  cout << (ns == t ? "Yes" : "No") << endl;
  return 0;
}

D - Divide Interval

L の値からシミュレーションする。 - 奇数の場合は 2⁰ * L, 2⁰ * (L+1) しかあり得ない - 偶数の場合は、2⁶⁰ から最も大きい範囲を取れる数を調べる

#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;
using P = pair<ll,ll>;

int main() {
  ll l,r; cin >> l >> r;
  vector<P> ans;
  while(l < r) {
    if (l%2) {
      ans.emplace_back(l,l+1);
      l = l+1;
    } else {
      for(ll i = 60; i >= 0; i--) {
        ll p = 1LL<<i;
        if (l % p) continue;
        ll nl = p * (l / p + 1);
        if (nl > r) continue;

        ans.emplace_back(l,nl);
        l = nl;
        break;
      }
    }
  }

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

E - Weighted Tic-Tac-Toe

お互い利益が最大になるように動く必要がある。こういうときはミニマックス法が使える。 ミニマックス法 - Wikipedia

#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 = 1e18;

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

  // used[i][j] := takahashi が置いたときは 1, aoki が置いたときは -1
  vector used(3,vector<int>(3));
  // マス{i,j}にターン t が置いたとき、タテ・ヨコ・ナナメいずれかが揃って勝てるか？
  auto win = [&](int i, int j, int t) {
    int res = 0, s = 3*t;
    used[i][j] = t;
    REP(i,3) res |= used[i][0] + used[i][1] + used[i][2] == s;
    REP(j,3) res |= used[0][j] + used[1][j] + used[2][j] == s;
    res |= used[0][0] + used[1][1] + used[2][2] == s;
    res |= used[0][2] + used[1][1] + used[2][0] == s;
    used[i][j] = 0;

    return res;
  };

  auto dfs = [&](auto self, int cnt, ll score) -> ll {
    if (cnt == 9) return score;
    // takahashi のターンは 1, aoki のターンは -1
    int t = cnt % 2 ? -1 : 1;

    ll res = -t*LINF;
    REP(i,3) REP(j,3) {
      if (used[i][j] != 0) continue; // 既に使われている
      if (win(i,j,t)) return t*LINF; // 3マス揃って勝てる場合

      used[i][j] = t;
      res = (t == 1) ?
        max(res,self(self,cnt+1,score+a[i][j]))
        : min(res,self(self,cnt+1,score-a[i][j]));
      used[i][j] = 0;
    }
    return res;
  };

  ll ans = dfs(dfs,0,0);
  cout << (ans > 0 ? "Takahashi" : "Aoki") << endl;
  return 0;
}