脳log[20241007]

2024年10月07日 (月) [AtCoder] 精進。おとといあった ABC374-F Shipping。ABC374 を通しての特徴だったけど、制約が 100 以下と小さい。O(N^4) とかにならない限り制約に殺される心配がなかったけど、制約からのメタ読みでアルゴリズムを絞らせない狙いでもあったのだろうか。そしてこの問題は代わりにパラメータが多い。溜まっている注文の数、どの注文まで出荷したか、最終出荷日、不満度の累計。それと最初は気付いていなかったんだけど、最終出荷日というのは Ti の値とは独立して決まるんだよね。何かの注文が出荷可能になったタイミングで必ずしも出荷されるのではない。注文が K+1 個溜まらないように出荷されるのではない。問題を読んで、読むだけでなく理解してください。■提出 #58547000 (AC / 461 Byte / 106 ms)。コメントに書いたように、i 番目の注文を含む 1 から K 個の荷を出荷するような DP を書いた。中心となるデータは最終出荷日と累積不満度のペアの配列。出荷日が遅れるほど不満度は低くなければいけない。逆に言えば、出荷日が早いなら不満度が高くても記録する価値がある。日をおいて改めて考えてお風呂デバッグが完了したと思ったら逆に WA が増えた E 問題と比べると、落ち着いて整理すれば解ける普通の問題だった。■E 問題が解けるまで ABC374 のふりかえりはできないよ。提出一覧で他の人の提出を見たり、順位表で解いている人数を見たり、AtCoder Problems で難易度を見たり、Yahoo!リアルタイム検索で X の投稿を読んだり、ブログの参加記を読んだりできないよ。解けるんだからネタバレは嫌だ。E 問題を始末するまで ABC374 が終わらない。■■■E の精進 (20241010)。