スポンサーがHUAWEIでしたね。
A問題 Yay!
mapを使えばあっという間に実装終了。
#include <bits/stdc++.h> using namespace std; int main() { string s; map<char,int>dict; cin >> s; for(int i=0;i<s.size();i++){ if(dict.count(s[i])==0)dict[s[i]]=1; else dict[s[i]]++; } for(int i=0;i<s.size();i++){ if(dict[s[i]]==1)cout << i+1 << endl; } return 0; }
B問題 Which is ahead?
人iが前から何番目にいるかを格納する配列を作ってo(1)でアクセスできるようにすれば通ります。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int>p(n); for(int i=0;i<n;i++)cin >> p[i]; vector<int>num(n); for(int i=0;i<n;i++)num[p[i]-1]=i+1; int t; cin >> t; int a,b; for(int q=0;q<t;q++){ cin >> a >> b; if(num[a-1]<num[b-1])cout << a << endl; else cout << b << endl; } return 0; }
C問題 Many Replacement
mapをうまいこと使えば解けるんですねぇ。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; string s; cin >> s; map<char,char>dict; map<char,vector<char>>dict2; for(int i=0;i<n;i++)dict[s[i]]=s[i]; set<char>st; for(int i=0;i<n;i++)st.insert(s[i]); for(auto itr=st.begin();itr!=st.end();++itr)dict2[*itr].push_back(*itr); int t; char a,b; cin >> t; for(int q=0;q<t;q++){ cin >> a >> b; if(a==b)continue; for(int i=0;i<dict2[a].size();i++){ dict2[b].emplace_back(dict2[a][i]); dict[dict2[a][i]]=b; } dict2[a].clear(); } for(int i=0;i<n;i++)cout << dict[s[i]]; cout << endl; return 0; }
D問題 Square Pair
素因数分解して、それぞれの因数の個数を2で割ったときのあまりが完全に等しい値同士をかけてあげると平方数になります。
あと０は何をかけても平方数になることに注意です。
https://atcoder.jp/contests/abc342/submissions/50588801#include <bits/stdc++.h> using namespace std; vector<pair<long long, long long> > prime_factorize(long long N) { vector<pair<long long, long long> > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({a, ex}); } // 最後に残った数について if (N != 1) res.push_back({N, 1}); return res; } int main() { int n; cin >> n; vector<long long>a(n); for(int i=0;i<n;i++)cin >> a[i]; map<vector<long long>,long long>dict; set<vector<long long>>st; vector<long long>ans; long long count=0; for(int i=0;i<n;i++){ if(a[i]==0){ count+=1; continue; } ans.clear(); vector<pair<long long,long long>>num=prime_factorize(a[i]); for(int ipp=0;ipp<num.size();ipp++){ if(num[ipp].second%2==0)continue; ans.emplace_back(num[ipp].first); } sort(ans.begin(),ans.end()); if(st.count(ans)==0){ st.insert(ans); dict[ans]=1; } else dict[ans]++; } long long ans2=0; for(auto itr=st.begin();itr!=st.end();++itr){ if(dict[*itr]==1)continue; ans2+=dict[*itr]*(dict[*itr]-1)/2; } if(count>=1){ ans2+=(n-count)*count; } if(count>=2)ans2+=count*(count-1)/2; cout << ans2 << endl; return 0; }
E問題 Last Train
後ろからダイクストラをすればよいです。
本番でペナをつけずに一発で通せて嬉しかったです。
#include <bits/stdc++.h> using namespace std; int main() { int n,m,a; cin >> n >> m; vector<vector<long long>>train; vector<vector<int>>graph(n); vector<long long>hako2; for(int i=0;i<m;i++){ hako2.clear(); for(int ipp=0;ipp<6;ipp++){ cin >> a; hako2.emplace_back(a); } train.push_back(hako2); graph[hako2[5]-1].emplace_back(i); } vector<long long>amount(n,-1); amount[n-1]=4e18; int iti=0,hako; priority_queue<pair<long long,int>>prq; prq.push(make_pair(2e18,n)); while(prq.size()>0){ hako=prq.top().second; prq.pop(); for(int i=0;i<graph[hako-1].size();i++){ hako2=train[graph[hako-1][i]]; if(amount[hako-1]<hako2[0]+hako2[3])continue; if(amount[hako2[4]-1]>=min(hako2[0]+(hako2[2]-1)*hako2[1],(amount[hako-1]-(amount[hako-1]-hako2[0]-hako2[3])%hako2[1])-hako2[3]))continue; amount[hako2[4]-1]=min(hako2[0]+(hako2[2]-1)*hako2[1],(amount[hako-1]-(amount[hako-1]-hako2[0]-hako2[3])%hako2[1])-hako2[3]); prq.push(make_pair(amount[hako2[4]-1],hako2[4])); } } for(int i=0;i<n-1;i++){ if(amount[i]==-1)cout << "Unreachable" << endl; else cout << amount[i] << endl; } return 0; }
僕の提出
https://atcoder.jp/contests/abc342/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=rotti
