脳log[20220323]

2022年03月23日 (水) [AtCoder] 精進。大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）-C「Max Dot」(青 diff)。「茶 diff も緑 diff も解けないゼロ完だった」回の ARC。今もって A 問題も B 問題も解けないんだけど C 問題はなんとかなった。だけど難しい。■もっとも単純なケースとして A 数列が昇順に並んでいる場合を考える。この場合は A 数列を後ろから見ていって、合計が S を超えない範囲で順番に上限である M の重みを割り振っていけば最大値が達成できるし、前から見ていったときに重みが減少していてはいけないという条件も満足できる。次に１つだけイレギュラーを起こして、A 数列のある要素が直前の要素より小さくなった場合を考える(ある要素を除けば全体として昇順になっている)。ある小さな要素と直前の要素をその平均で置き換えたときに数列の全体が昇順になるのなら、最初の場合と同じようにして最大値が達成できる。平均を取った２つの要素に揃って M の重みを割り振るにはもちろん S から 2M 分の割り当てを確保しなければいけない。これらを踏まえて実際に行う操作は、数列を後ろから見ていって基本的には平均を取る。現在の要素とこれまでの平均を比べて昇順になっている(現在の要素の方が小さい)なら平均を取るのを区切って新たな平均を取り始める。そして先頭まで処理が済んだら昇順になった区間に後ろから重みを割り振っていく。■提出 #30369066 (AC / 64 ms)。自分は１回の操作で満足していたのだけどテストケースが合わなかったので数列が完全に昇順になるまで何度でも操作を繰り返すようにしたらなぜか時間内に答えが出た。考えれば１回の操作で数列の長さは必ず１以上縮むのだから、最悪 N の２乗を想定しておけば答えは出るのだった。64 ms は 5000 の２乗よりずっと速いので何かが見えていない可能性はあるが。■これを「やるだけ」とか言って解きたいものだ。■自分のは ixrs さんのこの提出 #26597419 (AC / 61 ms) の劣化版みたいなものだな。自分が前半のループで if ～ else ～ end と書いているところがあちらでは until groups.empty? do ～ end になっていて、新しい配列を伸ばす一方ではなく処理対象にしてしまっている。そのおかげで一度のスキャンで必要な処理を終えられているのだろう。自分のように何度も何度もスキャンしないで済んでいる。それ以外の部分は全体的によく似ていて理解がしやすいあたり、O(N) 解法までわりと惜しいところまでいっていたのだな。解説に書いてあった O(N) 解法のヒント(凸包)が何のことかはさっぱりわかりませんが(「俺は凸包の点数はいらねーんだ」「それは自分の人生とは一切関わることのない専門用語」)。■まねまね>提出 #30381972 (AC / 66 ms)。