B - Big Integers

• Quiz
  • https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_b
• AC
  • https://atcoder.jp/contests/nikkei2019-final/submissions/20052741
• 解説
  • 公式editorialがアッサリしすぎなので書く
  • 制約を見ると、A<K, B<Kです。K=10とすると、Aは0～9までしか出ない
  • K^Nが大きすぎるのでそれを直接求めるのを避けたい
  • A1, B1を見て差を取り、dと置く。次にA2, B2の差を取るが、dをK倍して持ち越す。A2, B2でどう頑張っても、前段で発生した差dを逆転する差は生み出せないので、次数の多い方から係数を比較するだけでいい

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M,K;
    cin>>N>>M>>K;

    ll ma = max(N,M);

    VI A;
    rep(i,ma-N)A.push_back(0);

    VI B;
    rep(i,ma-M)B.push_back(0);

    rep(i,N){
      ll a;cin>>a;
      A.push_back(a);
    }

    rep(i,M){
      ll b;cin>>b;
      B.push_back(b);
    }

    // 終了関数
    auto x = [](){
      p("X");exit(0);
    };
    auto y = [](){
      p("Y");exit(0);
    };

    rep(i,ma){
      if(A[i]>B[i])y();
      if(A[i]<B[i])x();
    }
    p("Same");
   
    return 0;
}