🔵
【ABC396】AtCoder Beginner Contest 396【C++】
コンテスト名
AtCoder Beginner Contest 396
コンテストURL
開催日
2025/03/08 21:00-22:40
A: Triple Four
解法
- 問題文通りに判定する
ABC396A.cpp
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> A(n);
for(int i=0; i<n; i++){
cin >> A[i];
}
for(int i=2; i<n; i++){
if(A[i-2]==A[i-1] && A[i-1]==A[i]){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}
B: Card Pile
解法
- スタックで実装する
ABC396B.cpp
#include <iostream>
#include <vector>
using namespace std;
int main(){
int q;
cin >> q;
vector<int> V;
for(int i=0; i<100; i++){
V.push_back(0);
}
int num, x;
for(int i=0; i<q; i++){
cin >> num;
if(num==1){
cin >> x;
V.push_back(x);
}else{
cout << V.back() << '\n';
V.pop_back();
}
}
return 0;
}
C: Buy Balls
解法
-
と をそれぞれ降順にソートする -
かつ となる最大の まで、黒色のボールと白色のボールを両方選ぶ -
より大きい範囲は、 となる最大の まで、黒色のボールのみを選ぶ
ABC396C.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<long long int> B(n), W(m);
for(int i=0; i<n; i++){
cin >> B[i];
}
for(int i=0; i<m; i++){
cin >> W[i];
}
sort(B.rbegin(), B.rend());
sort(W.rbegin(), W.rend());
long long int sum = 0;
int i;
bool flag = true;
for(i=0; i<min(n, m); i++){
if(W[i]>0 && B[i]+W[i]>0){
sum += (B[i]+W[i]);
}else{
flag = false;
break;
}
}
if(flag){
i = min(n, m);
}
for(int j=i; j<n; j++){
if(B[j]>0){
sum += B[j];
}else{
break;
}
}
cout << sum << endl;
return 0;
}
D: Minimum XOR Path
解法
- 順列全探索
- 深さ優先探索 (DFS)
ABC396D_1.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
long long int n, m;
cin >> n >> m;
vector<vector<long long int>> G(n, vector<long long int>(n, -1));
int u, v;
long long int w;
for(int i=0; i<m; i++){
cin >> u >> v >> w;
u--;
v--;
G[u][v] = w;
G[v][u] = w;
}
long long int minv = 1LL<<60;
vector<int> P;
for(int i=1; i<n; i++){
P.push_back(i);
}
do{
long long int sum = 0;
int pre = 0;
for(int i=0; i<n-1; i++){
if(G[pre][P[i]]!=-1){
sum ^= G[pre][P[i]];
pre = P[i];
}else{
break;
}
if(P[i]==n-1){
minv = min(minv, sum);
}
}
}while(next_permutation(P.begin(), P.end()));
cout << minv << endl;
return 0;
}
ABC396D_2.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long int n, m;
vector<vector<pair<int, long long int>>> G;
vector<int> seen;
long long int minv = 1LL<<60;
void dfs(int x, long long int sum){
seen[x] = 1;
if(x==n-1){
minv = min(minv, sum);
}
for(int i=0; i<G[x].size(); i++){
auto [nx, w] = G[x][i];
if(seen[nx]){
continue;
}
dfs(nx, sum^w);
}
seen[x] = 0;
}
int main(){
cin >> n >> m;
G.resize(n);
int u, v;
long long int w;
for(int i=0; i<m; i++){
cin >> u >> v >> w;
u--;
v--;
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
seen.resize(n);
dfs(0, 0);
cout << minv << endl;
return 0;
}
E: Min of Restricted Sum
解法
- 頂点
と頂点 を重み の辺で結ぶ無向グラフを考える - 連結成分ごとに幅優先探索 (BFS) する
- 一つの頂点の値が決まれば、XOR の条件より、同じ連結成分のすべての値が決まる
- 各ビットは独立であることを利用する
- 各ビットにおいて、
1
の数が過半数の場合は、0
と1
を逆転する
ABC396E.cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> G(n);
int x, y, z;
for(int i=0; i<m; i++){
cin >> x >> y >> z;
x--;
y--;
G[x].emplace_back(y, z);
G[y].emplace_back(x, z);
}
vector<int> A(n);
vector<int> seen(n);
vector<int> B(n, -1);
for(int i=0; i<n; i++){
if(seen[i]){
continue;
}
queue<pair<int, int>> Q;
Q.emplace(i, 0);
B[i] = 0;
vector<int> V;
V.push_back(i);
while(!Q.empty()){
auto [x, z] = Q.front();
Q.pop();
seen[x] = 1;
for(int j=0; j<G[x].size(); j++){
auto [nx, nz] = G[x][j];
if(B[nx]!=-1){
if(B[nx]!=(z^nz)){
cout << -1 << endl;
return 0;
}else{
continue;
}
}
Q.emplace(nx, z^nz);
B[nx] = z^nz;
V.push_back(nx);
}
}
for(int j=0; j<30; j++){
int cnt = 0;
for(int l=0; l<V.size(); l++){
if(B[V[l]]&(1<<j)){
cnt++;
}
}
if(cnt<V.size()-cnt){
for(int l=0; l<V.size(); l++){
if(B[V[l]]&(1<<j)){
A[V[l]] |= (1<<j);
}
}
}else{
for(int l=0; l<V.size(); l++){
if(!(B[V[l]]&(1<<j))){
A[V[l]] |= (1<<j);
}
}
}
}
}
for(int i=0; i<n; i++){
if(i){
cout << " ";
}
cout << A[i];
}
cout << endl;
return 0;
}
Discussion