0.はじめに
昨日は調子が悪かったので気を取り直してレギュラーコンテスト。
A問題は解けましたが、B以降は解き方の考えがまとまりませんでした・・・。
レートは微増でした。
1.A - Ekiden Race
問題名が駅伝となっていたので、問題がすんなり理解できませんでした・・・。
駅伝は忘れて取り組みました。
考え方
往路順位が最終順位より高いかつ、往路順位が自分以下な人に袋順位で抜かされていない人が
区間賞を取っている可能性がある。
注意点としては、以下のようなケースの場合
2 1 4 3
最終1位の人は、最終2位の人を抜かしているので
区間賞の可能性があるが、最終3位の人も、1位の人に抜かれていないので
区間賞の可能性があるということ。
実装
以下ケースごとの実装内容
変数定義
N：ケースごとの人数(入力値)
P：順位リスト(入力値)
Q：往路が下位の人に、復路で抜かれていないかを保持するリスト(初期値0)
0(未チェック・抜かれていない) 1：抜かれたorチェック済
chk：復路順位チェック用変数(初期値1)
flg：抜かした人用ループフラグ(初期値0)
ans：回答用変数(初期値0)
i：抜かした人用ループ変数
Q[1]に1(チェック済)をセット
以下flgが0の間繰り返す
-chk位の人が往路どの順位だったかを探す＆抜かした人を抜かれた状態にする
以下P[i]がchkと異なる間繰り返す
Q[P[i]に1(抜かれた)をセット
→最初のループ(1位の人を探すループ)時を例にとると
最終順位1位より前にいる→往路で1位の人より先にいた→復路で抜かれた
iに1を加算
最終順位1の人は区間賞の可能性があるので、ansに1加算
-次に探す順位を求める処理
j：chk+1↑で調べた順位の次の順位をセット
iに1を加算(次のループ時には今まで調べた往路順位移行から調べればよいため)
flg2に0をセット：2個目のループ制御用
以下、flg2が0の間実行
jがNを超えた場合（全員チェックを終えた場合）
flg2に1をセット
Q[j]が0（未チェック＆抜かされてない）の時
Q[j]に1をセット→チェック対象とする
flg2に1をセット
chkにjをセット
上記以外の場合
jに1を加算
-1週目のループ終了判定
jがNを超えた場合
flgに1をセット
最後にansを出力して終了
https://atcoder.jp/contests/arc162/submissions/42722070
以上