「オフラインリアルタイムどう書くF06の問題 - ツリーの中の数」の解答

http://nabetani.sakura.ne.jp/hena/ordf06numit/

はじめて勉強会に参加しました。
一時間という制限のなか、問題の理解に10分以上。。
そして何もひねることもできず、再起呼び出しでリミット寸前になんとか終わりました。

Javaで、メモ化なしとメモ化ありです。

速度は圧倒的にメモ化の勝利。

* メモ化なし：total time= 801[msec]
* メモ化あり：total time= 59[msec]

### メモなし

```
package nabetani01;
public class Test01 {

	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		/*0*/ test( "123,4", "5" );
		/*1*/ test( "1,1", "1" );
		/*2*/ test( "2,1", "1" );
		/*3*/ test( "3,3", "1" );
		/*4*/ test( "19,5", "1" );
		/*5*/ test( "69,5", "3" );
		/*6*/ test( "88,9", "2" );
		/*7*/ test( "1,100", "0" );
		/*8*/ test( "100,4", "4" );
		/*9*/ test( "101,9", "0" );
		/*10*/ test( "456,7", "7" );
		/*11*/ test( "567,8", "12" );
		/*12*/ test( "756,10", "10" );
		/*13*/ test( "789,10", "12" );
		/*14*/ test( "896,29", "2" );
		/*15*/ test( "7764,6", "664" );
		/*16*/ test( "1234,56", "3" );
		/*17*/ test( "8563,29", "35" );
		/*18*/ test( "12345,67", "10" );
		/*19*/ test( "72927,51", "263" );
		/*20*/ test( "71441,145", "22" );
		/*21*/ test( "123456,78", "397" );
		/*22*/ test( "123456,789", "1" );
		/*23*/ test( "592741,216", "55" );
		/*24*/ test( "913826,584", "81" );
		/*25*/ test( "1234567,89", "2293" );
		/*26*/ test( "10000000,1", "19383507" );
		/*27*/ test( "12345678,9", "3567354" );
		/*28*/ test( "6215879,358", "2907" );
		/*29*/ test( "12345678,90", "79419" );
		/*30*/ test( "5745432,1032", "1287" );
		long end = System.currentTimeMillis();

		System.out.printf("total time= %d[msec]\n", end - start);

	}

	private static void test(String question, String ans)
	{
		long start = System.currentTimeMillis();

		String strs[] = question.split(",", 0);
		int parent = Integer.parseInt(strs[0]);
		int target = Integer.parseInt(strs[1]);
		int answer = Integer.parseInt(ans);

		int result = 0;
		result = countTarget(parent, target);

		long end = System.currentTimeMillis();
		System.out.printf("[%s]%d, %d, result = %d, answer = %d, %d[msec]\n",
				result == answer ? "OK":"NG", parent, target, result, answer, end - start);
	}

	private static int countTarget(int parent, int target)
	{
		int result = 0;

		if (parent == target)
			return result++;

		int rh, lh;
		rh = parent / 2 - 10;
		lh = parent * 2 / 3;

		if (rh > 0)
		{
			if (rh == target)
				result++;
			else if (rh > target)
				result += countTarget(rh, target);
		}

		if (lh > 0)
		{
			if (lh == target)
				result++;
			else if (lh > target)
				result += countTarget(lh, target);
		}

		return result;
	}
}
```

### メモあり

```
/**
 *
 */
package nabetani01;
import java.util.HashMap;
import java.util.Map;

public class Test02 {
	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		/*0*/ test( "123,4", "5" );
		/*1*/ test( "1,1", "1" );
		/*2*/ test( "2,1", "1" );
		/*3*/ test( "3,3", "1" );
		/*4*/ test( "19,5", "1" );
		/*5*/ test( "69,5", "3" );
		/*6*/ test( "88,9", "2" );
		/*7*/ test( "1,100", "0" );
		/*8*/ test( "100,4", "4" );
		/*9*/ test( "101,9", "0" );
		/*10*/ test( "456,7", "7" );
		/*11*/ test( "567,8", "12" );
		/*12*/ test( "756,10", "10" );
		/*13*/ test( "789,10", "12" );
		/*14*/ test( "896,29", "2" );
		/*15*/ test( "7764,6", "664" );
		/*16*/ test( "1234,56", "3" );
		/*17*/ test( "8563,29", "35" );
		/*18*/ test( "12345,67", "10" );
		/*19*/ test( "72927,51", "263" );
		/*20*/ test( "71441,145", "22" );
		/*21*/ test( "123456,78", "397" );
		/*22*/ test( "123456,789", "1" );
		/*23*/ test( "592741,216", "55" );
		/*24*/ test( "913826,584", "81" );
		/*25*/ test( "1234567,89", "2293" );
		/*26*/ test( "10000000,1", "19383507" );
		/*27*/ test( "12345678,9", "3567354" );
		/*28*/ test( "6215879,358", "2907" );
		/*29*/ test( "12345678,90", "79419" );
		/*30*/ test( "5745432,1032", "1287" );

		long end = System.currentTimeMillis();

		System.out.printf("total time= %d[msec]\n", end - start);

	}

	private static void test(String question, String ans)
	{
		long start = System.currentTimeMillis();

		String strs[] = question.split(",", 0);
		int parent = Integer.parseInt(strs[0]);
		int target = Integer.parseInt(strs[1]);
		int answer = Integer.parseInt(ans);

		Map<Integer, Integer> cache = new HashMap<>();
		int result = 0;
		result = countTarget(parent, target, cache);

		long end = System.currentTimeMillis();
		System.out.printf("[%s]%d, %d, result = %d, answer = %d, %d[msec]\n",
				result == answer ? "OK":"NG", parent, target, result, answer, end - start);
	}


	private static int countTarget(int parent, int target, Map<Integer, Integer> cache)
	{
		int result = 0;

		if (cache.containsKey(target))
			return cache.get(target);

		if (parent == target)
			return result++;

		int rh, lh;
		rh = parent / 2 - 10;
		lh = parent * 2 / 3;

		if (rh > 0)
		{
			if (rh == target)
				result++;
			else if (rh > target)
				result += countTarget(rh, target, cache);
		}

		if (lh > 0)
		{
			if (lh == target)
				result++;
			else if (lh > target)
				result += countTarget(lh, target, cache);
		}

		cache.put(target,  result);
		return result;
	}
}

```