AtCoder ABC170 反省会 [A,B,C,D完, E追記]

こんにちは。ABC170でした。

↑意気込み

↑謎の予言

（追記：Eも解けたので良ければ見ていってください

o-treetree.hatenablog.com

）

A

1:37で提出

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

int main(){
  vector<int> x(5);
  for(int i=0; i<5;i++)cin>>x[i];
  for(int i=0; i<5; i++){
    if(x[i]==0){
      cout<<i+1<<endl;
      return 0;
    }
  }
}

これ、$x = \{0,0,0,0,0\}$ みたいなのって制約でハジけるんすかね、まあええわ

（追記：問題文の「変数 $x_i$ には整数 $i$ が代入されていました。」を誤読してた。操作前 $x = \{1,2,3,4,5\}$ か。）

B

与えられた変数 $X,Y$ がつるかめ算の（動物数, 足の数）としてありえる値かどうか判定するという問題

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

int main(){
  int x,y;cin>>x>>y;
  for(int turu = 0; turu<=100; turu++){
    for(int kame = 0; turu+kame<=100; kame++){
      if(turu+kame==x && 2*turu+4*kame==y){
        cout<<"Yes\n";
        return 0;
      }
    }
  }
  cout<<"No\n";
}

冒頭の予言により全探索する覚悟ができていたので全探索しました。

C

入力 $X$ に最も近い整数を、数列 $p$ 以外の整数から選ぶ問題

x = 6
p = {4 7 10 6 5}

ans = 8

i	1	2	3	4	5	6	7	8	9	10
選択可能	o	o	o	x	x	x	x	o	o	x

選択可能な中で6に一番近いのは8。

（等距離の数字があれば小さい方を選択（↑で4も選択可能だったら4を出力））

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

int main(){
  map<int, int> mp;
  int X,N;cin>>X>>N;
  for(int i=0; i<N; i++){
    int f;cin>>f;mp[f]++;
  }
  int i,j;
  i=j=X;
  while(1){
    if(mp.find(i)==mp.end()){
      cout<<i<<endl;
      break;
    }
    if(mp.find(j)==mp.end()){
      cout<<j<<endl;
      break;
    }
    i--;j++;
  }
}

選択不可の数をmapで管理したけど、ふつうにvector<bool>でよかったな

探索を $i=j=X$ から初めて、$i$ は小さく、$j$ は大きくして見ていく

D

数列Aの各A[i]について、Aの他の要素でA[i]を割り切るものがないのをカウントする

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()

long long divisor(long long n, vector<long long> &d){
  long long cnt = 0;
  for(long long i=1; i*i<=n; i++){
    if(n%i==0){
      d.push_back(i);
      if(i*i!=n){
        d.push_back(n/i);
      }
      cnt++;
    }
  }
  return cnt;
}

int main(){
  int N;cin>>N;
  vector<int> A(N);
  map<int,int> mp;
  for(int i=0; i<N; i++){
    cin>>A[i];
    mp[A[i]]++;
  }
  sort(all(A), greater<int>()); //ここ要らなかった

  int cnt = N;
  for(int i=0; i<N; i++){
    int s = A[i];

    if(mp[s]>1){
      cnt--;
      continue;
    }

    vector<long long> d;
    divisor(s,d);

    for(auto x: d){
      if(x==s)continue;
      if(mp.find(x)!=mp.end()){
        cnt--;
        break;
      }
    }
  }

  cout<<cnt<<endl;
}