Python3で解く AtCoder Beginner Contest 177 C - Sum of product of pairs
要求されている掛け算の和を累積和を使ってシンプルにする事ができるかどうかを試されている。
目次
概要
問題
1. 個の整数が与えられる。
1. を
で割った余りは？
制約
解くときに考えた内容
- 愚直にいったらTLE
- 数式を整理すると、 まず
の時を考えると
- なので、
の部分は各項までの累積和を出しておいて、全体の和（もしくは累積和の最後の項）から左側からかける値までの累積和を引けばいい。
- これを
まで行えば良い。
あとmodはPythonなので、最後にmodととした。制約上問題ない。
コード
n = int(input()) A = [int(x) for x in input().split()] mod = 10**9+7 a_cum = [0] * (n+1) # 累積和の計算 for i in range(n): a_cum[i + 1] = a_cum[i] + A[i] ans = 0 for i in range(len(A)-1): # a_cum[n]は全ての合計と同義。a_cumはindexが1つずれているので以下のようになる。 ans += A[i] * (a_cum[n] - a_cum[i+1]) % mod ans %= mod print(ans)
書籍
最近ポチった書籍
機械学習スタートアップシリーズ ゼロからつくるPython機械学習プログラミング入門 (KS情報科学専門書)
- 作者:八谷 大岳
- 発売日: 2020/08/31
- メディア: 単行本（ソフトカバー）
アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク・強化学習・教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。これは別記事で紹介する予定である。
- 実用的でないPythonプログラミング
バカ売れしているのか、アマゾンでは値段があがっている。自分は、予約していたのに来ないので、楽天で購入した。 内容としては、面白いテーマの物が多く、pygletなどを使って描画もあるような内容が結構推されているが、アルゴリズムに関する内容もある。特に前半は文字列を操作して暗号解読であったり、アナグラム・回文といったものが扱われているので勉強になる。遺伝的アルゴリズムも面白く金庫破りの実装は非常に参考になった。
実用的でないPythonプログラミング: 楽しくコードを書いて賢くなろう!
- 作者:ヴォーン,リー
- 発売日: 2020/08/12
- メディア: 単行本
- 問題解決力を鍛える!アルゴリズムとデータ構造
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本（ソフトカバー）
アルゴリズムの参考書籍
- プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）
