外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

E - Forced Super Arcaea Online

作成者 sevenc_nanashi

テスター unbakedbread

配点 300 点

実行時間制限
2 秒
メモリ制限
512 MiB

解説

前提:計算量について

ShareOJではLv.3以降、AtCoderではC問題以降の問題からは処理を行う回数に気を配る必要のある問題が出てくるようになります。

この問題は素直に実装すると最大10910^9ヶ月分の計算が必要になってしまいます。
雑に書くと、計算回数は大まかに10810^8回程度までしか許容されません。
Lv.3以降の問題は、このような処理をいかに効率化して、可能な限り少ない計算で済ませるかが重要になってきます。

(詳しくは「計算量」で調べると良いでしょう)

本題

では、この問題を高速に解きましょう。

メモリーを購入する月・問題で指定された月以外をスキップすることで、計算量を大幅に削減することができます。
また、現在のメモリー量をFFで割ることで、何ヶ月加入できるかを一気に計算することができます。

よって、以下のように解くことができます:

  • メモリーを購入する月・質問された月を「重要な月」として、重要な月のみに注目します。
    • 重要な月の重複を削除したうえで、昇順にソートしておきます。
  • 重要な月を順に処理していきます。
    • 1つ前の重要な月から現在の重要な月までの月数を計算し、11を引いた値を「飛ばした月数」とします。
    • 現在のメモリー量をFFで割ることで、何ヶ月加入できるかを計算します。
    • 「飛ばした月数」と「加入できる月数」の小さい方がスキップした期間で実際に加入した月数となるため、その分のメモリーを消費します。
    • 現在の重要な月でメモリーを購入した場合は、購入したメモリーを現在のメモリー量に加えます。
    • 現在のメモリー量がFF以上なら加入処理を行い、加入状況と現在のメモリー量を更新します。
    • 現在の重要な月が問題で指定された月であれば、加入状況と現在のメモリー量を出力します。

ソートでは計算量がO((N+Q)log⁡(N+Q))O((N+Q)\log(N+Q))かかり、それ以降の処理はO(N+Q)O(N+Q)で済むため、全体の計算量はO((N+Q)log⁡(N+Q))O((N+Q)\log(N+Q))となります。
これは十分に高速であり、制約内で解くことができます。

実装例(Ruby、532ms)

Bonus:O(N+Q)O(N+Q)で解いてみましょう。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。