AtCoder Beginner Contest 162 [ D - RGB Triplets ]をPythonで解く（400点、🟫茶diff）
問題
解法
1 <= N <= 4000
なのでO(N3)だと、43 * 109 でTLEのはず。
なので、R, Gの二つの要素を固定。
すると O(16 * 106) くらい？
あとは、計算でBの要素から何個採用できるかを出す。
この方針でTLEは出ないはず。
R, Gのある場所のインデックスは総当たり。
R, Gのある場所のインデックスの大きい方と小さい方の変数をbig, smallとする。
I < j < k であるから、このbig, smallは
1. small = i, big = j
2. small = i, big = k
3. small = j, big = k
の3通りが想定できる。
j-i != k-j である必要があるので、採用しない要素があるかをBのインデックスから確認する。
採用しない要素の数が出たら
Bの数 - 採用しない要素の数
を足し込んでいく。
実装
実行結果
PyPy3(7.3.0) AC 315ms
Python3.8.2 AC 1967ms お、ギリやな
参考
この問題が似てた。
AtCoder Beginner Contest 143 [ D - Triangles ]をPythonで解く（400点、🟫茶diff）
問題
解法その1 numpy + njitを使ったO(N3)解法
なんと、何も考えずに問題通り、総当たりコードを書くとACしてしまうという解法。
マジですか。
AtCoderのPythonではnumpyが使用できるが、njitを使って関数の実行速度を高速化。
実行すると、1731msくらいでACする。
問題の制約が、3 < N < 2 * 103。
とすると、O(N3)は、(2 * 103)3なので、8 * 109。
108をオーバーするので、普通はTLEだろうと見込んでスルーする実装だが、njitを使うことで実は間に合ってしまう。
なるほどねー。わからないから、とりあえずnjitでも使ってみるか。
という選択肢もアリってことかな？
とりあえず作問した人は想定してなかった解答だろうな。
実装その1
解法その2
問題の制約が、3 < N < 2 * 103。
全探索は109オーバーなので、数学的な最適化を狙う方法。
atcoderの通常パターンなら、こう考えるべきだがw
a < b < c と考える。
a, bに総当たりならば(2 * 103)2 = 4 * 106。
cの値は計算で求める。
c < a + b
であるあから、a + b以下の要素がLの中に何個あるかを二分探索で求める。
cはbより大きいから、b+1以上の要素が下限。
Lの中からa+b以下、b+1以上の要素数を引き算で出せば終了。
計算量はO( N2 logN)
実装その2
参考
AtCoder Beginner Contest 144 [ D - Water Bottle ]をPythonで解く（400点、🟫茶diff、図形問題）
問題
数学問題。
解法
水の体積が、水筒の半分以下か以上かで処理が異なる。
水の体積が水筒の半分以下のとき
半分以下の時、水は三角柱の形でこぼれる。
θの角度が求める答え。
水の面積 x / a
水の底辺yの値を求める。三角形の面積の公式から
x / a = b * y /2
これをyについて解く。両辺に2をかけて
2 * x / a = b * y
y = 2 * x / (a * b)
ここまでとけたら、atanを計算すればθは出る。
atan(b / y)
水の体積が水筒の半分以上のとき
半分以下の時、水は台形でこぼれる。
水の面積 x / a
水筒の面積 a * b
水筒の空気部分の面積 a * b - x / a (水筒の面積 - 水の面積)
水筒の空気部分の三角形の辺yの長さを求める。
三角形の面積の公式から
a * b - x / a = a * y / 2
これをyについて解く
2 * a * b - 2 * x / a = a * y
y = 2 * b - 2 * x / a2
ここまでとけたら、atanを計算すればθは出る。
atan(y / a)
実装
参考
Educational DP Contest / DP まとめコンテスト [ K - Stones ]をPythonで解く
AtCoder Beginner Contest 141 [ D - Powerful Discount Tickets ]をPythonで解く（400点、🟩緑diff）
問題
解法
問題を一見すると
「どの商品に何枚半額割引券を使えばよいか？」
という問題に見える。
だが半額割引券を1枚ずつ使っても結果は変わらない。
なので、
「一番値段が高い商品に1枚ずつ割引券を使う」
という貪欲法で解ける。
あとは、これを高速に処理すれば良いが、優先度付きキュー(priority queue)を使う。
優先度付きキューは、最小値を高速にとることができるので、全ての数字に-1をかけて負の数字として扱い、最小値を半額していくロジックにする。
負の値を//2で割り算切り捨てすると結果にズレが出るので正の値で//2にする。
実装
参考
AtCoder Beginner Contest 212 [ D - Querying Multiset ]をPythonで解く（400点、🟫茶diff）
問題
解法
最小値を計算量低く取り出すデータ管理構造、優先度付きキュー（priority queue）を使うことがポイント。
Pythonではheapqとして提供されている。
全体に対する玉の数の上下はoffset変数を作って管理。
玉を追加する時は、offset値を引いて追加する。
優先度付きキューの特徴
- 最小値（最大値）を O(logN)O(logN)で取り出す
- 要素を O(logN)O(logN) で挿入する
ことが出来ます。 通常のリストだとそれぞれ O(N)O(N) ですので高速です。
「リストの要素の挿入」と「最小値（最大値）を取り出す」ことを繰り返すような時に使います。
実装
参考
AtCoder Beginner Contest 212 [ C - Min Difference ]をPythonで解く（300点、⬜️灰色diff）
問題
解法
数列A、数列Bが2 x 105なので、A,Bの全要素に対して総当たりだと、2 x 105の2乗なので108越えでTLE確実。
なにか最適化する必要がある。
おそらく二分探索だろうと、検索したところ、そういえばbisectという便利ライブラリがPythonにはあることを思い出す。
数列A、Bをソート。
数列Aの各要素に近い値を数列Bからbisect_rightで二分探索。
bisect_rightの結果のIはB[I-1]とB[I]を使用。
計算量はO(N logM)。
