トヨタ自動車プログラミングコンテスト2025（AtCoder Beginner Contest 389）E,F,G 問題メモ

トヨタ自動車プログラミングコンテスト2025（AtCoder Beginner Contest 389）

E - Square Price

• $N$ 種類の商品がそれぞれ $10^{100}$ 個ずつあります。
• あなたはこれらの商品を各種類について $0$ 個以上買うことが出来ます。$i$ 番目の商品を $k$ 個買うには $k^2P_i$ 円かかります。
• 購入金額の合計を $M$ 円以下にするとき、最大何個の商品を買うことができるか求めてください。

• $1\leq N\leq 2\times 10^{5}$
• $1\leq M\leq 10^{18}$
• $1\leq P_i\leq 2\times 10^{9}$
• 入力される数値は全て整数

$x^2-(x-1)^2=2x-1$ を利用する。

$k-1$ 個買った状態から $k$ 個目を追加で買うときの差分に着目すると、$i$ 番目の商品について

• 1個目は $P_i$、2個目は $3P_i$、3個目は $5P_i$、、、$n$ 個目は $(2n-1)P_i$

という別々の価格の商品が1つずつ売られていると考えても問題ない。

全ての商品から、その時々で一番安いものを $M$ 円を超えない範囲で 貪欲に買っていけばよいが、愚直にシミュレーションするとTLE。

「$X$ 円以下の商品は全て買う」という方針で各商品を何個買えるか、その結果いくらになるかは、 $X$ を決めると $O(N)$ で求められる。
「$X$ 円以下の商品は全て買えるが、$X+1$ 円以下の商品を全て買ったら $M$ 円をオーバーする」 の境界 $X$ を二分探索する。

その上で、余ったお金で $X+1$ 円の商品を買えるだけ買えば、答えとなる。
（$X+1$ 円の商品を全て買うとオーバーすることが二分探索の結果として保証されているので、$X+1$ 円の商品は十分な数、必ず存在する）

Python3

F - Rated Range

• 高橋君はAtCoderのコンテストに $N$ 回参加しようとしています。
• $i$ 回目 $(1 \leq i \leq N)$ のコンテストでは、レーティングが $L_i$ 以上 $R_i$ 以下である場合、レーティングが $1$ 増加します。
• 以下の形式で与えられる $Q$ 個のクエリに答えてください。
  • 整数 $X$ が与えられる。高橋君の最初のレーティングが $X$ であった場合、$N$ 回のコンテストを終えた後のレーティングを求めてください。

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq 5 \times 10^5$ $(1 \leq i \leq N)$
• $1 \leq Q \leq 3 \times 10^5$
• 各クエリについて $1 \leq X \leq 5 \times 10^5$
• 入力は全て整数

少し高度なデータ構造を必要とする問題。逆にそれがあればF問題にしては考察部分は控えめ?

レートは全て整数で、増加するときも $1$ しか増加しない。

もしレートが2以上、たとえば $5$ 増加するなら 「レーティング対象が $1999$ までのコンテストで、 $1999$ の人が $2004$ になり、対象外の $2000～2003$ の人を逆転する」 ということがあり得るが、今回はそういうことは発生しない。

初期レートを $1,2,3,...$ と横に取り、その時々のレートを数値で表すと、

初期  １  ２  ３  ４  ５  ６  ７  ８     Li  Ri

      １ [２  ３  ４  ５] ６  ７  ８      2   5
                ↓                  
      １ [３  ４  ５  ６] ６  ７  ８
      
      １  ３  ４ [５  ６  ６  ７] ８      5   7
                        ↓          
      １  ３  ４ [６  ７  ７  ８] ８
      
     [１  ３  ４  ６] ７  ７  ８  ８      1   6
            ↓                      
     [２  ３  ４  ７] ７  ７  ８  ８

各コンテストによるレート変化は、区間に1を加算する処理となる。
逆転が発生しないので、加算範囲が1つの区間であることが保証される。
加算区間は、「その時点で、値が $L_i$ 以上 $R_i$ 以下である範囲」となる。

AtCoderライブラリにある遅延セグメント木では、max_right などを使えば、その時点の値による二分探索が行える。

• AC Library Lazy Segtree

また、より単純なデータ構造では、Fenwick木でも区間加算とその時点の値の二分探索が可能である。

Python3

G - Odd Even Graph

• 正偶数 $N$ 、素数 $P$ が与えられます。
• $M=N-1,\ldots,\frac{N(N-1)}{2}$ について、以下の問題を解いてください。
• 頂点に $1$ から $N$ の番号が付いた $N$ 頂点 $M$ 辺の無向連結単純グラフであって、頂点 $1$ からの最短距離が偶数の頂点の個数と距離が奇数の頂点の個数が等しいものは何個あるでしょうか。個数を $P$ で割ったあまりを求めてください。

