AtCoder ABC169 反省会 [A,B,D,E完]

こんにちは。ABC169でした。

感想

なんでぇ？

それでは、振り返っていきましょう。スピード重視の雑解説(?)です。

A

やるだけ。33秒で提出できました。

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

int main(){
  int A,B;cin>>A>>B;
  cout<<A*B<<endl;
}

B

一度は後回しにしたが無理やり通した。配列Aとは別に、log10(A)の配列Bを用意した。

とりあえず掛け算に0があれば0を出力して終わる
longlong と、log10とで同時に計算して、Bの和logansが18を越えていたらAの積ansも10¹⁸を越えるので-1を出力して終わる
ただ、たとえば ans = 10¹⁸ +1 のとき、誤差の問題でlogans=18となって通過してしまうので（そのくらいならlonglongでオーバーフローはしていないので）愚直に10¹⁸ との比較で落とす
全て通過すればそのままansを出力

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define all(v) (v).begin(), (v).end()

const ll m = 1000000000000000000;

int main(){
  int N;cin>>N;
  ll ans = 1;
  vector<ll> A(N);
  vector<double> B(N);
  for(int i=0; i<N; i++){
    cin>>A[i];
    B[i] = log10(A[i]);
  }
  if(find(all(A), 0) != A.end()){
    cout<<0<<endl;
    return 0;
  }
  double logans = 0;
  for(int i=0; i<N; i++){
    ans *= A[i];
    logans += B[i];
  }
  if(logans > 18){
    cout<<-1<<endl;
    return 0;
  }
  if(ans > m){
    cout<<-1<<endl;
    return 0;
  }
  cout<<ans<<endl;
}

C

なぜWA？後回し

（23:23追記）

浮動小数点の誤差の問題だったそうです。

僕の解答WA

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

int main(){
  ll A;
  double B;
  cin>>A>>B;
  ll ANS = A * (ll)(B*100);
  cout<<ANS/100<<endl;
}

なんで通らないんだ？と思っていたのですが、B*100のところが競プロ的に「雑」だったということらしく、詳しくは↑の記事を見てもらえばいいのですが、まあそういうことで。

AC

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

int main(){
  ll A;
  double B;
  cin>>A>>B;
  ll ANS = A * (ll)((B+0.00001)*100);
  cout<<ANS/100<<endl;
}

今度からはこの手には引っかからんぞ！！！！！

（追記おしまい）

D

手をつけて15分しないで解けてる。

まず、Nを素因数分解します。例えば N = 1728 = 2⁶ * 3³ を考えると

2 2 2 2 2 2 3 3 3

とばらして、各素数ごとに1個、2個、と取り去っていく回数が答えです。

[2] [2 2] [2 2 2] [3] [3 3]

という感じで、5回に分けてとっていけるので N＝1728について答えは5です。素因数分解する関数を既に持っていたのでそれを流用してサクッと解けました。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ff first
#define ss second

  /*
  判定する数:n
  素因数分解の結果を格納する:l
  返り値:素因数の数
  */
long long prime_fac(long long n, vector<pair<long long, long long> >&l){
  long long s = floor(sqrt(n));
  long long r;
  pair<long long, long long> x;
  for(long long i=2; i<=s; i++){
    if(n%i==0){
      r=0;
      do{
        r++;
        n /= i;
      }while(n%i==0);
      x = make_pair(i, r);
      l.push_back(x);
    }
  }

  if(n>s){
    x = make_pair(n, 1);
    l.push_back(x);
  }

  return l.size();
}

ll counter(ll n){
  ll ans = 0;
  for(ll i=1; i<=n; i++){
    n -= i;
    ans++;
  }
  return ans;
}

int main(){
  ll N;cin>>N;
  vector<pair<long long, long long> >l;
  prime_fac(N, l);

  ll ans = 0;
  for(pair<long long, long long>x: l){
    ans += counter(x.ss);
  }
  cout<<ans<<endl;
}

vector<pair<long long, long long> >lには、(素因数, 指数) の組が入ります。

1728を素因数分解した時は

{ pair(2, 6), pair(3, 3) } のようになる（イメージ）。

E

これも手をつけてから15分しないで解けている。

AとBをそれぞれ数列に入れ、ソートすることで「下限の数列」と「上限の数列」がわかります。

それぞれ中央値を求めると「中央値の下限」と「中央値の上限」がでて、下限から上限まで

Nが奇数だったら1刻みで
Nが偶数だったら1/2刻みで

全ての値を取れる（気がした）のでそのまま実装したらACになりました。証明はしてない。

（23:40追記）公式解説pdfに、全部の値を取れるって書いてありました。良かった。https://img.atcoder.jp/abc169/editorial.pdf（追記終わり）

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

using vi = vector<int>;
#define all(v) (v).begin(), (v).end()

int main(){
  int N;cin>>N;
  vi A(N);
  vi B(N);
  for(int i=0; i<N; i++){
    cin>>A[i];
    cin>>B[i];
  }

  sort(all(A));
  sort(all(B));

  int L,R;
  if(N%2==1){
    L = A[N/2];
    R = B[N/2];
    cout<<( R-L+1 )<<endl;
  }else{
    L = A[N/2] + A[N/2-1];
    R = B[N/2] + B[N/2-1];
    cout<<( R-L+1 )<<endl;
  }
}

Cが解けたら追記します。おしまい。

おはやし日記

テーマ……バイク←プログラミング←旅

AtCoder ABC169 反省会 [A,B,D,E完]

感想

A

B

C

D

E