精進日記といいつつ精進記事を生やしたことがなかったので書いてみます
今回は4完59分(1ペナ)でちょい冷えでした
コードや解法が間違っていたらぜひ指摘してください
A - Red or Not
条件分岐するだけですね
提出コード
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int a;
string s;
cin>> a >> s;
if(a>=3200) cout << s << endl;
else cout << "red" << endl;
}ところで珍しく早解きできてA提出時点で7位でした
この後はもう見どころがありません（かなしいね）
Aの早解きだけ珍しく成功してるｗ
— ボンド@競プロ (@bond_cmprog) 2019年8月18日
Bondo416's replay of AtCoder Beginner Contest 138
最大瞬間風速は 7位 (00:38, abc138_a AC) だよ！https://t.co/7356oB8tes#AtCoder_Replay pic.twitter.com/Ja9FFFYSiU
B - Resistors in Parallel
一瞬頭がこんがらがりましたが，分母を足していって最後にそれを逆数にするというふうにしました
提出コード
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
double ans = 1;
double sum = 0;
REP(i,N){
double a;
cin >> a;
sum += 1/a;
}
sum = 1 / sum;
printf("%.8lf\n",sum);
}C - Alchemist
ぱっと見貪欲法っぽそう
要素を全部プライオリティキューに入れて，小さい順に2つ取ってからその結果をまたキューに入れるみたいにやりました
ソートして取っていくだけでもいいみたいです
提出コード(プライオリティキュー版)
提出コード(ソート版)
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
priority_queue,greater> pq;
REP(i,N){
double v;
cin >> v;
pq.push(v);
}
while(pq.size() != 1){
double x = pq.top(); pq.pop();
double y = pq.top(); pq.pop();
pq.push((x+y)/2);
}
double ans = pq.top();
printf("%.8lf\n",ans);
} D - Ki
最初見た瞬間よくわからなくて，途中オイラーツアーとかをググっていました（ア）
AC数が多かったので愚直にDFSでクエリを処理して投げるとTLEしたので
ぐっと睨むと各頂点に加算しておいて最後にDFSで累積和っぽく伝搬させるとOKでした
ところでコンテスト中は有向辺だと思いこんでいて投げたら通りました（嘘）
問題文はちゃんと読もうね（反省）
提出コード(コンテスト後修正)
vector<vector<int>> G;
vector<ll> sum(202020);
void dfs(int v, int p, ll s){
sum[v] += s;
for(auto nv : G[v]){
if(nv == p) continue;
dfs(nv,v,sum[v]);
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N,Q;
cin >> N >> Q;
G.resize(N);
REP(i,N-1){
int a,b;
cin >> a >> b;
--a,--b;
G[a].push_back(b);
G[b].push_back(a);
}
REP(i,Q){
int p,x;
cin >> p >> x;
--p;
sum[p] += x;
}
dfs(0,-1,0);
REP(i,N) cout << sum[i] << " ";
cout << endl;
}E - Strings of Impurity
Dで時間かけてしまったため，コンテスト中は通せなかった
コンテスト後ガリガリ実装してると無事AC
Tを前から順に見ていってSにおける今いるindex(cur)と次の文字のindex(next)で答えを加算していくみたいな感じです
curよりも後にnextがあればそのまま取れば良くて
curよりも前にnextがあったらSを継ぎ足していくことになるので，|S| - curとnextを足していくみたいにやりました
インデックスを愚直に調べるとTLEするので二分探索で調べると間に合います
提出コード
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
string S,T;
cin >> S >> T;
vector> idx(26);
REP(i,S.size()){
idx[(S[i]-'a')].push_back(i+1);
}
ll ans = 0;
int cur = 0;
REP(i,T.size()){
if(idx[T[i]-'a'].size() != 0){
int next_idx = upper_bound(idx[T[i]-'a'].begin(),idx[T[i]-'a'].end(),cur) - idx[T[i]-'a'].begin();
int next;
if(next_idx == idx[T[i]-'a'].size()){
next = idx[T[i]-'a'][0];
ans += (int)S.size() - cur;
cur = next;
ans += cur;
}
else{
next = idx[T[i]-'a'][next_idx];
ans += next - cur;
cur = next;
}
}
else{
cout << -1 << endl;
return 0;
}
}
cout << ans << endl;
} おわりに
今回のDが2000人，Eが1250人くらい通していて人々強いなあという感想
こういう早解き回になるとパフォ取れないがちなので頑張りたいね