• $2\leq N\leq 30$
• $10^8\leq P\leq 10^9$
• $N$ は偶数
• $P$ は素数
• 入力される数値は全て整数

次元の多いDP。

頂点 $1$ から距離が近い順に、採用頂点と、辺の張り方を確定させていく。

    ①
  ／  ＼
...省略...
｜  ｜  ｜
○  ○  ○    最短距離 i-1 の頂点群

○  ○  ○    最短距離 i として新たに追加する頂点群

距離 $i$ の頂点から出る辺は、以下の3通り。

• (A)距離 $i-1$ の頂点群の、少なくとも1頂点と繋がる。複数頂点と繋がってもよい。
• (B)距離 $i$ の頂点同士は自由。あってもなくてもよい。
• (C)距離 $i+1$ の頂点群と繋がる可能性がある。

これ以外の層の間に辺があると、ショートカットとなり、最短距離がおかしくなってしまう。

(C)は $i→(i+1)$ の遷移の時に考えるとして、$(i-1)→i$ の遷移では(A)と(B)を計算する。
つまり、DPの遷移は、直前の層の頂点数があれば計算できる。

また、実際には $i$ は具体的な数値でなく、偶奇の2通りで分ければ十分である。

以上から、次のDPで計算できる。

• $\mathrm{DP}[v,l,e,u,d]:=$
  • $v$ 頂点 $e$ 辺で、
  • 頂点 $1$ からの距離が偶数である頂点数が $l$ で、
  • 直前の層の頂点数は $u$ で、
  • 直前の層の $1$ からの距離の偶奇が $d=0:偶数, 1:奇数$ であるグラフの個数

遷移では、「新たな層に何頂点何辺追加するか」を全通り試せばよい。
「直前が $p$ 頂点、新たに追加する層が $q$ 頂点 $r$ 辺の時の、辺の張り方は何通りあるか」は、層に依らず一定なので事前計算しておける。

具体的な距離でなく偶奇の2通りにしてしまうと、DPの依存関係（どこから先に処理するべきか）が循環してしまわないか？ と一瞬思うものの、このDPは頂点数 $v$ も持っている。 各層では少なくとも1頂点は追加するので、「$v$ の小さい方から計算していく」ことで、依存関係が循環することはなくなる。

計算量は、頂点に関する次元が $O(N)$、辺に関する次元が $O(N^2)$ なので、状態数が $O(N^5)$、遷移が $O(N^3)$ で、 オーダー上では全体 $O(N^8)$ などとなってしまうが、「$O(N)$ と言いつつ、実体は $\frac{N}{2}$」「$v$ が小さいうちは、$l,u$ も小さい」など、 定数倍で何分の1かになる要素が多く、間に合う。

以下を求めたい。

• $P(p,q,r):=$ 直前が $p$ 頂点、新たに追加する層が $q$ 頂点 $r$ 辺の時の、辺の張り方は何通りあるか

$p,q$ を固定して、それぞれに対し数列 $P(p,q,*)$ を求める。

まず、(A)直前の層と追加する層の間の辺 は、

• 追加層の、ある1頂点から $k=1～p$ 辺を使って親と結ぶ方法は、$\dbinom{p}{k}$ 通りの辺の張り方がある
• $q$ 頂点あるので、形式的冪級数を使って
  • $F(x)=\dbinom{p}{1}x + \dbinom{p}{2}x^2 + ... + \dbinom{p}{p}x^p$ として、
  • $F(x)^q$ と表される

また、(B)同じ層の頂点同士の辺 は、最大で $L=\dfrac{q(q-1)}{2}$ 本まで張れる。

• $k=0～L$ のそれぞれにつき、$\dbinom{L}{k}$ 通りの辺の張り方がある。

$G(x)=\dbinom{L}{0} + \dbinom{L}{1}x + ... + \dbinom{L}{L}x^L$ として、 最終的に $F(x)^qG(x)$ が表す数列が $P(p,q,*)$ となる。

畳み込みを愚直に行った場合（このサイズならおそらくその方が速い）、 1つの $(p,q)$ につき、(A)は $O(N^3)$、(B)を(A)と統合するのは $O(N^4)$ かかる。
$p,q$ もそれぞれ $O(N)$ の範囲を動くので、事前計算全体で $O(N^6)$ かかる計算となる。

$N =30$ の時 $N^6 \simeq 7 \times 10^8$ となるが、これもDPの計算量と同様、定数倍が軽いので大丈夫。

Python3