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

はじめに

2020年12月19日21:00-22:40 パナソニックプログラミングコンテスト(ABC186）に参戦しました。

結果は34:50 ノーペナ４完で2197/6238位、パフォーマンス961でレーティングは前回798から+18の816となりhighestを更新して４度目の入緑を果たしました。

前回に続いてそこそこ手応えのある問題を無難な時間に解くことができてよかったです。

A問題

単純な割り算です。

B問題

グリッドの数字を最小の数字にあわせるのに必要な数を求めます。
グリッドの数字のsumから最小の数字にグリッド数を乗じた数を引きます。
シンプルですが基本が詰まっててよい問題だなと思いました。
テストケースをしっかり確認し4分33秒、通算5分29秒。

C問題

10進数で7が入っているかどうかは10でmodをとることと10で割ることを繰り返して判定し、8進数では8でmodをとることと8で割ることを繰り返して判定します。

少しもたつきましたが6分37秒、通算12分6秒。

提出コードを展開

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

int main(){
  int N;
  cin>>N;
  int cnt=0;
  for(int i=1;i<=N;i++){
    int temp=i;
    int flag=0;
    while(temp){
      if(temp%10==7){
        flag=1;
        break;
      }
      temp/=10;
    }
    if(flag) continue;
    temp=i;
    while(temp){
      if(temp%8==7){
        flag=1;
        break;
      }
      temp/=8;
    }
    if(flag) continue;
    cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}

D問題

素直に実装すると20万×20万=400億でTLEが見えています。
累積和をとることを考えましたが値が正整数でなく絶対値をとる点に悩みました。

テストケースをいじりながら考察すると結局全通りの組み合わせを加算していることに気づきました。降順に並び替えた上、累積和を使ってACできました。

これを比較的早い時間に気づけたのは運がよかったのかもしれません。

提出コードを展開

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

int main(){
  int N;
  cin>>N;
  vector<long long>A(N,0);
  long long S[N];
  long long sum=0;
  for(int i=0;i<N;i++){
    cin>>A[i];
    sum+=A[i];
  }
  sort(A.begin(),A.end(),greater<long long>());
  S[0]=sum;
  for(int i=0;i<N-1;i++){
    S[i+1]=S[i]-A[i];
  }
  
  long long ans=0;
  for(int i=0;i<N-1;i++){
    ans+=(abs(S[i+1]-A[i]*(N-1-i)));
  }
  cout<<ans<<endl;  
  return 0;
}

E問題

いろいろ考察しましたが解ききれませんでした。
全探索は間に合わず一次不定方程式を立てて解くのも正解までたどり着けませんでした。
まだまだ数学力が不足しているなと思います。

F問題

こちらも考察するだけ考察しました。

横に進み縦に進むのと、縦に進み横に進むので到達可能な場所を数えるところまではできそうです。
しかし両者が重なる部分の数え方を思いつきませんでした。

しかし、そんな遠いところにあるわけではなく、今いるところからちょっと背を伸ばせば手が届きそうなところにあるように感じました。

終わりに

ABC185に続き得意なセットでレーティングをあげて４度目の入力を果たすことができましたが、E問題、F問題には手が出ず伸びしろはまだまだあります。

これまで３回の入力はいずれも次のコンテストで冷えて茶に転落しているので、まずは緑安定を目指し、そして更に上を目指したいと思います。