AtCoder Beginner Contest115 D - Christmasがわからない

Question

以下のコードのpati関数が何をしているのかがいまいち理解できません。
例えば、
else if(x<=1+layer[n-1])return pati(n-1,x-1);
とありますが、ここでの返り値はどのような演算を行なっているのでしょうか？

import java.util.*;
 
public class Main {
	
	static long[] layer;
	
	public static void main(String args[]){
		Scanner sc= new Scanner (System.in);
		int n = sc.nextInt();
		long x = sc.nextLong();
		
		layer=new long [n];
		for(int i=0;i<n;i++){
			if(i==0)layer[i]=1;
			else layer[i]=layer[i-1]*2+3;
		}
		
		
		long ans = pati(n,x);
		
		
		
		System.out.println(ans);
		
		
	}
	
	
	public static long pati(int n, long x){
		if(n==0)return 1;
		else if(x<=1)return 0;
		else if(x<=1+layer[n-1])return pati(n-1,x-1);
		else if(layer[n-1]+2==x)return pati(n-1,x-2)+1;
		else if(x<2*layer[n-1]+2)return pati(n-1,layer[n-1])+1+pati(n-1,x-1-layer[n-1]-1);
		else return 2*pati(n-1,layer[n-1])+1;
		
		
	}
 
}

参考にしたコードのリンクはこちらです
https://atcoder.jp/contests/abc115/submissions/3770935

問題のリンクはこちらです
https://atcoder.jp/contests/abc115/tasks/abc115_d

Answer 1

else if(x<=1+layer[n-1])return pati(n-1,x-1);

レベルnを下からx枚食べた時のpati数は、
x <= 1 + レベル(n-1)の枚数であれば
レベル(n-1)を下から(x-1)枚食べた時のpati数として計算できる

これ絵を書きながらやると分かりやすいですよ

Comments

[Moai101]

返信ありがとうございます！
「レベル(n-1)を下から(x-1)枚食べた時のpati数として計算できる」とのことですが、具体的に私が載せたコードのどの部分で計算しているか教えていただけませんでしょうか？
例えば、
if(n==0)return 1;
の部分ですと、実際に１という数字が返り値として返されてるので理解できます。しかし、返り値が関数だと、どこでどのように計算されて、出力されるのかが掴みきれていないところです。

[set0gut1]

pati(n-1,x-1) は関数ではなく、関数を実行した結果の long 型の値です。（関数 pati 自体を返すようなコードも存在するので念のため）

pati 内で pati を呼び出すような実装を再帰と言います。このコードだと O(x) 回ほど pati が呼び出され、その計算結果が積み上がって全体の計算結果が組み立てられるような動きになります。

もし再帰の概念に馴染みがなければ、「ハノイの塔」について調べると分かりやすいと思います。

[Moai101]

返信遅れました。ありがとうございます！なんとか解決できました

[set0gut1]

おめでとうございます！