Codeforces #279 Div.2 – C. Hacking Cypher

Tatsuya Yatagawa

2014-11-23

Codeforces #279 (Div.2)のCが結構いい問題だと思ったので備忘録的に解説します。

問題

最大100万桁ある数が与えられる。この数をどこかの桁で左右に2つに分割した時に、前側の数がaで、後側の数がbで割り切れるようにしたい。ただし、分割した後の数は先頭に0を含んではいけない。もし、そのような分割があれば、その答えを、なければ-1を出力せよ。

解法(間違い)

ものすごく単純に考えると、前後の数を多倍長でもって、その都度剰余を計算すればよさそうです。

とっても頭が弱い私は「あぁ、多倍長演算めんどいなぁ。Rubyでやろw」といって、以下のコードをSubmitします。

s = STDIN.gets.strip
t = STDIN.gets.split(" ");
a = t[0].to_i
b = t[1].to_i

m = s.length
dig = 1
for i in 1..m-1
  dig = dig * 10
end

ok = false

aa = 0
bb = s.to_i
while dig != 1
  tmp = bb / dig
  bb -= tmp * dig
  aa = aa * 10 + tmp
  dig = dig / 10

  if bb / dig == 0
    next
  end

  if aa % a == 0 and bb % b == 0
    puts("YES")
    puts(aa)
    puts(bb)
    ok = true
    break
  end
end

if not ok
  puts("NO")
end

まぁ、普通に小さい入力だったら問題なく動作するわけですが、1時間ほど経って、何者かにHackされてしまう…

よくよく考えると、剰余を求める計算の計算量を厳密に捉えれば上のコードの計算量はO(N^2)のオーダーになるためTLEすることに気づきます。

解法 (本物)

じゃあどうするかというと、余りだけが分かればいいので、あらかじめ与えられた数と10の累乗のbでの剰余を計算しておいて、逐一、前側の数のaでの剰余と後側の数のbでの剰余を更新していってあげればよいことが分かります。

言葉で言ってもわかりづらいので、以下のコードを見てください。最後の文字出力のところが分かりづらいかもですが、コピーしていると時間の無駄なので、こっちの方が早いです(無駄な努力)。


#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

typedef long long lint;
typedef pair<lint,lint> pll;

string s;
lint a, b;

lint dig[1000011];

void solve() {
    lint aa = 0;
    lint bb = 0;
    dig[0] = 1;
    int n = s.size();
    REP(i,n) {
        bb = (bb * 10 + (s[i] - '0')) % b;
        dig[i+1] = (dig[i] * 10) % b;
    }

    REP(i,n-1) {
        aa = (aa * 10 + (s[i] - '0')) % a;
        bb = (bb - ((s[i] - '0') * dig[n-i-1]) % b + b)  % b; 
        if(s[i+1] == '0') continue;
        if(aa == 0 && bb == 0) {
            printf("YES\n");
            int c = s[i+1];
            s[i+1] = '\0';
            printf("%s\n", s.c_str());
            s[i+1] = c;
            printf("%s\n", s.c_str()+(i+1));
            return;
        }
    }
    printf("NO\n");
}

void coding() {
    while(cin>>s) {
        cin>>a>>b;
        solve();
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("c.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}