Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

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

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

AtCoder ABC 灰Diff Diff: 100~299 プログラミング

atcoder.jp

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

問題概要

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

  • A_i = -1 : 人 i は先頭に並んでいる。
  • A_i \neq -1 : 人 i は人 A_i のすぐ後ろに並んでいる。

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

制約

  • 入力はすべて整数。
  • 1 \leq N \leq 3 \times 10^5
  • A_i = -1 または 1 \leq A_i \leq N

考察

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

入力を受け取ったらpos[i][0] = -1となる i にカウンター (ここでは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分