ARC105参戦記 - chacoderのブログ

f:id:chacoder:20201012094203p:plain

はじめに
A問題
- 提出コード
B問題
- ACしたコード
C問題以下
まとめ

はじめに

2020年10月11日22:30からARC105に出場しました。

ABの２完　１ペナ　1593/3806位　パフォ979でレーティングは21あがって807に。
４回ぶりに再入緑しhighestを更新しました。

f:id:chacoder:20201012094259p:plain

A問題

４つの数を２つに分割した際に分割されたそれぞれの数が等しい場合があるかという問題です。

さすがにARCでA問題からそこそこ骨があります。
４つの数から１つもしくは２つを選ぶ組み合わせなので実質７通りしかなく，すべて書き出す方針でACしました。回答時間５分２８秒はまあまあでした。

提出コード

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

int main(){
  long long A[4];
  for(int i=0;i<4;i++){
    cin>>A[i];
  }
  if(A[0]==A[1]+A[2]+A[3] || A[1]==A[0]+A[2]+A[3] ||A[2]==A[1]+A[0]+A[3] ||A[3]==A[1]+A[2]+A[0] ){
    cout<<"Yes"<<endl;
    return 0;
  }
  if(A[0]+A[1]==A[2]+A[3] || A[0]+A[2]==A[1]+A[3] ||A[0]+A[3]==A[2]+A[1]){
    cout<<"Yes"<<endl;
    return 0;
  }    
  cout<<"No"<<endl;
  return 0;
}

B問題

B - MAX-=min

複数毎のカードがあり最大値と最小値が等しい場合は終了，そうでない場合は，最大値から最大値と最小値の差を引いた数で最大値を置き換える，ということを繰り返し最後に残る数を出力する問題です。

愚直にシミュレーションしてTLEたたいたのは余計でした。
大きい数から小さい数を引いて大きい方と入れ替える，というのはユークリッドの互除法です。

GCDとることに気づいてサンプルケースを通しAC。１３分１秒＋１ペナ。

ACしたコード

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

int main(){
  int N;
  cin>>N;
  int A[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  if(N==1){
    cout<<A[0]<<endl;
    return 0;
  }
  
  sort(A,A+N);
  int ans=A[0];
  for(int i=0;i<N;i++){
    ans=gcd(ans,A[i]);
  }
  cout<<ans<<endl;

  return 0;
}