ABC164振り返り

ABC164の振り返りをします。

結果はこんな感じで、レートが少し冷えてしまいました。

幸いABCはほぼ毎週あるので、できることを増やしていき挽回していきたいです(´･ω･`)

コンテスト中

A-Cを9分台で解き終わりました。

C問題

mapを利用すれば簡単にかけます。

D問題

90分以上あったものの正しい解法にたどり着けなかったです。
問題自体はわかりやすく、おそらく典型問題だと思ったので焦っていました。

色々sampleでためし、結局後ろからnけたの2019でのあまりが0の時の回数を求めて終わってしまいました。

コンテスト後

F問題は難しそうなのでD,E問題に関して

D問題

D - Multiple of 2019

下の位からn桁が0の時に2019で割った時のあまりを求める。
それをmapを用いて保存しながら被ったら、これまで登場した分足していけば良い

気づけば単純な操作でこれができなかったのは相当敗北感

// 前処理
 rep(i,N){
   ll d = st[i] - '0';
   c[i] = d * modpow(10 , N-i-1 , 2019);
   c[i] %= 2019;
   // cout<<c[i]<<endl;
 }
 vector<ll> t(N);
 t[0] = c[N - 1];
 repn(i,N-1){
   t[i] = t[i - 1] + c[N - i - 1];
   t[i] %= 2019;
   // cout<<t[i]<<endl;
 }

 ll ans = 0;
 ll tmp = 0;
 map<ll,ll> m;
 m[0]++;
 for(ll i = N-1 ; i >= 0; i--){
   if(m[t[i]]){
     ans += m[t[i]];
   }
   m[t[i]]++;
 }

E問題

E - Two Currencies

銀貨の意味ある保有枚数がせいぜい2500枚以下なので、銀貨の枚数ごとに違う頂点だと認識してグラフを作成すれば良い。

頂点数VはN*2500, 辺の数EはM*2500 + N*2500なのでDijkstra法を利用することで計算量O(ElogV)で最短経路を得ることができる。

struct Edge {
   ll to;
   ll cost;
   Edge(ll t, ll w) : to(t), cost(w) { }
};

using Graph = vector<vector<Edge> >;
ll d[MAX];
Graph G(MAX);

void dijkstra(ll s) {
   fill(d, d + MAX, 1e18);
   d[s] = 0;  // 始点sへの最短距離は0

   priority_queue<P, vector<P>, greater<P> > que;  // 距離が小さい順に取り出せるようgreater<P>を指定
   que.push(P(0, s));
   while (!que.empty()) {
       P p = que.top();
       que.pop();
       ll v = p.second;  // 更新した頂点の中で距離が最小の頂点v
       if (d[v] < p.first) {
           continue;
       }
       for (auto e : G[v]) {  // 頂点vから出る辺eを走査
           if (d[e.to] > d[v] + e.cost) {
               d[e.to] = d[v] + e.cost;
               que.push(P(d[e.to], e.to));
           }
       }
   }
}


int main(){
 ll N,M,S;cin>>N>>M>>S;

 // 銀貨の数それぞれに関して違う頂点を考える

 rep(i,M){
   ll from, to , mar , weight;
   cin >> from >> to >> mar >>weight;
   rep(j,2500){
     // jは保有している銀貨の枚数
     if(mar > j) continue;
     else{
       G[from * 2500 + j].pb(Edge(to * 2500 + j - mar , weight));
       G[to * 2500 + j].pb(Edge(from * 2500 + j - mar , weight));
     }
   }
 }
 // 銀貨を増やすプロセスについての経路を作る
 repn(i,N){
   ll to, weight;
   cin >> to >> weight;
   rep(j,2500){
     if( ( j + to) >= 2500) continue;
     G[i * 2500 + j].pb(Edge(i * 2500 + j + to , weight));
   }
 }

 if(S >= 2500) S = 2499;
 dijkstra(1 * 2500 + S);

 //check
 /*
 repn(i,N){
   rep(j,10){
     cout<<d[i*2500 + j]<<" ";
   }
   cout<<endl;
 }
 */

 // ans出力
 for(ll i = 2; i <= N; i++){
   ll ans = 1e18;
   rep(j, 2500){
     ans = min(ans , d[i * 2500 + j]);
   }
   cout<<ans<<endl;
 }
}

次回もあるよ^ ^