脳log[20230206]

2023年02月06日 (月) [AtCoder] 精進。先週末あった Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）-F「Integer Division」(ぎりぎり黄 diff)。当日は D と E をひとしきり考えて諦めた後は F に狙いを定めていた。狙いはまちがっていなくて、３問のうちまず F が解けた。■提出 #38678223 (AC / 143 Byte / 91 ms)。前からの DP で解ける。何を覚えておいて何が計算したいか。１桁目が A、２桁目が B だったとして、(AB+A*B) に当たるものを覚えているとする。３桁目が C だとして求めたいものは問題の定義から (ABC+A*BC+AB*C+A*B*C) なんだけど、AB*C+A*B*C は覚えておいた (AB+A*B) に C を掛けて求まるとして ABC+A*BC はどう求まるか。覚えておいたものを 10 倍すると (AB0+A*B0) となって惜しい。不足は (1+A)*C であるが 1+A とは何か。２つ前までに覚えていた値の和だということがサンプルを丁寧にデバッグしていてやっとわかった。わかったというか見つかった。がちゃがちゃデバッグ、良くないね。■D 問題「Range Add Query」はまず操作の累積和を記録して、区間の末尾 K 要素が０になるかどうかを見たいと思った。しかし数列全体を通した累積和から区間の前 K-1(？)要素の影響を引き算する方法がわからなかった。■E 問題「Wish List」は前から順番に何個の商品を選んだ場合に最小コストがいくらかを記録していく DP をやりたいと思った。前に最初何個の商品があって最後何個まで減るかが決まっていれば最適な順序コスト(C)の選び方がわかる。そしてその選び方は前にある商品の選び方に影響を与えない。M 個の商品については必ず選ぶこととし、それ以外の商品は選ぶ場合と選ばない場合を両方考える。時間に追われてふわふわしてる頭で書ける DP ではないのだ。■E 問題。F の AC から２時間弱、ここまでの日記を書いてからじっくり集中して AC です。提出 #38679476 (AC / 465 Byte / 2166 ms)。■残った D 問題は「あ、一応。典型の考え方も含めて。「この問題そのものが有名」という話ではない。 ・区間に足し引きする問題は、imos法の逆の考え方で、始点・終点に足し引きする問題に変換できる ・足す区間が一定（長さK）の場合は、modKが同じ場所しか互いに影響を与えないので独立で考えられる の2つが典型」とか「X_i, X_{i+1}, \cdots , X_{i+K-1}にcを加算するとはどういうことでしょう。Aを多項式、すなわち A_1 + A_2x + \cdots + A_Nx^{N-1}と考えると、 c(x^{i-1}+ \cdots x^{i+K-2})を足すことです。つまり、この問題は、 1 + x+ \cdots + x^{K-1}の倍数を足して0になるか、言い換えると多項式を 1 + x + \cdots + x^{K-1}で割って余りが0か否かということです」とかのネタバレをすでに読んでしまったのだけど、だからといって自分で書ける目途は立たないんだな。咀嚼が足りない。