質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.44%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

1067閲覧

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

Fafrotskies

総合スコア1

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2023/06/06 03:41

わからないこと

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

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

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

C++

1#include <bits/stdc++.h> 2using namespace std; 3#define rep(i, n) for (int i = 0; i < (n); i++) 4#define rep1(i, n) for (int i = 1; i <= (n); i++) 5 6int main() { 7 int n; cin >> n; 8 vector<int> p(2*n + 2); 9 rep1(i,n) { 10 int a; cin >> a; 11 p[i*2] = p[i*2+1] = a; 12 } 13 vector<int> ans(n*2+2); 14 for(int i = 2; i <= n*2+1; i++) { 15 ans[i] = ans[p[i]]+1; 16 } 17 for(int i = 1; i <= n*2+1;i++) { 18 cout << ans[i] << '\n'; 19 } 20 return 0; 21}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2023/06/06 08:23 編集

(同じ話を「回答」として書いたので削除)
guest

回答2

0

ベストアンサー

~をもとにしたACコード

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

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

例えば…

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

C++

1int main() 2{ 3 //問題文と記号を合わせて { N, Ai } みたいな変数名を用いたら分かりやすいであろう. 4 int N, Ai; 5 std::cin >> N; 6 7 //呪文みたいな数式を書くんじゃなくて,意味がある値をその意味を示す名称の変数に保持してみるとか 8 const int nAmeba = 1 + 2*N; //アメーバの総数(まず最初の1匹がいて,記録1つにつき2匹増える) 9 10 //vectorの用途等も注釈なりで明記してみては? 11 // 各アメーバの親の番号を記録する用. 12 // ParentAmebaNo[ i ] には,番号i のアメーバの親の番号を記録する. 13 // アメーバの番号は 1-based な値なので,[0]は未使用. 14 std::vector<int> ParentAmebaNo( nAmeba+1 ); 15 16 //(ループにわざわざ "rep1" みたいなマクロを使わない) 17 for( int i=1; i<=N; ++i ) //ここの変数名 i は問題文での記号に合わせてのこと 18 { 19 std::cin >> Ai; 20 ParentAmebaNo[ i*2 ] = Ai; 21 ParentAmebaNo[ i*2 + 1 ] = Ai; 22 } 23 24 //答えの記録用. 25 // Ans[ i ] には,番号i のアメーバが(最初のアメーバを「0世代目」として)何世代目なのかを記録する. 26 std::vector<int> Ans( nAmeba+1, 0 ); //ここでは Ans[1]=0 であることに意味があるのだから初期化値 0 を明記すると良いか 27 for( int AmebaNo=2; AmebaNo<=nAmeba; ++AmebaNo ) //ループ変数は意味が分かる名前にする 28 { 29 Ans[ AmebaNo ] = Ans[ ParentAmebaNo[AmebaNo] ] + 1; 30 } 31 32 //結果出力 33 for( int AmebaNo=1; AmebaNo<=nAmeba; ++AmebaNo ) 34 { 35 std::cout << Ans[ AmebaNo ] << '\n'; 36 } 37 return 0; 38}

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

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

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

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

C++

1int main() 2{ 3 //問題文と記号を合わせて { N, Ai } みたいな変数名を用いたら分かりやすいであろう. 4 int N, Ai; 5 std::cin >> N; 6 7 //呪文みたいな数式を書くんじゃなくて,意味がある値をその意味を示す名称の変数に保持してみるとか 8 const int nAmeba = 1 + 2*N; //アメーバの総数(まず最初の1匹がいて,記録1つにつき2匹増える) 9 10 //i番目の記録での分裂によって発生したアメーバとは何世代目の存在なのか?を記録する用. 11 //※便宜上,最初の一匹目が「i=0 番目の分裂で発生した」と見なす. 12 std::vector<int> ANS_i( N+1, 0 ); //最初の一匹目用のデータとして,ANS_i[0] = 0 としておく 13 14 //各アメーバが何番目の分裂によって発生したのか?を記録する用. 15 // アメーバの番号は 1-based な値なので,[0]は未使用. 16 std::vector<int> iOfAmeba( nAmeba + 1, 0 ); //最初の一匹目用のデータとして,iOfAmeba[1] = 0 としておく 17 18 //N個の分裂記録を読込みつつ,内容を記録していく. 19 for( int i=1; i<=N; ++i ) //ここの変数名 i は問題文での記号に合わせてのこと 20 { 21 std::cin >> Ai; 22 ANS_i[ i ] = iOfAmeba[Ai] + 1; 23 iOfAmeba[ i*2 ] = i; 24 iOfAmeba[ i*2 + 1 ] = i; 25 } 26 27 //結果出力 28 for( int AmebaNo=1; AmebaNo<=nAmeba; ++AmebaNo ) 29 { 30 std::cout << ANS_i[ iOfAmeba[AmebaNo] ] << '\n'; 31 } 32 return 0; 33}

投稿2023/06/06 08:22

編集2023/06/07 02:13
fana

総合スコア11729

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2023/06/06 08:28

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

2023/06/07 01:35

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

2023/06/07 02:15

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

2023/06/07 02:28 編集

> A_iを分裂番号目の配列に記録していく この理解が間違いに見えます. 私が提示したコードでの > ParentAmebaNo[ i*2 ] = Ai; > ParentAmebaNo[ i*2 + 1 ] = Ai; の部分の添え字{ i*2, i*2+1 }というのは「 i 番目の分裂によって新たに発生した2匹のアメーバに付与される番号」です. アメーバに振られた番号なのであって「分裂番号目」ではありません. > // ParentAmebaNo[ i ] には,番号i のアメーバの親の番号を記録する. っていう注釈もつけてますよね. (…と,こんな感じに,「各配列の添え字って何なの?」とかそういうことをちゃんと明記してみれば混乱を防げるよね,というのが,まさにこの回答の内容)
fana

2023/06/07 02:31

そういう意味では,より分かりやすいコードにするなら,例えば int NewAmebaNo[2] = { i*2, i*2+1 }; //新たに生じた2匹のアメーバに付与される番号 ParentAmebaNo[ NewAmebaNo[0] ] = Ai; ParentAmebaNo[ NewAmebaNo[1] ] = Ai; とか書けばいいのかな.
Fafrotskies

2023/06/15 11:12

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

0

なぜ 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;になります。

投稿2023/06/06 07:10

ozwk

総合スコア13544

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.44%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問