問題一覧 > スコア問題

No.5010 Better Mo's Algorithm is Needed!! (Unweighted)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 29
作問者 : butsurizukibutsurizuki
1 ProblemId : 8810 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-17 00:34:02

メモ

この問題のスコア順位はこちらをご覧ください。 https://yukicoder.me/problems/no/5010/score

この問題は、Advent Calendar Contest 2022 17日目の 問題1 です。
難易度は、Advent Calendar Contest 用に付けられたものです。正当な出力を行うことが出来ればコンテストで得点を獲得できます。

ルール

Advent Calendar Contest 2022 17日目 (Better Mo's Algorithm is Needed!!) は、2つの問題からなります。

  • 問題1: Better Mo's Algorithm is Needed!! (Unweighted)
  • 問題2: Better Mo's Algorithm is Needed!! (Weighted)
この問題は 問題1 です。
問題2 との相違点は以下です。
  • $WT=1$ で固定です。
  • $W_i=100$ で固定です。
  • 問題2 の $W$ は期待値が約 $50$ になるように生成されます。そのため、 問題2 は 問題1 の $2$ 倍かそれ以上のスコアを期待することができます。

この問題の総合順位は以下のように決定されます:
  • (問題1の得点) + (問題2の得点) の合計が高い方が上位である。
  • ここまでで順序がつかなければ、同順位とする。
なお、総合順位はコンテスト期間終了後に手動で集計されます。

スコア問題であるため、最後の提出から5分間は次の提出を行うことができません。

この問題に対しての、(Writerが想定している)コンテスト中の言及ルールは以下です。
  • 解法に直接かかわらない部分(ローカルテストの方法等)について、議論や相談を認めます。
  • ビジュアライザを有志で作成し公開するなどしても構いません。
  • さらに、自身の解法を直接言及することも、コードを共有することも認めます。
    • ただし、そのことによって他の方が解を改良した場合、その得点は改良したコードの提出者のものとなります。
なお、コンテスト期間終了後のリジャッジ、システムテスト等は予定しておりません。
2022-12-17 23:30:00 をもってコンテスト期間終了とし、解説ページにてケース生成に用いたシードを公開します。

問題文

重み $W=(W_1,W_2,\dots,W_N)$ が長さ $N$ の数列として与えられる。
また、 $1 \le L_i \le R_i \le N$ を満たす区間 $[L_i,R_i]$ が $Q$ 個与えられる。
この問題の目的は、 $(1,2,\dots,Q)$ の順列である $P=(P_1,P_2,\dots,P_Q)$ を適切に定め、以下で定義する実行時間 $T$ を最小化することである。

実行時間 $T$ は、以下のように定義される。

  • まず、 $\displaystyle T=\sum^{R_{P_1}}_{k = L_{P_1}} W_k$ とする。
  • 次に、 $i=1,2,\dots,Q-1$ に対して、以下を行う。
    • $[a,b]=[L_{P_i},R_{P_i}],[c,d]=[L_{P_{i+1}},R_{P_{i+1}}]$ とする。
    • $\alpha = \min(a,c), \beta = \max(a,c)$ とし、 $T$ に $\displaystyle \sum^{\beta-1}_{k=\alpha} W_k$ を加算する。 $a=c$ であるとき加算される値は $0$ である。
    • $\gamma = \min(b,d), \delta = \max(b,d)$ とし、 $T$ に $\displaystyle \sum^{\delta}_{k=\gamma+1} W_k$ を加算する。 $b=d$ であるとき加算される値は $0$ である。

得点

この問題にはテストケースが 120 個存在します。
各テストケースに対する得点は $\min \left( \rm{round} \displaystyle \left( \frac{10^{18}}{T} \right) , 10^{16} \right)$ です。
この問題に対する最終的な得点は、全てのテストケースの得点の総和です。

入力

$N$ $Q$ $WT$ $ST$
$W_1$ $W_2$ $\dots$ $W_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

制約

  • 入力は全て整数
  • $N = 200000$
  • $Q = 200000$
  • $\color{red}{WT = 1}$
  • $1 \le ST \le 3$
  • $\color{red}{W_i = 100}$
  • $1 \le L_i \le R_i \le N$

$WT$ は $W$ の生成方法、 $ST$ は区間の生成方法を表した整数である。詳細は後述する。

出力

順列 $P$ を以下の形式で出力せよ。

$P_1$ $P_2$ $\dots$ $P_Q$

入力生成方法

$l$ 以上 $r$ 以下の整数を返す一様乱数を $\rm{rnd}$$(l,r)$ と書きます。
$N=200000,Q=200000$ は固定です。
この問題では、 $WT=1$ です。
$WT=1$ であるとき、全ての $i$ に対し $W_i=100$ となります。
また、 $ST$ は $1,2,3$ いずれかの値を取ります。テストケースには各 $ST$ が同数含まれます。
$ST=1$ であるとき、区間 $[L_i,R_i]$ は必ず 方法1 によって生成されます。
$ST=2$ であるとき、区間 $[L_i,R_i]$ は必ず 方法2 によって生成されます。
$ST=3$ であるとき、区間 $[L_i,R_i]$ は 方法1 と 方法2 のどちらかが等確率で区間ごとに独立に選択され、その方法で生成されます。

方法1:

  • $x=$ $\rm{rnd}$$(1,N),y=$ $\rm{rnd}$$(1,N)$ で生成する。
  • もし $x>y$ なら $x,y$ を交換する。
  • 生成される区間は $[x,y]$ である。
方法2:
  • $l=$ $\rm{rnd}$$(1,N)$ で生成する。
  • $x=$ $\rm{rnd}$$(1,N-l+1)$ で生成し、 $y=x+l-1$ とする。
  • 生成される区間は $[x,y]$ である。

配布物等

こちらから配布物(zip)を入手してください。
この配布物を解答に用いたり、この配布物を他言語に翻訳したものを再配布しても構いません。

サンプル

サンプル1
入力
5 6 1 1
100 200 300 400 500
1 3
4 4
2 5
1 5
3 5
2 4
出力
6 5 4 3 1 2

このサンプルは制約違反であり、実際の入力には含まれません。

  • $P_1 = 6$ であり、この時点で $T=900$ です。
  • $P_2 = 5$ であり、この時点で $T=1600$ です。
  • $P_3 = 4$ であり、この時点で $T=1900$ です。
  • $P_4 = 3$ であり、この時点で $T=2000$ です。
  • $P_5 = 1$ であり、この時点で $T=3000$ です。
  • $P_6 = 2$ であり、この時点で $T=4000$ です。
以上より、この出力に対するスコアは $250000000000000$ です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。