【AtCoder】ABC 337 C - Lining Up 2 | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 258

問題概要

人1, 2, ..., の 人が一列に並んでおり、その並び方の情報が長さ の配列 で与えられる。 は以下の情報を表す。

• : 人 は先頭に並んでいる。
• : 人 は人 のすぐ後ろに並んでいる。

このとき、列に並んでいる人の番号を先頭から順番に出力せよ。

制約

• 入力はすべて整数。
• 
• 

考察

把握しておきたい情報は、「人 の前後に何番の人が並んでいるか」であるから、番号 の人の前に並んでいる人の番号を pos[i][0] に、後ろに並んでいる人の番号を pos[i][1] に格納する二次元配列posを作成しよう。データ構造的には隣接リストに似た感じである。

入力を受け取ったらpos[i][0] = -1となる にカウンター (ここではnowとした) をセットし、 pos[now][1]にカウンターを遷移させてやればいい。

※よく考えたら前に並んでいる人の番号の情報はいらなかったので、posは一次元で十分かもしれない。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> A(N + 1);
    rep(i, 1, N + 1) cin >> A[i];

    vector<vector<int>> pos(N + 1, vector<int>(2, 0));
    int start = 0;
    rep(i, 1, N + 1)
    {
        if (A[i] == -1)
        {
            start = i;
        }
        else
        {
            pos[i][0] = A[i];
            pos[A[i]][1] = i;
        }
    }

    int now = start;
    while (pos[now][1] != 0)
    {
        cout << now << " ";
        now = pos[now][1];
    }
    cout << now << endl;
}

atcoder.jp

実装時間: 15分