少し前のことですが、ABC333に参加していたので記録として投稿しておきます。
成績は3完。
A Three Threes
#include<bits/stdc++.h>
using namespace std;
int main () {
int N;
std::cin >> N;
for(int i=0; i<N; i++){
std::cout << N;
}
std::cout << std::endl;
}B Pentagon
#include<bits/stdc++.h>
using namespace std;
int main () {
std::string S,T;
std::cin >> S >> T;
std::sort(S.begin(), S.end());
std::sort(T.begin(), T.end());
int length_s = S[1]-S[0];
int length_t = T[1]-T[0];
if((length_s == 2)||(length_s == 3)){
length_s = 2;
}
else{
length_s = 1;
}
if((length_t == 2)||(length_t == 3)){
length_t = 2;
}
else{
length_t = 1;
}
if(length_s == length_t){
std::cout << "Yes" << std::endl;
}
else{
std::cout << "No" << std::endl;
}
}C Repunit Trio
#include<bits/stdc++.h>
using namespace std;
int main () {
long long repnits[12] = {1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111};
// std::vector<long long> sums;
std::set<long long> sums;
for(int i=0; i<12; i++){
for(int j=0; j<12; j++){
for(int k=0; k<12; k++){
// sums.push_back(repnits[i]+repnits[j]+repnits[k]);
sums.insert(repnits[i]+repnits[j]+repnits[k]);
}
}
}
// std::sort(sums.begin(), sums.end());
int N;
std::cin >> N;
auto itr = sums.begin();
for(int i=1; i<N; i++){
// std::cout << sums[i] << std::endl;
// std::cout << *itr << std::endl;
itr++;
}
//std::cout << sums[N-1] << std::endl;
std::cout << *itr << std::endl;
}D Erase Leaves
木に対して深さ優先探索をしていくと回答できる問題。
木もDFSも知らなくて腰抜かしてました。
#include <iostream>
#include<vector>
struct TreeNode {
std::vector<int> Children;
bool IsVisited = false;
};
std::vector<TreeNode> _Tree;
// あるノードを根とした部分木の大きさを返す。
int dfs(int node_index, int tmp_count) {
_Tree[node_index].IsVisited = true;
tmp_count++; // カウントアップ
for (auto p : _Tree[node_index].Children) {
if (p != 0) {
if (_Tree[p].IsVisited == false) {
tmp_count = dfs(p, tmp_count);
}
}
}
return tmp_count;
}
int main()
{
int N;
std::cin >> N;
_Tree.resize(N, TreeNode());
for (int i = 0; i < (N-1); i++) { //N個の頂点を持つ木の辺の数はN-1個
int u, v;
std::cin >> u >> v;
u--;
v--;
_Tree[u].Children.push_back(v);
_Tree[v].Children.push_back(u);
}
/*
問題のポイント
頂点1を消すことが出来る＝頂点１に繋がっている部分木のうち、大きさが最大でないものを全部消した状態
⇒答え = 全頂点数 - 最大の部分木の大きさ
*/
int max_subtree_size = 0;
for (int i = 0; i < _Tree[0].Children.size(); i++) { //「頂点１」と繋がっている部分木に着目
max_subtree_size = std::max(dfs(_Tree[0].Children[i], 0), max_subtree_size);
}
std::cout << (N - max_subtree_size) << std::endl;
}
コメント