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
一つの直方体は原点に固定して、残り2つの座標を -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