yukicoder No.539 インクリメント

解くのに3時間くらいかかったが、得られたものはそこそこあった。

この問題、一見すると最後尾の整数を1増やせばいいだけのように思えるが、実際はもっと複雑な解法を要求されている。コードの中で一つ一つ解説する前に、大まかな攻略方針を示したいと思う。

1．文字列を後ろから1文字ずつ探索していき、処理が終わればStringBuilderにappendする。最後にそれをreverseして出力。最初はinsert(0,a)を使って先頭に詰め込んでいたが、これだと処理が遅すぎてTLEしてしまう。
2．最後尾の整数が9未満であれば、それを1増やすだけでよく、以降は何も変更せずただ出力すればよい。
3．最後尾の整数が9のとき、これが問題である。
3-1．そこで、最後尾の整数が9であったなら、値を0に変更し、変数incrementにtrueを保持する。
3-2．次の値が9未満であれば、それを1増やして処理終了。もしまた9であるなら、値を0に変更する。
4．このようにして処理すべき整数部分（hoge999hogeの999の部分）に繰り上げ処理を施していって、もし処理すべき整数部分が終了したなら、そこへ1を付け加える。hoge999hogeの例でいくと……
　e - eg - ego - egoh　とこうなって
　egoh0　とここで繰り上げ処理が入る。incrementにtrueを保持する。
　egoh00
　egoh000
　egoh000[1]e　
5．探索中の文字がeになった、つまり処理すべき部分が終わったので、incrementにtrueが保持されているなら、1をeの前に余計にappendしてやる。
6．以上。以下に貼りつけるコードは、大まかにいうとこのような処理の流れになっている。

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		sc.nextLine();
		//繰り上げ処理用変数
		boolean increment = false;
		//下3つは条件分岐用の変数、うまくやればいくらかは省略できそう
		boolean isFinished; //繰り上がり処理が終わったかどうかを管理する
		boolean isFirst; 
		boolean isSearch; //処理すべき整数部分かどうかを管理する探索用変数
		StringBuilder ans = new StringBuilder();
		
		//メインループ
		for (int i=0; i<n; i++) {
			//char型配列でやらないと時間制約が厳しい
			char[] ar = sc.nextLine().toCharArray();
			isFinished = false;
			isFirst = true;
			isSearch = false;
			
			//メイン処理
			for (int j=ar.length-1; j>=0; j--) {
				
				//探索中の文字が数字ならこっち
				if ('0'<=ar[j] && ar[j]<='9') {
					
					//整数の処理が終わっている場合は実行しない
					if (isFinished==false) {
						
						//探索中の文字は初めて登場する整数か、という分岐。
						if (isFirst==true) {
							
							//9ならば、すでに述べた繰り上がり処理を行う。
							//繰り上がり処理を行うということは、探索が続くということなので、
							//繰り上がり処理用変数と探索用変数をfalseにしない
							if (ar[j]=='9') {
								increment = true;
								ar[j] = '0';
								isSearch = true;
							}
							
							//9未満であれば処理終了。
							//ただし、整数部分はまだ終わらない可能性があるので、
							//探索用変数はfalseにしない。繰り上がり処理用変数はfalseにする。
							else {
								ar[j]++;
								increment = false;
								isFinished = true;
							}
							
							//最初の文字についての処理はこれで終了。
							isFirst = false;
						}
						
						//次、処理すべき整数部の初め以外の部分。
						else if (isFirst==false) {
							
							//2文字目以降も9だった場合は、繰り上がり処理を続ける。
							//もし「aaa19999aaa」という文字列であれば、
							//この部分は3回実行される。
							//aaa1[999]9aaa←ここ。
							if (ar[j]=='9') {
								ar[j] = '0';
							}
							
							//incrementを抱えたまま9未満の整数を発見できた場合は、
							//繰り上がりが処理できる。それがこの部分。
							//aaa[2]0000aaa←こうなる。
							//同時に、処理も終了。
							else if (ar[j]<'9') {
								ar[j]++;
								increment = false;
								isFinished = true;
							}
						}
						
						//取って付けた箇所。
						//処理すべき整数部が9のみからなる文字列「999aaa」とかだと、
						//処理が上手くいかなかったので。
						//先頭の1文字を処理した時点でincrementを抱えているとき、
						//つまり処理すべき整数部が先頭にありその先頭が9だった場合、
						//01をつけてbreakさせる。10でないのは、
						//文字列をあとでreverse()するため。
						//たとえば上の例を処理する場合、「aaa00」でここに差し掛かり、
						//「aaa0001」となって出て行く。
						if (j==0 && increment==true) {ans.append("01"); break;}
					}
				}
				
				//探索中の文字が数字以外で、かつ、整数の処理が終わっている場合
				//サンプル2のhoge999hogeでいくと、hog[e]999hoge、このeでここが実行される
				else {
					if (isSearch==true) {
						isFinished = true;
						isSearch = false;
						if (increment==true) {
							ans.append(1);
						}
					}
				}
				
				//処理が終わった文字を出力用変数にくっつける
				ans.append(ar[j]);
			}
			ans.reverse();
			out.println(ans);
			ans.setLength(0);
		}
	}
}