ABC180(2020/10/17)参戦記
はじめに
2020年10月17日20:00から開催されたABC180に参戦しました。
結果は１５分０５秒ノーペナ３完で2760/5748位。
パフォーマンス676でレートは-13となり794となって茶落ちしました。
A問題
簡単な引き算足し算の問題です。
念のため丁寧にサンプル通してAC。
１分１０秒はまずまずでした。
B問題
N次元空間内の点が与えられ，原点との間のマンハッタン距離，ユークリッド距離，チェビシェフ距離を求める問題です。
チェビシェフ距離とかいう聞いたことのない距離がでてきましたが，定義が書いてあるのでそのとおりに実装するだけです。ユークリッド距離だけ実数タイプなので誤差に気をつけました。
これも丁寧にサンプルを確認し７分４２秒（本問６分３２秒）でAC。まずまずでした。
C問題
N個のシュークリームを分割することなく平等に分けられる人数を出力する問題です。
シンプルな約数列挙でした。
制約が10e12と大きいですがi*i<=nで剰余を確認し割れる場合はペアになる数も拾うようにすれば余裕で間に合います。
最後に昇順で出力することや平方数の場合を考えてmapを使って実装。
この辺はだいぶ身についてきたなという気がします。
１５分０５秒（本問７分２３秒）でAC。そこそこのペースでペナなく３問解けてこの時点の推定パフォが１０００を超えていてほくほくしていました。
ACしたコード
#include <bits/stdc++.h> using namespace std; int main(){ long long n; cin>>n; map<long long,int>mp; for(long long i=1;i*i<=n;i++){ if(n%i==0){ mp[i]++; mp[n/i]++; } //cout<<i<<endl; //cout<<n/i<<endl; } for(auto itr=mp.begin();itr != mp.end();itr++){ cout<<itr->first<<endl; } return 0; }
D問題
今回のはまりがD問題でした。
問題はもとの数XにAをかける操作とBを足す操作のいずれかの操作をYを超えない範囲で何回できるか，というものです。X,Yがいずれも10e18までの制約で，サンプルにもわざわざオーバーフローに気をつけてください，と書いてあったのにオーバーフローではまりました。
オーバーフローに気をつけるのか，型をlong longにしとけばいいね，とだけ考えてしまったのが間違いでした。
愚直に実装してサンプルでTLEだったので，次にかける場合はせいぜい３０～４０回までなのでその回数を超えていたらあとは足すことにするアルゴリズムとか，Aをかけた結果とBを足した結果を比較して足した結果の方が多かったら，あとは割り算して残り回数をだしてやる，といったアルゴリズムでやりましたがいずれもWAやTLE。
WAはわかるのですがどうしてTLEがまざっているのか，ここをしっかり考えるべきでした。
WAしたコード
#include <bits/stdc++.h> using namespace std; int main(){ long long x,y,a,b; cin>>x>>y>>a>>b; long long fort=x; long long exp=0; while(fort<=y){ if(fort*a <= (fort+b)){ fort*=a; } else{ exp+=(y+b-fort-1)/b; cout<<exp-1<<endl; return 0; } exp++; //cout<<exp<<" "<<fort<<endl; } cout<<exp-1<<endl; return 0; }
このコードでばぐっていたのはここでした。
if(fort*a <= (fort+b)){
fort*=a;
}
強さfortは10e18に近い数の場合があり，aの制約も10e9までなので掛け合わせるとlong long でもオーバーフローします。そしてオーバーフローした場合，エラーにならず負の数とか適当な数が返ってくるのがやっかいなところです
結局，テストケースによっては，このfortがオーバーフローしてwhile文の判定がいつまでも真のままでループが回りTLEになるのがわかりました。TLEにならないケースもオーバーフローしているとWAになります。
ACしたコード
コンテストが終わったあとツイッターのTLでオーバーフローの話題を見て上記に気づき，コードを修正。オーバーフロー判定をかませてACできました。
#include <bits/stdc++.h> using namespace std; int main(){ long long x,y,a,b; cin>>x>>y>>a>>b; long long fort=x; long long exp=0; while(fort<=y){ if(fort*a <= (fort+b) && y/fort>a){ fort*=a; } else{ exp+=(y+b-fort-1)/b; cout<<exp-1<<endl; return 0; } exp++; //cout<<exp<<" "<<fort<<endl; } cout<<exp-1<<endl; return 0; }
D問題の反省
このオーバーフローの問題は，競プロに必要な力を①数学，②アルゴリズム，③コンピューターサイエンスの３つにわけると，計算誤差などの問題と同じく③コンピューターサイエンスの力を求められる問題です。この部分ではまって冷える経験はこれまで何度も繰り返してきました。
改めてこの点に気づかせてくれた今回の経験をしっかり活かしたいと思います。
E問題
D問題ではまりつづけていてひょっとしたら解けないかなと思ってE問題をのぞいてみました。
最近よく目にする巡回セールスマン問題です。
コストが珍しいですが，コストだけ計算していれてやるとそこらから拾ってきたアルゴリズムで解けそうな気がしました。
都市１からスタートし，というのもどこから回っても経路としては同じなので気にしなくてよさそうです。
実際には，経路の入力で詰まって（有方向なので逆も入れなければならないところに気づかず）解ききれませんでしたが，うまくすると解けた可能性があるなと思いました。
記念提出してWAしたコード
あとちょっと改善するとればACできそう。
#include<bits/stdc++.h> using namespace std; int X[300],Y[300],Z[300]; struct Edge { int dst,weight; }; int TravelingSalesmanProblem(int V,int E,vector<int> s,vector<int> t,vector<int> d) { vector<vector<Edge> > G(V); vector<int> cost(V,INT_MAX); cost[0] = 0; for(int i=0;i<E;++i) { G[s[i]].push_back((Edge){t[i],d[i]}); if( t[i] == 0 ) { cost[s[i]] = min(cost[s[i]],d[i]); } } vector<vector<int> > dp((1<<V),vector<int>(V,INT_MAX)); dp[1][0] = 0; for(int state=0;state<(1<<V);++state) { for(int cur=0;cur<V;++cur) if( dp[state][cur] != INT_MAX ) { for(int i=0;i<(int)G[cur].size();++i) { Edge &e = G[cur][i]; if( (state>>e.dst) & 1 ) continue; dp[state|(1<<e.dst)][e.dst] = min(dp[state|(1<<e.dst)][e.dst], dp[state][cur]+e.weight); } } } int mini = INT_MAX; for(int i=0;i<V;++i) if( dp[(1<<V)-1][i] != INT_MAX && cost[i] != INT_MAX ) { mini = min(mini,dp[(1<<V)-1][i]+cost[i]); } return (mini!=INT_MAX)?mini:-1; } int main() { int V,E; cin>>V; for(int i=0;i<V;i++){ cin>>X[i]>>Y[i]>>Z[i]; } E=V*(V-1); vector<int> s(E), t(E), d(E); int cnt=0; for(int i=0;i<V;++i) { for(int j=i+1;j<V;j++){ s[cnt]=i; t[cnt]=j; d[cnt]=abs(X[j]-X[i])+abs(Y[j]-Y[i])+max(0,Z[j]-Z[i]); cnt++; } } cout << TravelingSalesmanProblem(V,E,s,t,d) << endl; return 0; }
ACしたコード
辺の数Eを２倍にして逆の辺についてコストをいれてみたらすんなりACしました。
これも落ち着いてやれば時間内に書けてたなあ。
#include<bits/stdc++.h> using namespace std; int X[300],Y[300],Z[300]; struct Edge { int dst,weight; }; int TravelingSalesmanProblem(int V,int E,vector<int> s,vector<int> t,vector<int> d) { vector<vector<Edge> > G(V); vector<int> cost(V,INT_MAX); cost[0] = 0; for(int i=0;i<E;++i) { G[s[i]].push_back((Edge){t[i],d[i]}); if( t[i] == 0 ) { cost[s[i]] = min(cost[s[i]],d[i]); } } vector<vector<int> > dp((1<<V),vector<int>(V,INT_MAX)); dp[1][0] = 0; for(int state=0;state<(1<<V);++state) { for(int cur=0;cur<V;++cur) if( dp[state][cur] != INT_MAX ) { for(int i=0;i<(int)G[cur].size();++i) { Edge &e = G[cur][i]; if( (state>>e.dst) & 1 ) continue; dp[state|(1<<e.dst)][e.dst] = min(dp[state|(1<<e.dst)][e.dst], dp[state][cur]+e.weight); } } } int mini = INT_MAX; for(int i=0;i<V;++i) if( dp[(1<<V)-1][i] != INT_MAX && cost[i] != INT_MAX ) { mini = min(mini,dp[(1<<V)-1][i]+cost[i]); } return (mini!=INT_MAX)?mini:-1; } int main() { int V,E; cin>>V; for(int i=0;i<V;i++){ cin>>X[i]>>Y[i]>>Z[i]; } E=V*(V-1); vector<int> s(E*2), t(E*2), d(E*2); int cnt=0; for(int i=0;i<V;++i) { for(int j=i+1;j<V;j++){ s[cnt]=i; t[cnt]=j; d[cnt]=abs(X[j]-X[i])+abs(Y[j]-Y[i])+max(0,Z[j]-Z[i]); s[cnt+E]=j; t[cnt+E]=i; d[cnt+E]=abs(X[j]-X[i])+abs(Y[j]-Y[i])+max(0,Z[i]-Z[j]); cnt++; } } cout << TravelingSalesmanProblem(V,E*2,s,t,d) << endl; return 0; }
２度目の色落ちしてみて
今回も前回緑化時に続き，緑になった次のratedで茶落ちし緑コーダーは１回天下?でした。
色が変わると落ちた～って感じがしますね。
残念で悲しいことですが，人はレートのみに生きるにあらず（マタイ ４：４）。
コンテストで冷えてレートが下がるなら，それは適正レートです。
今回はD問題が解けていれば緑に踏みとどまれたことがわかっています。D問題が解けないのは，まだまだ基本ができていないことのあらわれです。
順位表を見ると緑ではD問題を落としているひとはぽつぽつ見かけますが，水以上では４人だけです。こうしてみると色が実力を保証する機能はちゃんと確保できていて，実力の足りない人が落とされるのは仕方のないことだと思います。
こういう弱点を１つづつ潰して安定してパフォーマンスを出せるようになりたいです。レートが落ちるのは，また，色変をともなってレートが落ちるのは悲しいことですし，２回目の茶落ちとなるとなおさらではありますが，くさることなく楽しみながら競技を続けたいと思います。
囲碁の段みたいに一度色がついたら下向きには色が変わらないようにしてくれるといいのになとは思いますが。
