Loading [MathJax]/jax/output/CommonHTML/jax.js

目次

トヨタ自動車プログラミングコンテスト2024#8(AtCoder Beginner Contest 365)G問題メモ

トヨタ自動車プログラミングコンテスト2024#8(AtCoder Beginner Contest 365)

G - AtCoder Office

G - AtCoder Office

問題文

制約

解法

まず注意点として、同じ (Ai,Bi) クエリは複数回投げられうる。
同じクエリは再計算されないように、事前にまとめるなどする必要がある。

イベント順に解く

まず率直に思いつく方法として、イベント順に解くことを考えると、

を用意して、Ti 順に入退室を見ていき、

としていくと、答えとなる。

問題は、「入退室が多く、ペアも多い人」がいると、O(NM) かかってしまう。
(例えば、ほぼ人 i の入退室で M 個の記録が占められ、クエリでも他の N1 人全てとの答えが求められる場合など)

そういう人は、別処理をする。

1人を基準に解く

入退室の多い1人を p とする。

記録 i から i+1 までの時間を、「時区間 i」とする。
各時区間の長さ Di=Ti+1Ti を求めておく。

長さ M1 の数列 X を用意し、時区間 i に人 p が入室しているなら Xi=Di、退室中は Xi=0 とする。

   記録 i   0   1    2    3    4    5    6    7
        T   3   9   15   17   20   25   26   30
        D     6   6    2    3    5    1    4

pの入退室  in      out        in       out
        X     6   6    0    0    5    1    0

こうしておけば、

2つの解法を使い分ける閾値

p の入退室回数を Rp、クエリで p とペアとなる人の数を Pp とする。

イベント順の解法では、p の入退室によって発生する計算量が 「入退室回数 Rp× ペア数 Pp」かかっていたのに比べ、 1人を基準にする解法は最初に X を作る際の「入退室記録数 M」の計算量で済む。

相手 j の入退室によって発生する、p の状態確認 (イベント順なら LastEnter のチェック、1人を基準にする解法なら X の累積和の取得) の計算量は Rj に依存し、こちらはどちらの解法も変わらない。

よって、「Rp×PpM を超える場合」に、 イベント順から p を基準に解く解法に変えるのが良い、はず。

(以下、駄文)

なお、クエリ (p,j) の両方とも R×P が大きい場合、 基準とする方をどちらか一方に決めなければいけない。
(どちらでもACできるだろうので別に突き詰める必要は無いのだが)どちらを基準とした方がよいか?

「入退室回数 R が多い」方を基準にした方が、(p,j) ペアだけ考えたときの削減効果は大きいが、 基準にされなかった方は、実質的に P(※)が1減り、評価値 R×P が変動する。
(※イベント順の解法を取ったときに、入退室のたびにチェックする相手数)

評価値 R×P が減ることで、結局イベント順の解法にした方がいい、となるかもしれない。
その場合、評価値の削減効果が大きいのも「入退室回数 R が多い」方である。

この最適化って、どうしたらいいんだろうね。

Python3