競プロでの皆さんの入力の扱い方を教えていただきたいです。
解決したいこと
atcoderのAPG4b、再帰関数の例題について質問があります。(私はプログラミング初心者(1ヶ月)で、C++は独習2日目です。競プロをやる予定の大学生です。)
コード自体は30分もかかったとはいえ短く(簡潔かは不明)書け普通に動作もしたのですが、模範解答を見ると表面的なプロセスだけでなく、発想の仕方の手順が違うように思えました。具体的には、私は入力をそのまま使って目的を果たそうとした一方で、模範解答は入力をあるべき構造に整理してから、それを用いて目的を果たそうとしているという感じです。
そこで質問なのですが、
一般に、競プロなどで解決の手順を考えるとき、皆さんは入力されたデータを整理できるか考えるというプロセスを踏むでしょうか？(木構造などと書いてあったので、そういう有名な(？)構造があるときなどはその構造にデータを落とし込んでから考えるのが定石なのかもと思いました)
例題自体が分からないことはないのく皆さんの入力の扱い方を知りたいのですが、参考までに問題文は載せておきます。
問題文
あなたはA社を経営する社長です。 A社は
N個の組織からなり、それぞれに
0番から
N−1番の番号が付いています。
0番の番号が付いた組織はトップの組織です。
組織間には親子関係があり、
0番以外の
N−1個の組織には必ず1つの親組織があります。 子組織は複数になることがあります。 また、それぞれの組織は直接的または間接的にトップの組織と関係があるものとします。
あなたは全ての組織に報告書を提出するように求めました。
混雑を避けるために、「各組織は子組織の報告書がそろったら、自身の報告書を加えて親組織に送る」ことを繰り返します。 子組織が無いような組織は自身の報告書だけをすぐに親組織に送ります。
ある組織から報告書を送ってから、その親組織が受け取るときにかかる時間を1分とします。
あるタイミングで一斉に報告書の伝達を開始したときに、トップの組織の元に全ての組織の報告書が揃う時刻（伝達を始めてから何分後か）を求めてください。 なお、各組織の報告書は既に準備されているため、報告書の伝達以外の時間はかからないこととします。
私の考えたソースコード
#include <bits/stdc++.h>
using namespace std;
//階層の階数が求める時間よりそれを求める
int steps(int n,vector<int>ps,int N){
vector <int> match(1,0);
for (int i=0;i<N-1;i++){
if (ps.at(i)== n){
match.push_back(steps(i+1,ps,N)+1);
}
}
sort(match.begin(),match.end());
int time =match.at(match.size()-1);
return time;
}
int main(){
int N;
cin>>N;
vector<int>ps(N-1);
for(int i=0 ; i<N-1 ; i++){
cin>>ps.at(i);
}
cout<<steps(0,ps,N)<<endl;
}
模範解答
#include
using namespace std;
// x番の組織について、子組織からの報告書が揃う時刻を返す
// childrenは組織の関係を表す2次元配列(参照渡し)
int complete_time(vector> &children, int x) {
// ベースケース
if (children.at(x).size() == 0) {
return 0; // 子組織が無いような組織について、報告書が揃う時刻は0
}
// 再帰ステップ
int max_receive_time = 0; // 受け取った時刻の最大値
// x番の組織の子組織についてループ
for (int c : children.at(x)) {
// (子組織 c のもとに揃った時刻 + 1) の時刻に c からの報告書を受け取る
int receive_time = complete_time(children, c) + 1;
// 受け取った時刻の最大値 = 揃った時刻 なので最大値を求める
max_receive_time = max(max_receive_time, receive_time);
}
return max_receive_time;
}
// これ以降の行は変更しなくてよい
int main() {
int N;
cin >> N;
vector p(N); // 各組織の親組織を示す配列
p.at(0) = -1; // 0番組織の親組織は存在しないので-1を入れておく
for (int i = 1; i < N; i++) {
cin >> p.at(i);
}
// 組織の関係から2次元配列を作る
vector> children(N); // ある組織の子組織の番号一覧
for (int i = 1; i < N; i++) {
int parent = p.at(i); // i番の親組織の番号
children.at(parent).push_back(i); // parentの子組織一覧にi番を追加
}
// 0番の組織の元に報告書が揃う時刻を求める
cout << complete_time(children, 0) << endl;
}
