ABC462 B - Gift

考え方

不定長の二次元 vector を扱えるか、という問題。

まず、入力を受け取るのが難しい。
方法は以下。

• $N$ 個の空配列をもっている二次元 vector を作っておく。
• 以下をループする
  • $K$ の値を受け取ったら、.resize() を使って a.at(i) の大きさを $K$ に変更する。
  • $K$ 個分、通常の vector と同じように入力を受け取っていく。

それができたら、今度は答えを作っていく。
再び $N$ 個の空配列をもっている二次元 vector を作っておく。
そして、人 $i$ から人 $j$ にギフトを送るなら、人 $j$ は人 $i$ からギフトを受け取るということ。
これを、.emplace_back() で答え用の二次元 vector に入れていく。
$i$ が小さい順に処理することで、自然と結果が昇順に並ぶ。

実際には 0-indexed と 1-indexed の変換をしなくてはいけないことに注意。
すなわち、a.at(i) のデータに j とあるなら、result.at(j-1) に i+1 を入れることになる。

完成したら、今度は出力。
中身の各配列ごとに、まずサイズを出力して、その後中身をスペース区切りで出力する。
最後の出力後のスペースを取り除いてきっちり指定形式にしてもいいし、
AtCoderでは改行前に余計な半角スペースがあっても無視してくれるので、それを利用してもよい。

以下は、C問題以上のレベルの話。
実はこれは有向グラフの隣接リストにおいて、すべての辺の向きを逆転する方法そのものである。
今後もっと難しい問題で使用することになるので、覚えておきたい。

入力例1での動作

入力を受け取る。

n: 4
a: {
     {2},
     {3},
     {2},
     {1, 2, 3}
   }

人 $1$ から順に、ギフトを送った相手を見ていく。
相手ごとに「誰からギフトを受け取ったか」を追加していく。

したがって、各人にギフトを送った人は次のようになる。

注意点

特になし。

別解

特になし。