2021/04/06

概略

今日は新卒の方と懇親会? みたいなのがありました. PJの闇を多く語り過ぎた気もする.

昨日からエヴァの過去映画を見始めているが, なるほどわからん.

今日の競プロ

本日もランダムなりて

今日はABC192D Base n

整数Xがmax_element(X)より大きなN進数で解釈した場合にM以下の何種類の数字として読めるかを求める物

Xが1桁の場合は進数によらず数値はXのため, XがM以下かどうかで1 / 0 分岐のみ, 2桁以上の場合は, 進数ごとに値が確実に異なるため, 実質的に「条件に合うN進数でXを解釈した時に値がM以下になる進数の数」が解答になる.

2桁以上の場合は最上位桁が0ではない制約があるので, Nは単調増加. よって二分探索が使える.

それぞれのNについてN進数で解釈してM以下になるかを検証していけばok.

2桁かつ最上位桁が1の場合でもM+1進数ではMを超えるので, 上限はM+1で十分. ちなみに初め上限を1e+18 + 1にして落ちた. この記法結構使っていたのだけれど, よくよく考えればdoubleの有効桁数は15桁くらいのはずなので, 19桁 + 1すると確かに計算誤差が凄い. 10000....0LLとかなら通る. 気をつけよう.

オーバーフローしないよう, 値の確認は割り算で.

submit result (書き終えてから気付いたけどaccumulateのlambdaの中charじゃないな...)

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

int main(){
  string xs;
  ll m;
  cin >> xs >> m;
  int n = xs.size();

  // 面倒なので数値に直しておく
  vector<ll> x(n);
  for(int i=0; i<n; i++) x[i] = xs[i] - '0'; 

  // 1桁の場合比較で完結
  if(x.size() == 1){
    cout << (x[0] <= m ? 1 : 0) << endl;
    return 0;
  }

  ll d = *max_element(x.begin(), x.end());

  // にぶたん
  ll lp = d, rp = m + 1;
  while(rp - lp > 1) {
    ll mid = (rp + lp) / 2;
    ll result = accumulate(x.begin(), x.end(), 0LL, 
      [m, mid](ll acc, char cur) {
        return (acc > (m - cur) / mid ? m + 1 : acc * mid + cur);
      });
    if(result > m) rp = mid;
    else lp = mid;
  }
  cout << lp - d << endl;
}