AtCoderBeginnerContest274 C問題Ameba 解説が理解できない DFS

Question

わからないこと

https://atcoder.jp/contests/abc274/tasks/abc274_c

なぜ p[2i], p[2i+1] に a を代入するのか、
親の代+1が自分の代ということは理解できるのですが、p[i]番目の配列に1を足したものが答えになるのかがわかりません。

公式解説放放送をもとにしたACコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)

int main() {
    int n; cin >> n;
    vector<int> p(2*n + 2);
    rep1(i,n) {
        int a; cin >> a;
        p[i*2] = p[i*2+1] = a;
    }
    vector<int> ans(n*2+2);
    for(int i = 2; i <= n*2+1; i++) {
        ans[i] = ans[p[i]]+1;
    }
    for(int i = 1; i <= n*2+1;i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Comments

[fana]

（同じ話を「回答」として書いたので削除）

Answer 1

～をもとにしたACコード

という言い回しから察するに，そのコードはご自身で書かれたわけですよね？

何故この手のパズルをやってる人は一様にこのようなコードを書くのか？っていうその理由や必要性は知りませんが…
仮に，わざわざ呪文みたいなコードを書いてそれを自身で「イミフ」って言ってるのであれば，
少なくとも内容理解を目的とする状況下においては　前記の「理由や必要性」　は当てはまらないと思うので，そういう際にはもっと　ご自身が読める/説明的/etc　な形にコードを書いてみたら良いのではないでしょうか．

例えば…

• N, Ai, i といった，問題文に出てくる記号については，コードでも同じ記号を変数名にすればどうですか？（そしてこれらの変数を別の用途に使わない．例えば i を別の意味合いのループに使わない）
• 以下のように感じに，変数の意味とか使い方を明記してみればどうですか？
• （ループ用の変なマクロは見た目に値域がわからないので，こういう場合にはやめた方が良いように思えますが，これは本人の慣れ次第かな？）

int main()
{
	//問題文と記号を合わせて { N, Ai } みたいな変数名を用いたら分かりやすいであろう．
	int N, Ai;
	std::cin >> N;
	
	//呪文みたいな数式を書くんじゃなくて，意味がある値をその意味を示す名称の変数に保持してみるとか
	const int nAmeba = 1 + 2*N;  //アメーバの総数（まず最初の1匹がいて，記録１つにつき２匹増える）

	//vectorの用途等も注釈なりで明記してみては？
	//	各アメーバの親の番号を記録する用．
	//	ParentAmebaNo[ i ] には，番号i のアメーバの親の番号を記録する．
	//	アメーバの番号は 1-based な値なので，[0]は未使用．
	std::vector<int> ParentAmebaNo( nAmeba+1 );

	//（ループにわざわざ "rep1" みたいなマクロを使わない）
	for( int i=1; i<=N; ++i )  //ここの変数名 i は問題文での記号に合わせてのこと
	{
		std::cin >> Ai;
		ParentAmebaNo[ i*2 ] = Ai;
		ParentAmebaNo[ i*2 + 1 ] = Ai;
	}

	//答えの記録用．
	//	Ans[ i ] には，番号i のアメーバが（最初のアメーバを「0世代目」として）何世代目なのかを記録する．
	std::vector<int> Ans( nAmeba+1, 0 );  //ここでは Ans[1]=0 であることに意味があるのだから初期化値 0 を明記すると良いか
	for( int AmebaNo=2; AmebaNo<=nAmeba; ++AmebaNo )  //ループ変数は意味が分かる名前にする
	{
		Ans[ AmebaNo ] = Ans[ ParentAmebaNo[AmebaNo] ] + 1;
	}

	//結果出力
	for( int AmebaNo=1; AmebaNo<=nAmeba; ++AmebaNo )
	{
		std::cout << Ans[ AmebaNo ] << '\n';
	}
	return 0;
}

---

親が何代目かがわかればそれに1足せば答えになると思うのですが、分裂番号が何代目かかを記録していくのではなく、A_iを分裂番号目の配列に記録していくことでなぜ答えにつながるのかがわかりません。

というコメントを受けての追記：

【あなたが言うようなアルゴリズムでも問題を解くことができますが，それは提示されたコードが使っているアルゴリズムとは異なる】というだけのことです．

分裂番号が何代目かを記録していく形の方法を実装するとしたら，例えば以下のようになるでしょうか．

int main()
{
	//問題文と記号を合わせて { N, Ai } みたいな変数名を用いたら分かりやすいであろう．
	int N, Ai;
	std::cin >> N;
	
	//呪文みたいな数式を書くんじゃなくて，意味がある値をその意味を示す名称の変数に保持してみるとか
	const int nAmeba = 1 + 2*N;  //アメーバの総数（まず最初の1匹がいて，記録１つにつき２匹増える）

	//i番目の記録での分裂によって発生したアメーバとは何世代目の存在なのか？を記録する用．
	//※便宜上，最初の一匹目が「i=0 番目の分裂で発生した」と見なす．
	std::vector<int> ANS_i( N+1, 0 );	//最初の一匹目用のデータとして，ANS_i[0] = 0 としておく

	//各アメーバが何番目の分裂によって発生したのか？を記録する用．
	//	アメーバの番号は 1-based な値なので，[0]は未使用．
	std::vector<int> iOfAmeba( nAmeba + 1, 0 );	//最初の一匹目用のデータとして，iOfAmeba[1] = 0 としておく

	//N個の分裂記録を読込みつつ，内容を記録していく．
	for( int i=1; i<=N; ++i )  //ここの変数名 i は問題文での記号に合わせてのこと
	{
		std::cin >> Ai;
		ANS_i[ i ] = iOfAmeba[Ai] + 1;
		iOfAmeba[ i*2 ] = i;
		iOfAmeba[ i*2 + 1 ] = i;
	}

	//結果出力
	for( int AmebaNo=1; AmebaNo<=nAmeba; ++AmebaNo )
	{
		std::cout << ANS_i[ iOfAmeba[AmebaNo] ] << '\n';
	}
	return 0;
}

Comments

[fana]

全然関係ないけど，アメーバは "amoeba" だと思ってたんだけど "ameba" でもOKなんですね．

[Fafrotskies]

回答ありがとうございます、
親が何代目かがわかればそれに1足せば答えになると思うのですが、分裂番号が何代目かかを記録していくのではなく、A_iを分裂番号目の配列に記録していくことでなぜ答えにつながるのかがわかりません。

[fana]

回答に追記しました．
あなたが言うような方法でも問題を解くことが可能です．
単に，方法が１つしか存在しないということではないので，たまたま違う方法が解説されているというだけでしょう．

[fana]

> A_iを分裂番号目の配列に記録していく

この理解が間違いに見えます．
私が提示したコードでの

> ParentAmebaNo[ i*2 ] = Ai;
> ParentAmebaNo[ i*2 + 1 ] = Ai;

の部分の添え字｛ i*2, i*2+1 ｝というのは「 i 番目の分裂によって新たに発生した２匹のアメーバに付与される番号」です．
アメーバに振られた番号なのであって「分裂番号目」ではありません．

> // ParentAmebaNo[ i ] には，番号i のアメーバの親の番号を記録する．

っていう注釈もつけてますよね．

（…と，こんな感じに，「各配列の添え字って何なの？」とかそういうことをちゃんと明記してみれば混乱を防げるよね，というのが，まさにこの回答の内容）

[fana]

そういう意味では，より分かりやすいコードにするなら，例えば

int NewAmebaNo[2] = { i*2, i*2+1 }; //新たに生じた２匹のアメーバに付与される番号
ParentAmebaNo[ NewAmebaNo[0] ] = Ai;
ParentAmebaNo[ NewAmebaNo[1] ] = Ai;

とか書けばいいのかな．

[Fafrotskies]

ありがとうございます、助かりました

Answer 2

なぜ p[2*i], p[2*i+1] に a を代入するのか

p[X]は番号Xのアメーバの親の番号を記録します。
コード中のaは問題文中のAiのことです。

「番号 A i​ のアメーバが分裂して消滅し、新たに 2 匹のアメーバが生まれ、それらにそれぞれ 2i,2i+1 と番号をつけた」

ということは、p[2*i], p[2*i+1] に 親の番号であるa を代入しています。

---

p[i]番目の配列に1を足したものが答えになるのかがわかりません。

p[i](問題文に合わせるなら添字はk)というのはアメーバiの親の番号のことですから、

親の代+1が自分の代

というのは
自分(i)の代(ans[i])は
自分の親p[i]の代(ans[p[i]])+1なので

ans[i] = ans[p[i]]+1;になります。