コンテストページ: Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288） - AtCoder
コンテスト中AC: A〜C
コンテスト後自力AC: D〜F

D - Range Add Query

0-indexedとします。
$X$ を愚直に全て0にできるか試すときどうするかを考えると、端から順に0にしていく方法が思い浮かびます。

例えば、 $n=8, K=3$ としてシミュレートしてみます。
まず、 $i=0$ を0にするため、 $i=0,1,2$ に $-X_0$ を足します。

$X=\{0,\ X_1-X_0,\ X_2-X_0,\ X_3,\ \cdots \}$

次は $i=1,2,3$ に $-(X_1 - X_0)$ を足す…としたいところですが、足される項が増えてややこしいので、まず、 $X_0$ を $i=1,2,3$ に足しておきます。

$X=\{0,\ X_1,\ X_2,\ X_3+X_0,\ \cdots \}$

それでは先程と同様に、 $i=1,2,3$ に $-X_1$ を足し、 $i=2,3,4$ に $X_1$ を足します。

$X=\{0,\ 0,\ X_2,\ X_3+X_0,\ X_4+X_1,\ \cdots \}$

これを繰り返しと、最終的に以下のようになります。

$X=\{0,\ \cdots ,\ 0,\ X_0+X_3+X_6,\ X_1+X_4+X_7,\ X_2+X_5+X_8\}$

このようにシミュレートしてみると以下がわかります。

$X_{i+K}$ に $X_i$ が足され、末尾 $K$ 項に $i\ mod\ K$ が等しいものの累積和が構築される

最終的に末尾 $K$ 項が等しい場合には、 $X$ を0にすることが可能です。

これより、各クエリの $A_{l_i},\ \cdots ,\ A_{r_i}$ について、 $mod\ K$ が等しい $i$ の累積和が全て同じかを判定すればよいです。

$i\ mod\ K$ が等しいものについての $A$ の累積和を予め計算しておけば、区間の累積和は $O(1)$ で求められます。

よって、各クエリ $O(K)$ で判定できます。

実装: Submission #38649675 - Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）

E - Wish List

まず、

状況が変化していき、複雑なこと
$N$ が小さいこと

から、貪欲法よりもDPっぽいなと当たりをつけます。

$A_i$ をとることを考えたとき、 $i$ より前が何個取られているかで、どの $C_i$ となるか変化します。また、前に取られた個数が同じなら、どれが取られていても状況は同じなので、情報をひとまとめにできます。

ここから、以下のようなDPを考えます。
$dp[i][j]:=$ $A_i$ までを $j$ 個取った時の金額の最小値

$dp[i][j]$ を更新することを考えます。
$i$ より前は既に $j-1$ 個取られていたとしたら、 $A_i$ は $i-(j-1)$ 番目に移動しているはずなので、 $A_i + C_{i-j+1}$ の金額が必要なはず、と思ってしまいますが、これは誤りです。
なぜなら、 $i$ より前が $0,1,\cdots ,j-2$ 個のいずれかが取られた直後に $A_i$ を取ることも可能だからです。

ここが重要なポイントで、 $i$ 番目より前に $0,\ 1,\ \cdots ,\ j-1$ 個とられているような状況について、どのタイミングで $A_i$ を取ったことにしてもよいです。

理由は直感的になりますが、まず、 $A_i$ をとるタイミングを変えても $i$ より前のとる順番には影響を与えません。
次に、 $A_i$ をとることで、 $i$ より後ろがずれて、とりたい位置でとれなくなってしまうのではないかと心配になります。
その場合は、先に後ろのものをとっておけば良いです。その後ろのものをとることで、その後ろより更に後ろがずれるなら、更にその後ろを先に取れば良いです。これを繰り返せば、最終的に一番後ろになるので、いつかは矛盾なくとれるはずです。

以上から、 $i$ 番目までで $j-1$ 個取られている状況で、 $A_i$ を取って $j$ 個取られている状況にする場合、かかる金額は、

$A_i + min(C_{i-j+1},\ C_{i-j+2},\ \cdots ,\ C_i)$

とできます。
これはSegment TreeでRMQを処理すればよいです。

以上から、DPテーブルを $i=1,2,\cdots N$ の順に以下のように更新できます(初期値は、 $dp[0][0]$ が0でそれ以外は $\infty$ )。

$A_i$ をとる場合
$dp[i][j] \leftarrow min(dp[i][j],\ dp[i-1][j-1]+A_i + min(C_{i-j+1},\ C_{i-j+2},\ \cdots ,\ C_i))$
$A_i$ をとらない場合
$dp[i][j] \leftarrow min(dp[i][j],\ dp[i-1][j])$

但し、 $i$ が $X$ に含まれる場合はとらない選択をできません。

実装: Submission #38728052 - Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）

F - Integer Division

説明のため、乗算の×を挿入することを仕切りを挿入すると表現します。
例えば、 $12|3|45$ は、 $12\times 3\times 45$ です。

$X_{j+1}\cdots X_i$ を10進数とみなしたものを $b_{i,j}$ とします。これは、 $X_j$ の後ろに仕切りを入れ、その後 $i$ 番目まで仕切りがない場合の10進数と捉えることができます。

$i=1,2,\cdots , N$ の順に見ていくとき、最後に仕切った場所が同じものについては、同じ10進数をかけることになります。

具体例を示します。 $X=12345$ として、 $i=5$ を考えたとき、最後に $j=3$ の後ろで区切ったものを考えます。
$j=3$ の後ろで区切った時のそれ以前の区切り方は、
$123,\ 12|3,\ 1|23,\ 1|2|3$ の4通りとなりますが、それより後の区切りが無いためこれらには全て $45$ が掛けられることになります。