AtCoder Beginner Contest 287
結果
A - Majority:AC(3:06)
B - Postal Card:AC(18:08)(2ペナ)
C - Path Graph?:AC(52:30)
D - Match or Not:WA
A - Majority
ある提案に対し$${N}$$人(奇数)の人がそれぞれ「For」か「Against」で表明している
過半数の人がこの提案に賛成しているかを判定する問題
自分の回答
int main(){
int N;
cin >> N;
string s;
int f = 0;
for(int i = 0; i < N; i++){
cin >> s;
if(s == "For"){
f++;
}
}
if(f > N / 2){
printf("Yes\n");
}
else{
printf("No\n");
}
}そのまま
公式解説
省略
B - Postal Card
数字のみからなる6文字の文字列が$${N}$$個と3文字の文字列が$${M}$$個与えられ、6文字の文字列の内、下3文字が3文字の文字列のいずれかと一致するものがいくつあるかを求める問題
自分の回答
int main(){
int N, M;
cin >> N >> M;
vector<int> S(N), T(M);
for(int i = 0; i < N; i++){
cin >> S[i];
}
for(int i = 0; i < M; i++){
cin >> T[i];
}
int ans = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(S[i] % 1000 == T[j]){
ans++;
break;
}
}
}
printf("%d\n", ans);
}intでやってるけど今になって思えばこれ下3桁じゃなかったらダメなやつだったなこれ
分かったうえで取った方法じゃなかったからこれは良くない
Tの中にSの下3と一致するものがいくつあるかと勘違いして2ペナ
公式解説
省略
C - Path Graph?
$${N}$$頂点$${M}$$辺の単純無向グラフが与えられ、そのグラフがパスグラフ(全ての頂点が分岐なく一直線につながっているグラフ)かを判定する問題
自分の回答
int main(){
int N, M;
cin >> N >> M;
if(N - 1 != M){
printf("No\n");
return 0;
}
vector<vector<int>> G(N + 1);
int u, v;
for(int i = 0; i < M; i++){
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
queue<int> bfs;
vector<bool> check(N + 1, false);
for(int i = 1; i <= N; i++){
if(G[i].size() == 1){
bfs.push(i);
check[i] = true;
break;
}
}
while(!bfs.empty()){
int b = bfs.front();
bfs.pop();
if(G[b].size() >= 3){
printf("No\n");
return 0;
}
for(int x : G[b]){
if(check[x] == true){
continue;
}
bfs.push(x);
check[x] = true;
}
}
printf(count(check.begin(), check.end(), false) == 1 ? "Yes\n" : "No\n");
}まずパスグラフであるためにはM=N-1である必要があるためそこでふるいにかけてるけどこれはWAだった回答の残骸でこっちではいらなかった
グラフの始点(辺が1つの頂点)を見つけてそこから幅優先探索、辺が3つの頂点があったらダメなため終わり、最後まで行ったら全部の頂点を通ったかを判定
後から思えば始点を探す必要もなかったな
最初は残骸と各頂点の辺の数が1か2で行けると思ったけど1-2-3-1 4-5みたいなパターンを見逃してて1ペナ
公式解説
省略
D - Match or Not
英小文字と「?」からなる文字列$${S,T}$$が与えられ、$${S}$$の先頭$${x}$$文字と末尾($${T}$$の文字数-$${x}$$)文字を連結した文字列$${S'}$$と$${T}$$が一致するか(このとき「?」は任意の英小文字として扱える)を1から$${T}$$の文字数までの$${x}$$全てにおいて判定する問題
自分の回答
愚直に調べる方法で書いてみたがWAもTLEも出たため根本的に違う
最初の文字列の時点で計算できるんだろうなとは思いつつ方法を思いつかなかった
公式解説
bool match_or_not(char a,char b){
return a=='?' || b=='?' || a==b;
}
int main() {
string S,T;
cin>>S>>T;
vector<int> pre(S.size()+1,false),suf(S.size()+1,false);
pre[0] = true;
for(int i=0;i<T.size();i++){
if(!match_or_not(S[i],T[i]))break;
pre[i+1] = true;
}
reverse(S.begin(),S.end());
reverse(T.begin(),T.end());
suf[0] = true;
for(int i=0;i<T.size();i++){
if(!match_or_not(S[i],T[i]))break;
suf[i+1] = true;
}
for(int i=0;i<=T.size();i++){
if(pre[i] && suf[T.size()-i])printf("Yes\n");
else printf("No\n");
}
return 0;
}https://atcoder.jp/contests/abc287/editorial/5631より
そうかxがいくつだろうと前からと後ろからでそれぞれどの文字と当たるかは固定か
だからどの文字まで一致できるかを調べて前後両方trueならばYesか
なるほど