ABC195(パナソニックプログラミングコンテスト）参戦記

はじめに

2021年3月13日21:00-22:40に開催されたABC195(パナソニックプログラミングコンテスト）に参戦しました。
結果は43分38秒ACDの３完で2202位/7679人中、パフォ―マスは1014でレーティングが前回894から+13の907となりhighestを更新しました。

A問題

A問題らしいA問題。HがMの倍数かどうかを判定します。
丁寧にサンプルも確認して1分48秒で提出。

B問題

時間内に解けませんでした。
全探索だろうとあたりはついたのですが，難しく考えすぎてしまったかも知れません。
10分近く悩んで見切りをつけてC問題に進みましたが飛ばして正解でした。

あとで戻ってきて更に30分ほど考察しましたが正答に至らず。
コンテスト終了後、解説をみてなるほどでした。

C問題

1～10^15以下の数までを３ケタ毎にコンマ区切りで書いた場合にコンマの総数を求める問題。
大きい方から順に足していく解法がすぐに見えました。
通算18分42秒。

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

int main(){
  ll n;
  cin>>n;
  ll ans=0;
  if(n==1000000000000000){
    ans+=5;
    n--;
  }
  if(n>=1000000000000){
    ans+=(n-999999999999)*4;
    n=999999999999;
  }
  if(n>=1000000000){
    ans+=(n-999999999)*3;
    n=999999999;
  }  
  if(n>=1000000){
    ans+=(n-999999)*2;
    n=999999;
  }
  if(n>=1000){
    ans+=(n-999);
  }  
  cout<<ans<<endl;
}

D問題

D - Shipping Center

箱に荷物を入れていく問題。
クエリでｌ～rまでの箱が使えない場合があります。
貪欲法で、価値が最大の荷物を入れられるもっとも小さい使っていない箱に入れる、でよさそうです。

クエリで出てくる使えない箱は、大きさ０にすることで表現しました。
使った箱の大きさも０にします。
もとの箱の大きさを配列xでもち，クエリ毎にyにコピーして使います。
ちょっと時間はかかりましたが破綻なく実装し切れてよかったです。
通算43分38秒。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;

//int v[50];
//int w[50];
int x[50];
int y[50];//クエリ作業用
int main(){
  int n,m,q;
  cin>>n>>m>>q;
  vector<P>vec;
  rep(i,n){
    int w,v;
    cin>>w>>v;
    vec.push_back({v,w});
  }
  sort(vec.begin(),vec.end());
  /*for(auto e:vec){
    cout<<e.first<<" "<<e.second<<endl;
  }*/

  rep(i,m) cin>>x[i];
  int ans=0;
  //クエリ
  rep(i,q){
    ans=0;
    int l,r;
    cin>>l>>r;
    l--;
    r--;
    for(int j=0;j<m;j++){
      if(l<=j && j<=r){
        y[j]=0;
      }
      else{
        y[j]=x[j];
      }
    }
    sort(y,y+m);
    for(int k=n-1;k>=0;k--){
      for(int l=0;l<m;l++){
        if(vec[k].second<=y[l]){
          ans+=vec[k].first;
          y[l]=0;
          break;
        }
      }
    }
    cout<<ans<<endl; 
  }
}
    

E問題

10分ほど考えましたが解法を思いつきませんでした。
７の倍数は末尾の数字を消してその２倍を消した数から引いた数も７の倍数、みたいなのをぐぐって見つけましたがどう使っていいのかもわからず。

一つ上に行くにはこのレベルをきちっと解けるようにならないとダメだと思います。

終わりに

今回はB問題が解けなかったのが悔しかったですが，B問題が解けていてもパフォーマンスの差はわずかでした。
Dが解けたのは最近取り組んでいるcodeforcesでの精進による実装力強化の成果だと思います。

幸い停滞していたレートも緩やかに上昇を始めています。
水色を視野に入れて、基礎を固めつつ、Ｅ問題以降が解けるような力をつけていきたいと思います。