ABC185参戦記

はじめに

2020年12月13日21:00-22:40　ABC185に参戦しました。
62分12秒　4完ノーペナで2734位 /7478人中　パフォーマンス897でレーティングは+11の798となりました。

前回ARCで茶落ちしており、今回は緑復帰を目指すもわずかに足りませんでしたが手応えのあった回でした。

A問題

４つの値のminをとる問題です。
普通に書いて１分１３秒。

B問題

B - Smartphone Addiction

よく見るアルゴリズム問題。
スマートフォンのバッテリーが減っていき、カフェにいる間は充電できる、という設定です。
バッテリーはフル充電以上には充電できないことに気を付けます。
テストケースが親切でした。

１０分５８秒（通算１３分１１秒）はちょっとゆっくり目だったか。

C問題

C - Duodecim Ferra

よくある場合の数の問題ですがまともに計算するとすぐにオーバーフロー。
計算の工夫をしてオーバーフローを回避するのが正しそうですが思いつかず、ちょっと後ろめたさを感じつつも多倍長を使ってAC。

pythonなどで書く人のことを考えると遠慮なく多倍長を使ってもいいように思います。
また、せっかくpythonの基礎を勉強したのでpythonで書いてみるというトライもあったかも。

１８分２４秒（通算３０分３５秒）はこれものんびりですが、コンビネーションの計算を思い出しながら組むのと一度オーバーフローではまって手間取りました。

D問題

解法はすぐに見えましたが実装に手間取りました。
とくにブロック列の最初と最後のところの処理にちょっと試行錯誤がありました。

最小の空隙を捜し、空隙の長さをまとめた配列をつくり、各空隙を埋めるのに必要なスタンプ回数を求めて加算してAC。やってることはそんなに難しくないので、どれだけスムーズにとけるかが勝負だと思います。

３３分３７秒（通算６４分１２秒）はこれも時間がかかりましたが、ACできたので満足です。
もう１０分縮められればパフォ９５０くらいで余裕で入緑してましたが、これが今の実力だということでしょう。

ACしたコード

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M;
  cin>>N>>M;
  if(M==0){
    cout<<1<<endl;
    return 0;
  }
  if(M==N){
    cout<<0<<endl;
    return 0;
  }  
  vector<int>def;
  int A[M];
  for(int i=0;i<M;i++){
    cin>>A[i];
  }
  sort(A,A+M);
  
  int temp=0;
  int mindef=1000000000;
  for(int i=0;i<M;i++){
    if((A[i]-temp-1<mindef) && (A[i]-temp != 1)){
      mindef=A[i]-temp-1;
    }
    temp=A[i];
  }
  //cout<<N<<" "<<A[M-1]<<" "<<mindef<<endl;
  
  if((N+1-A[M-1] != 1) && (N-A[M-1]<mindef)){
    mindef=N-A[M-1];
  }
  //cout<<mindef<<endl;
  temp=0;
  for(int i=0;i<M;i++){
    if(A[i]-1-temp != 0){
      def.push_back(A[i]-temp-1);
      //cout<<A[i]-temp<<"##"<<endl;
    }
    temp=A[i];   
  }
  if(N+1-A[M-1] !=1){
    def.push_back(N+1-A[M-1]-1);
  }
    
  int ans=0;  
  for(auto itr=def.begin();itr != def.end();itr++){
    ans+=((*itr+mindef-1)/mindef);
    //cout<<*itr<<endl;
  }
  
  //cout<<mindef<<endl;
  cout<<ans<<endl;
 
  return 0;
}

E問題

編集距離のDPに似てるなと思いつつ、DPを詰め切れず解けませんでした。

F問題

手をつけられませんでしたがセグ木を使えるようになればそのままの典型のようです。
年内にセグ木のライブラリの使い方はマスターする予定なので、加算、乗算、min,max,gcd,lcm,xorなどの典型的な関数は退治できるようになるつもりです。