ABC169振り返り

takoagemat

2020年6月3日 01:00

ABC169の振り返りをします。

結果は73分A-E5完6ペナでレートが上がりました。

double型の精度に関する知識はあったはずなのですが、C問題でハマってしまいました。
しっかり原因を特定もしてないのにたくさん提出してペナルティをうけるのは得策ではないですね(´ω`)

引き続き精進していきたいところです。

コンテスト中

A問題

掛け算します。

int main(){
 ll a ,b; cin >> a >> b;
 cout << a * b << endl;
}

B問題

こちらも掛け算ですが、10^(18)を優に超える場合があり、その処理をうまくする必要があります。
0が存在する場合にも注意ですね。
1回WAを出してしまいました。

自分のコンテスト中の解法はだいぶ汚いのでリンクを載せておきます。

それぞれの掛け算で10^(18)を超えるかどうかは移項して商を考えることでオーバーフローすることなく計算できます。

int main(){
 ll N; cin >> N;
 vector<ll> a(N); rep(i,N) cin >> a[i];

 ll ans = 1;
 SORT(a);
 if(a[0] == 0){
   cout << 0 << endl;
   return 0;
 }
 rep(i,N){
   if(a[i] > (ll)1e18 / ans){
     cout << -1 << endl;
     return 0;
   }
   ans *= a[i];
 }
 cout << ans << endl;
}

C問題

この問題も掛け算ですが、浮動小数点に関する知識を問われる問題です。
当然有限なメモリを利用しているので、double型で誤差は出るはずです。

2進法なので0.1なども割り切れない話なども聞いたことはありました。
知っていたはずなのですが、しばらく気付きませんでした。
色々試行錯誤している間に45 * 1.13の出力が間違っていることに気付きACすることができました。

int main(){
 ll a; double b; cin >> a >> b;

 ll nb = b * 100.01;
 // cout << nb << endl;
 ll ans = a * nb;
 // cout << ans << endl;
 ans /= 100;
 cout << ans << endl;
}

D問題

正整数Nを出来るだけ多くの操作で割っていきたいという問題です。

まず、24に関してやってみると2,3,4で割ると3回の操作で1になります。

出来るだけ小さい値で割りたいので素数で割りたいという発想になりました。

素因数分解してその素因数では何回操作を実行できるかを考えていけばACできました。

int main(){
 map<ll,ll> m;
 ll N; cin >> N;
 for(ll i = 2; i * i <= N ; i++){
   while(N % i == 0){
     m[i]++;
     N /= i;
   }
 }
 if(N != 1) m[N]++;

 vector<ll> a(50);
 rep(i,50){
   a[i] = (i) * (i + 1) / 2;
 }

 ll ans = 0;
 for(auto p : m){
   // cout << p.fi << " " << p.sc << endl;
   ans += POSL(a,p.sc);
   ans --;
   if(p.sc == a[POSL(a, p.sc)]) ans++;
 }
 cout << ans << endl;
}

E問題

中央値の可能な範囲についての問題です。

中央値の下限と上限について別々に考えます。

Nが奇数の時は簡単で、中央値の下限は下限の中央値で、中央値の上限は上限の中央値になります。

中央値を下限の中央値より小さくすることはできず、中央値を上限の中央値より大きくすることはできないです。
また、下限の中央値以上、上限の中央値以下の値には必ずすることができます。

Nが偶数の時の同様の方法で考えました。

違うのは中央値の下限を下限の中央値の2倍、上限を上限の中央値の2倍として考えました。
合計が違えば、2で割った値も違うので十分なはずです。

int main(){
 ll N; cin >> N;
 vector<ll> a(N); vector<ll> b(N);
 rep(i,N) cin >> a[i] >> b[i];

 SORT(a); SORT(b);
 ll ans = 0;
 // 奇数の時は簡単、それぞれの真ん中の点の時の間の数の個数
 if(N % 2 == 1){
   ll d = a[N / 2];
   ll u = b[N / 2];
   ans = u - d + 1;
   if(ans < 0) ans = 0;
 }
 else{
   ll dd = a[N / 2 - 1];
   ll du = a[N / 2];
   ll ud = b[N / 2 - 1];
   ll uu = b[N / 2];
   ll nd = (dd + du);
   ll nu = (uu + ud);
   ans = nu - nd + 1;
   if(ans < 0) ans = 0;
 }
 cout << ans << endl;
}

コンテスト後

F問題

もう少しC問題を速く解き終えていたら解けたんじゃないかと思いました。

dpで今までの合計値に対する選び方の総数を更新していくことで解けました。

dpでメモリを無駄に使わないために、いらなくなった数値を消しながらdpするのにも慣れてきました。

ll dp[2][MAX];
// 和について何通りの選び方があるのか保存しとく

int main(){
 ll N , S; cin >> N >> S;
 vector<ll> a(N); rep(i,N) cin >> a[i];
 ll ans = 1;
 dp[0][0] = 1;
 rep(i,N){
   // 選ばない場合
   rep(j,S + 1){
     dp[1][j] = 2 * dp[0][j];
     dp[1][j] %= MOD;
   }
    // 選ぶ場合
    rep(j,S + 1){
      if(j + a[i] > S) continue;
      else{
        dp[1][j + a[i]] += dp[0][j];
        dp[1][j + a[i]] %= MOD;
      }
    }
    // 入れ替え
    rep(j , S + 1){
      dp[0][j] = dp[1][j];
    }
 }
 // rep(i,S) cout << i << " " << dp[0][i] << endl;
 cout << dp[0][S] << endl;
}

アドバイスなどあればぜひお願いします。

よろしければ少額でもサポートお願いします。サポートの費用対効果は抜群です。