AtCoder abc343 参加メモ

AtCoder Beginner Contest 343 - AtCoder

B - Adjacency Matrix

隣接行列を隣接リストにする

#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) REP(j,n) {
    int a; cin >> a;
    if (a == 1) g[i].push_back(j+1);
  }
  REP(i,n) {
    for(auto v: g[i]) cout << v << " ";
    cout << endl;
  }
  return 0;
}

C - 343

全探索する。数字を文字列に変換して回文判定。

#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;

bool is_palindrome(string s) {
  string t = s;
  reverse(t.begin(),t.end());
  return t == s;
}

int main() {
  ll n, ans = 0; cin >> n;
  REP(i,1e6+1) {
    ll x = (ll)i*i*i;
    if (x > n) break;
    if (is_palindrome(to_string(x))) { ans = x; }
  }
  cout << ans << endl;
  return 0;
}

D - Diversity of Scores

map で現在の点数の種類数を管理する

#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,t; cin >> n >> t;
  vector<ll> m(n);
  map<ll,int> mp;
  mp[0] = n;

  REP(_,t) {
    int a,b; cin >> a >> b; a--;
    ll before = m[a], after = m[a]+b;
    mp[before]--; mp[after]++;
    if (mp[before] == 0) mp.erase(before);
    m[a] = after;
    cout << mp.size() << endl;
  }
  return 0;
}

E - 7x7x7

一つの直方体は原点に固定して、残り２つの座標を -7 〜 +7 の範囲で全探索する。 直方体の重なっている部分の面積はがんばって計算する。

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

const int L = 7;
// 3つの直方体が重なっている部分の面積を返す
int calcArea(T sq1, T sq2, T sq3) {
  auto [x1,y1,z1] = sq1;
  auto [x2,y2,z2] = sq2;
  auto [x3,y3,z3] = sq3;
  int minX = max({x1, x2, x3});
  int maxX = min({x1, x2, x3}) + L;
  int minY = max({y1, y2, y3});
  int maxY = min({y1, y2, y3}) + L;
  int minZ = max({z1, z2, z3});
  int maxZ = min({z1, z2, z3}) + L;
  if (maxX - minX < 0 || maxY - minY < 0 || maxZ - minZ < 0) return 0;
  return (maxX - minX) * (maxY - minY) * (maxZ - minZ);
}

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

  auto f = [&](int x1, int y1, int z1, int x2, int y2, int z2) {
    T sq1 = {0,0,0};
    T sq2 = {x1,y1,z1};
    T sq3 = {x2,y2,z2};

    int v3 = calcArea(sq1,sq2,sq3);
    // 1-2, 1-3, 2-3 それぞれの組み合わせで重なっている部分の面積の合計 - 3つ重なっている部分の面積
    int v2 = calcArea(sq1,sq1,sq2) + calcArea(sq1,sq1,sq3) + calcArea(sq2,sq2,sq3) - v3*3;
    int v1 = (7*7*7*3) - (v3*3 + v2*2); // 3つの合計面積 - 重なっている部分の面積
    return (v[0] == v1 && v[1] == v2 && v[2] == v3);
  };

  for(int i1 = -7; i1 <= 7; i1++) {
    for(int j1 = -7; j1 <= 7; j1++) {
      for(int k1 = -7; k1 <= 7; k1++) {
        for(int i2 = -7; i2 <= 7; i2++) {
          for(int j2 = -7; j2 <= 7; j2++) {
            for(int k2 = -7; k2 <= 7; k2++) {
              if (f(i1,j1,k1,i2,j2,k2)) {
                printf("Yes\n0 0 0 %d %d %d %d %d %d\n",i1,j1,k1,i2,j2,k2);
                return 0;
              }
            }
          }
        }
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

tic40さんのAtCoder Beginner Contest 343での成績：1741位
パフォーマンス：1296相当
レーティング：1050→1077 (+27) :)
#AtCoder #ABC343 https://atcoder.jp/users/tic40/history/share/abc343?lang=ja