Search

Computer House Random
Computer House Random
  • Randomについて
  • ブログ
  • Project
  • 作品紹介
  • 部員紹介

主客転倒について

コストの寄与を考える

motu84834
最終更新 2021/05/07

※本稿を執筆しているのは競プロ初心者であるため、読みづらかったり間違いを含んでいる可能性があります。ご了承下さい。またABCの過去問のネタバレを含んでいます。

競プロの問題の典型に、盤面に対してコストが設定されるときあらゆる盤面に対してコストを計算しその和を出力せよ、というものがある。例えば以下のような問題。

例題

長さ$N$の数列$A=(a_1,a_2,…,a_n)$が与えられる。うぇかりー君は数列から連続した部分列を選ぶのが好きであり、数列$A$から$a_l,a_{l+1},…,a_r$を選んだときうぇかりー君の喜び度は$\sum_{i=l}^r a_i$と定義される。数列$A$のあらゆる連続した部分列の選び方に対してうぇかりー君の喜び度を計算しその和を$10^9+7$で割った余りを出力せよ。

制約

$1{\leq}N{\leq}10^5,1{\leq}a_i{\leq}10^5$

例題に対する入力として$N=3,A=(1,2,3)$が与えられたとすると、$A$に対する連続した部分列の選び方は$(1,2,3)$、$()$(何も選ばない)、$(1)$、$(2)$、$(3)$、$(1,2)$、$(2,3)$で全てであり、答えは$6+0+1+2+3+3+5=20$となる。
長さに関する制約から選び方をすべて列挙して計算するのは$O(N^2)$かかって厳しい。なので、かわりに$a_i$を含む連続する部分列の選び方が何通りあるかを数える。$a_i$が含まれる連続する部分列の個数は$i\times{(N-i+1)}$個であるので、答えのコストのうち$a_i$が選ばれることによるコストは$i\times{(N-i+1)}\times{a_i}$となる。よって例題の答えは以下のコードで計算出来る。(入力は省略)

const int MOD = 1e9+7;
long long ans = 0;
int n;
vector<long long> a(n);
for(int i = 0;i < n;i++){
 ans += a[i] * (i+1) % MOD * (n-i) % MOD;
 ans %= MOD;
}
cout << ans << endl;

答えに含まれる回数などを数え上げることで計算量をへらすのは典型でABCの過去問にもちょこちょこあったりするので、なんとなく覚えておくといいかもしれません。
類題:ABC058-E ABC127-E

新入生向けブログリレー2021

2021年度オンライン部活動説明
競技プログラミング 新歓ブログリレー2021 記事を共有
Avatar
motu84834

    Computer House Random はパソコンによる創作活動を行っている大阪府立大学の部活動です

    Avatar
    motu84834
      競技プログラミング 新歓ブログリレー2021 記事を共有

      News

      ICPC2020参加記

      ICPC
      pngn
      2021/05/08

      コンピュータハウスランダムってどんな部活?

      【1日目】5分でわかるランダムのこと
      NEGI
      最終更新 2020/04/18

      はじめまして、らんだむちゃんです!

      自己紹介と最初の動画
      らんだむちゃん
      最終更新 2020/03/19

      作品紹介

      【18日目】難波駅構内をblenderで再現してみた

      途中経過
      うっかり侍
      2021/08/31

      【17日目】ウィルダネスアドベンチャー(?)

      いつかリベンジする
      クマイザサ
      最終更新 2021/08/30

      【16日目】CHICKEN NIGHTS

      正直、すまんかった
      Marcus
      最終更新 2021/08/29

      Tag Cloud

      作品紹介 (48) 新歓ブログリレー2021 (46) 新歓ブログリレー2020 (37) 競技プログラミング (34) 新歓ブログリレー2022 (33) 雑談 (32) ゲーム (30) ゲーム制作 (24) 競プロ勉強会 (22) 作品展示リレー2021夏 (19)

      最新の投稿

      【38日目】OneDriveでファイルを管理して授業や部活で活用しよう!

      オム大、クラウド1TBくれるってよ
      Kwang
      最終更新 2022/04/29

      【37日目】受けループやらメタビートやらのすゝめ

      (ゲームにおいては)人の嫌がることをするのが最も楽しい
      クマイザサ
      2022/04/28

      【36日目】マイクラのMODパックで遊ぼう

      MODパックの導入は難しそうって思ってない?
      neuron
      2022/04/27

      【35日目】大阪公立大学 中百舌鳥図書館利用のススメ

      かなり長め
      Rikky
      2022/04/26
      READ MORE

      関連記事


      ICPC2020参加記

      ICPC

      Avatar

      AHCに参加してみた。

      競プロ勉強

      Avatar

      競プロのすすめ

      そろそろ復帰したい

      Avatar

      競プロ成長録的なもの

      精進しよう

      Avatar

      ARC120-F解説

      ARC120 F

      Avatar

      新入生向けブログリレー閉会式

      お疲れ様でした

      Avatar

      Random
      Randomについて
      ライセンス
      Privacy Policy
      お問い合わせ
      部員専用サイト
      Project
      新入生向けブログリレー2022
      作品展示リレー2021夏
      競プロ勉強会
      Web
      らんだむちゃん
      ブログ
      作品紹介
      LT会
      グラフィック
      DTM
      タグ一覧
      Copyright © 2020 Computer House Random
      引用
      コピー ダウンロード