AtCoder振り返りその3(AtCoder Regular Contest 162)

まえがき

競技プログラミング振り返り三回目となります。
時間内には解けませんでしたが、なんとかA問のみ解けたので振り返ります。

A問(A - Echo)

問題はこちら→A - Ekiden Race

復路が一番早い可能性がある人数を出力するものです。
問題文で説明されていない、3つ目のテストケースを用いて解説を行います。

往路	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
復路
往復	13	2	7	1	5	9	3	4	12	10	15	6	8	14	20	16	19	18	11	17

順位にを表に直すとこのようになります。
往路の順位と往復の順位がわかりますね、復路の順位は分からないので、一番早い可能性があれば○をそうでなければ×を入れます。
往路の昇順でならんでいますが、往復の昇順が処理と説明の都合よいので並び替えたものも用意します。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

往復の順位に並び替えたことにより少しわかりやすくなりました。
復路が一番早い可能性がある人を数えていくのですが、消去法でその可能性がない人を消していきます。
条件としてはだれかと比較して往路の順位が高く往復の順位が低い人が対象となります。
分かりやすくいうと復路で抜かされた人です、それ以外の人は復路が一番早い可能性がある人となります。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路	○	×
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

左から見ていき2番目で復路で抜かされた人がでてきました。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路	○	×	○
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

3番目の人は抜かされていないので○です。なぜ簡単にわかるかという往復が高い順位(左)から見ていくため、往路の順位をみて自分より左(往復が高い順位)に往路の順位が低い人がいれば×、いなければ○となります。
これをプログラミングで行う際は変数MAXに都度往路が低い順位を入れていき判定をおこないます。いまだとMAXに7が入っています。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路	○	×	○	○
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

MAXに8が入っています。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路	○	×	○	○	×	○	×	○	×	×	○	×	×	×	×	×	○	×	×	×
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

すべて埋めたものがこちらになります、ちゃんと出力例の通りに7人出ていますね。
上記の流れを行うと以下のようなコードになります。

A問提出コード

#include<stdio.h>

int main() {
	int t;
	int ans[500];
	
	scanf("%d", &t);
	for (int j = 0; j < t; j++)
	{
		int n, count = 0, max = 0;
		int p[1000];
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			int temp;
			scanf("%d", &temp);
			p[temp - 1] = i;
		}
		for (int i = 0; i < n; i++)
		{
			if (p[i] >= max)
			{
				max = p[i];
				count++;
			}
		}
		ans[j] = count;
	}
	for (int i = 0; i < t; i++)
	{
		printf("%d ", ans[i]);
	}
	return 0;
}

for内の最初のfor文で入力と同時に往復の昇順に配列をならべかえています。
その後説明した通りの流れで見ていき○があればcountを1増やしています。

感想

時間内に解くことはできませんでしたが、自身の力で解けたのでよしとします。