ABC188参戦記 - chacoderのブログ

はじめに
A問題
B問題
C問題
- 提出コード
D問題
- 考察
- 提出コード
E問題
感想など
息子に抜かれたこと

f:id:chacoder:20210111113136p:plain

f:id:chacoder:20210111113244p:plain

はじめに

2021年1月10日 21:00-21:40 ABC188に参戦しました。

atcoder.jp

結果は92分51秒　４完１ペナ　2618位／7831人中でパフォーマンス949
レーティングは前回より+16の814となり５度目の入緑を果たしました。

A問題

バスケットボールで現在X：Yの得点のとき劣勢の方が３ポイントシュートを決めて逆転優勢になれるかという問題です。

丁寧に実装してサンプルを通し２分でAC。

B問題

２次元ベクトルの内積が０になるかどうかを判定する問題。
Nの制約が＜＝１０００００、個別の要素の積は１００＊１００以下で１００００までなのでINT型で間に合います。

３分２４秒（通算５分２４秒）で提出しAC。

ゆっくり目ですがつまらないミスでペナルティを出さないようにすることを優先しています。
後半の考察で相当時間をとられるので、今のところはA問題やB問題あたりで多少時間をかけることは気にしないようにしています。

C問題

C - ABC Tournament

トーナメント戦の準優勝者を求める問題。
２つの山のMAXをとり，少ない方（準優勝者）のIDを特定する２段階で解答を出します。

問題文を正確に理解するのにちょっと手間取りましたが、気づけば簡単です。

８分１４秒（通算１３分３８秒）でAC。

エスティメーターみるとこのあたりで推定パフォ１１００ぐらいが出ててちょっと嬉しかったですが、後半が解けないとずるずる下がってぬか喜びになりがちなので、気を引き締めて先に進みます。

提出コード

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()

int main(){
  int N;
  cin>>N;
  int n=pow(2,N);
  int A[n];
  rep(i, n) cin>>A[i];
  int maxa=0;
  int maxb=0;
  rep(i, n/2){
    maxa=max(A[i],maxa);
  }
  for(int i=(n/2);i<n;i++){
    maxb=max(A[i],maxb);
  }
  int num=min(maxa,maxb);
 rep(i, n){
   if(A[i]==num){
     cout<<i+1<<endl;
     return 0;
   }
 }
  return 0;
}

D問題

D - Snuke Prime

よくありがちな問題ですが制約がとても大きいのでどんな工夫をすべきか悩みました。
途中、あきらめかけましたが、必ず解けると信じて最後まで粘れたのがよかったです。

考察

　日数が10^9と非常に長いので普通に配列に収納することすらできません。

　最初に考えたのは，i番目のサービスについて期間の総日数からすぬけプライムを使う日数分を引いた期間にCiを乗じてトータルをだし，最後にすぬけプライムを使う日数にCを乗じたコストを足す，という方針です。この方針は結局詰まって解ききれませんでしたが考える方向はよくて次につながりました。

　そこでひらめいたのはあるサービスについて使い始めた日以降はトータルのコストがCi増え，使い終わった翌日にはトータルのコストがCi減るので，各日のコストをtempとして各サービスの開始及び終わりに+Ci -Ciを入力した配列を準備することでした。

　コストの変更が生じるイベント毎に，各日のトータルコストtempがCを上回る場合にはCを乗じ，その他の場合にはtempを乗じます。

　vectorで実装したところサンプルが通ったので提出したところWA。
　同じ日に複数のイベントが発生した場合にバグるようです。

　そこで，同じ日に複数のイベントが発生した場合に新たなvectorに集約することを考えましたがなかなかうまくいきません。いろいろ試しているうちにイベントの発生する日をキーにするのだからmapを使えばいいのではないか，とひらめき，mapで実装。

　ACできました！

提出コード

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
const ll MOD=1000000007;

int main(){
  ll n,c;
  cin>>n>>c;
  ll A[n];
  ll B[n];
  ll C[n];
  rep(i, n)cin>>A[i]>>B[i]>>C[i];
  vector<pair<ll,ll>>P;
  rep(i, n){
    P.push_back({A[i],C[i]});
    P.push_back({B[i]+1,-C[i]});
  }
  sort(all(P));
  ll temp=0;
  ll pre=0;
  map<ll,ll>mp;
  for(auto e:P){
    mp[e.first]+=e.second;
  }
  /*for(auto e:mp){
    cout<<e.first<<" "<<e.second<<endl;
  }
  */
    
  //すぬけ発動期間を考えながら金額を計算
  pre=0;
  ll ans=0;
  for(auto e:mp){
    if(pre==e.first) continue;
    //cout<<e.first<<" "<<e.second<<" "<<temp<<endl;    
    if(temp>=c){
      ans+=(c*(e.first-pre));
    }
    else{
      ans+=(temp*(e.first-pre));
    }
    temp+=e.second;
    pre=e.first;
  }
  cout<<ans<<endl;
  return 0;
}