おはやし日記

特にテーマ無しの日記。

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;
}

数列Aを、配列の他にmapでも保持。divisor(n,d)は $n$ の約数を配列 d に入れる関数。

  • カウントを N にしておく
  • A[i]が2つ以上あったらカウントから外す(cnt--)。
  • A[i]の約数リストdを見て、約数 $x$ がA[i]自身だったら無視して
    • その他の数列Aの要素(map保持)に $x$ が入っていたらカウントから外す。

まとめ

DまでAC出たので満足しました。

Eはなんか解ける気せんし。

(追記:Eもなんかいけるみたいなことtwitterで見るし後でやってみます)

プライバシーポリシー ・お問い合わせはこちら