ABC194参戦記　2021/3/6 - chacoderのブログ

はじめに

2021年3月6日21:00-22:40に開催されたABC194に参戦しました。
結果は82:20 4完 3WA 2333位/ 7892人中　パフォーマンス1003でレーティングは882から+12の894となりhighestを更新しました。

f:id:chacoder:20210307095605p:plain

f:id:chacoder:20210307095948p:plain

A問題

A - I Scream

無脂乳固形分と乳脂肪分が与えられ乳固形分と乳脂肪分の割合により分類されるアイスクリーム類の分類をする問題です。

誤読しやすい問題ですがサンプルをちゃんと試せばＯＫ。
Ａ問題としては難しめの印象でした。

4分25秒。

B問題

B - Job Assignment

２つの仕事を誰にさせると最短でできるかを求める問題。

同じ人がやる場合には２つの仕事にかかる時間の合計時間がかかり(Ａi+Ｂi）、別の人がやる場合には、それぞれの人がかかる時間の長い方（max(Ai,Bj)）がかかります。

少し悩みましたがＮが１０００以下なので全探索でやるのがあっさりです。
同じ人が担当する場合と別の人が担当する場合で計算式を変えて最小時間を更新するようにします。

これもＢ問題としては難し目に感じました。

7分36秒　通算12分01秒

提出コード

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

int main(){
  int n;
  cin>>n;
  int a[n];
  int b[n];
  rep(i,n){
    cin>>a[i]>>b[i];
  }
  int mintemp=200000;
  rep(i,n) rep(j,n){
    if(i != j){
      mintemp=min(mintemp,max(a[i],b[j]));
    }
    else{
      mintemp=min(mintemp,a[i]+b[j]);
    }
  }
  cout<<mintemp<<endl; 
  return 0;
}

C問題

C - Squared Error

長さＮの数列Ａの各要素同士の差の二乗の和を求める問題です。
Ｎが最大3×10^5なのでＯ（Ｎ^２）ではTLEしそうです。

サンプルを見ながら式変形を考えました。
(A-B)^2=A^2+B^2-2*AB
なので，前の部分は各要素の二乗で計算できます。

後ろの部分は更に式変形すると　ある要素にその要素以外の要素の和を掛けたもの　の和を２倍すればよいことに気づきました。
これを前の部分から引きます。

すぐに解法が見えてしめしめとおもっていましたが，実装するとサンプルが合わなくて悩みました。

いろいろ考えても全然合わないので，血迷って１回TLE必至の愚直実装を提出しましたが当然TLEに。

あらためてＮ＝５のサンプルを手計算と比較しながら見直して間違いに気づきました。
前半部分をＮ＝３のサンプルから二乗の和の２倍と計算していたのが間違いでした。Ｎ－１倍すれば合います。

かなりもたつきましたがむしろ解ききれてよかったという気持ちの方が大きかったです。

32分14秒　通算44分15秒 1WA

提出コード

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

int main(){
  int n;
  cin>>n;
  ll a[n];
  ll sum=0;
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  ll ans=0;
  rep(i,n){
    ans+=(a[i]*a[i]);
  }
  ans*=(n-1);
  rep(i,n){
    ans-=(a[i]*(sum-a[i]));
  }
  cout<<ans<<endl;
  return 0;
}

D問題

D - Journey

頂点１にいる高橋君がN個の頂点にランダムに辺を張っていく場合にグラフが連結になるのに必要な操作回数の期待値を求める問題です。

この手の問題は見た目は怖いけどシンプルな問題が多く怖がらずにやろうと思いました。

最初はサンプルから計算式を考えましたがなかなか合わずにWA2連発。
ぐぐってガチャをコンプするのに必要な回数の期待値を発見してクリアーしました。
最初頂点１にいるので１引くのがポイント。

23分05秒 2WA　通算67分20秒 3WA

提出コード

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

int main(){
  int n;
  cin>>n;
  double ans=0;
  for(int i=1;i<=n;i++){
    ans+=(double)(1.0)/i;
  }
  ans*=(double)n; 
  cout<<setprecision(18)<<ans-1<<endl;
  return 0;
}