脳log[20211109]

2021年11月09日 (火) [AtCoder] 精進。ARC077-E「guruguru」(黄 diff)。それほど難しくはないかな。ABC-D＋α という感じ。プラスアルファで悉くつまずいて AC に辿り着けないのが自分ではあるが。ともあれ道具立てはコンテスト後にいつもいもす法だイベントソートだと話題になるあれ(よく知らないので自分では固有の名称に言及しないけど)。時間軸に沿って加速度と加速度の累積としての速度と速度の累積としての移動距離を記録して答えにする。■提出 #27154438。まずは入力された A 数列の隣接２要素(a,b)から情報を抽出する。a から b へ b-a 回のインクリメントを繰り返して移動するわけだけど、その途中にお気に入りがあると回数を節約できる。区間は [a+1,b] で節約幅は [0,b-a-1]。a+2 時点から節約効果が現れて、b がお気に入りのときに最高の b-a-1 回の節約になる。区間の左右端と節約回数の上下端が off-by-one エラーを誘発しやすい感じ(ドツボにはまった経験から書いています)。あとは区間を外れた b+1 の時点で節約効果をリセットするなど。時間軸は 1 から 2×M の２倍幅を扱うとループの境界を気にしなくて済む。■精進２。ARC035-C「アットコーダー王国の交通事情」(青 diff)。現在 Ruby での AC はなし>Ruby によるすべての提出。N^3 が想定解になる問題は定数倍のハンデも３乗で Ruby にはつらすぎる。提出 #27155496 (C++ / 88 ms)。C++ では一番速いぜ。■昨日の精進。ARC083-D「Restoring Road Network」(水 diff)。これも３乗だけど上限が 400 でなく 300 で、ループ内の処理もごく軽量なので、Ruby でも通る>Ruby によるすべての提出。