Processing math: 100%

目次

トヨタ自動車プログラミングコンテスト2024#2(AtCoder Beginner Contest 341)F,G問題メモ

トヨタ自動車プログラミングコンテスト2024#2(AtCoder Beginner Contest 341)

F - Breakdown

F - Breakdown

問題

解法

1つのコマが、生涯(そのコマから派生した全てのコマがなくなるまで)で 何回分の操作に相当するか、というのは、そのコマがどこに置かれているかで一意に決まる。

⑥←⑨→③→①
↓  ↓  ↓      W_i が 大→小 の方向にしかコマは流れないので、
③←④→②      辺は有効辺と見なす
    ↓
    ①

上記の①や②など、流出辺(自分より Wi が小さい隣接頂点)がなければ、 そのコマを取り除いた後は新たなコマを置けないので、可能な操作は1回のみ。

⑨や④など流出辺がある場合は、「和が自身の Wi を超えないように、隣接頂点から、1個あたりの操作回数が大きいものを選ぶ」ことになる。

これは、まさしくナップサック問題で、 ナップサックの容量を Wi、各隣接頂点 j につき Wj を重さ、DP[j] を価値とした問題を解けばよい。

Wi の小さい方からDPを埋めていけば、Wi を求めるときには、必要な DP[j] は埋まっている。

1回当たり m 個の荷物で容量 w のナップサック問題を解くとして、O(mw)、 これを各頂点に対して合計して、O(MWmax) となる。

Python3

G - Highest Ratio

G - Highest Ratio

問題

解法

区間の平均は、割る数が長さによって異なってくるため、[l,r) の時の結果を [l1,r)[l,r+1) に活用しづらい。

平均が、「累積和の傾き」によって表現できることを利用する。

14 |             *          A = (   1, 1, 4, 5, 3)
   |
   |                  累積和C = (0, 1, 2, 6,11,14)
11 |          *
   |
   |
   |
   |
 6 |       *
   |
   |
   |
 2 |    *
 1 | *
   +---------------
     1  2  3  4  5

傾きで考えると、上側凸包に含まれない点を考える必要がなくなる。

|                *
|             ,-'
|          ,-'
|       ,-' *         ← j は i より左の点を l とした時の r にはなり得ない
|     *'                 必ず i か k を r とした方が傾きが大きくなる
=
|
+-||----------------
      i     j    k 

i の大きい方から凸包を構成していけば、O(N) で求まる。

Python3