poj 2602 Superlong sums 2007/09/16 2007/09/16

Superlong sums
Cozy Ozy - Superlong sums(0)
Super_long_sums

はじめ、読み取った数字をStringBuilderにアペンドして最後にそれをBigIntegerにして計算させていました。
自分で実行させてみて計算できたので、submitしたのですが、やはりだめ。

問題文には、「1<=N<=1000000」とあるので、実験してみて、たしかに「1<=N<=1000000」な文字列からBigIntegerに直すにはそれなりのコストがかかっているようだったので、はじめのアイデアはボツ。


思いつかなかったので、shortcoderな方のサイトをみていて、char[]の配列を使っていたので、なんとなくその方向性でいくことにした。

変なところで、はまったのは問題文には、「the length of their sum does not exceed N」とあったことに気がつかず、足したら桁が増えるということを気にしてコードを書いていたこと。

最後に、Time Limit Exceededがでるようになった。で、悩んだあげく、Scannerを使っていたのをやめて、StreamTokenizerを使用したら、ようやくacceptedされた。

無駄な部分が多々ありますが、とりあえずコード。

コードは三つのパートに分かれてます。
１。入力読み取り
２。計算
３。出力のためにStringBuilderにつめてます。

package p2602;

import java.io.IOException;
import java.io.StreamTokenizer;

public class Main {
public static void main(String[] args) throws IOException {

//Scanner scanner = new Scanner(System.in);
StreamTokenizer tokenizer = new StreamTokenizer(System.in);
tokenizer.nextToken();
int n = (int)tokenizer.nval;

byte[] bs = new byte[n];
for (int i = 0; i < n; i++) {
tokenizer.nextToken();
int i1 = (int)tokenizer.nval;
tokenizer.nextToken();
int i2 = (int)tokenizer.nval;
bs[i] = (byte) (i1+ i2);
}

for (int i = bs.length - 1; 0 < i; i--) {
if (1 <= ((int) bs[i] / 10)) {
bs[i - 1]++;
bs[i] = (byte) ((int) bs[i] % 10);
}
}

StringBuilder sb = new StringBuilder();
for (int b : bs) {
sb.append(b);
}

System.out.println(sb);
}

}