脳log[20220316]

2022年03月16日 (水) [AtCoder] 精進。ABC076-D「AtCoder Express」(青 diff)。どう解くのが王道かわからない。ABC004-D「マーブル」の解法(20210406p01)を下敷きにしてシミュレーションで解いた。行き当たりばったりで区間の端の速度を書き換えて影響を波及させる感じ。マーブルは３要素だったけど今度は最大で 100 要素あるので、メッセージのやりとりが錯綜すると怖いなと思いながら祈って出した。■提出 #30174747 (AC / 1109 Byte / 62 ms)。全然問題なかった。グラフがとてもわかりやすい解説記事「ABC 076 [いかたこのたこつぼ]」。左からと右からの２回のスキャンで済むらしいところが自分のは N の２乗になってる気がするけど、制約が緩くて助かっている。今だと間違いなく 50 万くらいの制約上限で出てくるよね。■express という語のイメージはなかなか掴みづらい。意見を述べる、感情を表現する、急行、速達、追越し車線(～lane)とか書いてある。Visual Studio の無料版が Express Edition だったりもした。ここで Express Edition と急行のあいだに共通点が見つかった。IDE では機能の一部が、急行では停車駅が、間引かれている。だから？という感じではある。Express Edition を理解する助けにはなったけど express の語が掴めたとはいえない。母乳を express するという用法もあるみたい。ある意味これは意見や感情の表出と同じように ex + press で理解しやすい。■話は戻って AtCoder Express. N の２乗を改善する方法がたぶんあって、区間の左右端の初期値をゼロではなく上限(v)にすれば良かった。それから先頭と末尾に幅と上限を 0 にしたダミー区間(Span.new(0,0))を配置する。提出 #30372922 (AC / 64 ms)。実際これで Span#accl_l と Span#accl_r の呼び出しが減るんだけど、ケースが弱くて差が出ないどころか遅くなったように見える。■いや、初期値は不定(nil)にして、一端が不定のあいだは他端に隣接する区間から打診されるどんな速度も(上限に関わらず)受け入れるようにしないと N の２乗は改善しない気がするな。