脳log[20231209]

2023年12月09日 (土) [AtCoder] 今日は estie プログラミングコンテスト2023 （AtCoder Regular Contest 169）があった。なにか参加者が普段より多かったらしいという話を読んだけど、ABC と間違えた人がいくらかいたんだろうか。自分もすっかり定期開催が当たり前になった今になって開始時刻が 21 時でないことがあると見逃しそう。日記は B 問題のふりかえりのみ。■A 問題「Please Sign」。難しいよね。何を言っているのかわからないからサンプルを頼った。これが 400 点問題。300 点よりは難しいことになっているけども。10 の 100 乗回くりかえすとか、答えが正負ゼロのどれかでいいということから、雰囲気で答えを出していいのかと思ったよね。10 回とか 50 回とか時間が許す限り操作をシミュレートして、A[1] の値の変化量の変化量が正負ゼロのどれかを調べて、正負なら A[1] の値が行き着く先は正負そのままだし、ゼロならどの値で停滞しているかを調べればいいかなと。ダメなんです。無限大無限小に発散していくときはたぶんそれでいいけども、操作によって A[1] が定点を周回するようなとき、打ち消し合わない有限の寄与の軽重を二項係数で計算して合計して、A[1] の値がどこにあるかをしっかり確かめないといけないらしいです。たぶん。これも雰囲気で書いている。■B 問題「Subsegments with Small Sums」。早々にゼロ完を覚悟したけど B 問題が普通の DP で助かった。A 問題があまりにつれなくて 20 分くらいで見切りをつけられたのも運が良かった。連続部分列に切り分けるわけだから、たとえば左から切っていくとして、中途半端に左端に要素を残して得をすることってたぶんない。端から貪欲に切り分けて良さそう？ 確信は持てないけどそういうことにして考えた。範囲をだいたいいくつの部分列に切り分けることになるかは累積和で見当がつく。両端を決めてそのあいだにある要素の和が S の何倍であるか。かといって、両端の組み合わせはおおよそ 25 万の２乗通りあって、範囲をひとつひとつ考えることはできないし、範囲のひとつひとつについて、S の倍数をまたぐ境界付近で区切りの位置を確かめることもできない。ところで、異なる２つの範囲について、実は似たようなシチュエーションが現れることがありますね。左端から貪欲に区切りを置いていったときに、同じ位置に区切りを置いたらそれ以降に起こることは共通している。そしてそれっていうのは、共通の区切りを左端とする範囲についての f 値がわかれば計算できる。というわけで数列の右端から、その要素を左端とするすべての範囲について f 値の和を記録していった。範囲の左端を決めたとき最初の区切りがどこにあるかだけ累積和を使って調べた。難しすぎるテストは時間が余って困る法則によって時間には余裕があったので、累積和を二分探索していたのを尺取りに書き換える落ち着きを見せて一発 AC だった。提出 #48318193 (AC / 194 Byte / 119 ms)。べつに尺取りが二分探索でも TLE にはならないんだろうけど、解ける問題を時間内に解くためにシビアなタイムアタックが求められる(そして時間切れになる) ABC との、取り組む姿勢の違いの現れ。■■■A 問題について眠たいことを書いていた。ここに重要な予想していなかった観察結果が書いてあった>「estie プログラミングコンテスト2023(AtCoder Regular Contest 169)参加記 - devgenjin77’s blog」。A 問題が AC できるのはまだ先になりそう。