脳log[20211126]

2021年11月26日 (金) [AtCoder] 精進。JOI 2020/2021 本選 過去問 C「集合写真 (Group Photo)」。少し考えると、許される並びは一直線に右下がりの並びを基本として、何か所かでちょん切った右下がりを逆順に配置したギザギザ右下がりしか許されないとわかる。それを制約上限 5000 を４秒以内で求める手順とは。DP ですね。１以下の H をいい感じに並べる手数から始めて２以下、３以下……をいい感じに並べていくと最後に答えが出る。■提出 #27502421 (64/100 点 / TLE×15)。制約が異なる小課題のうち最後の小課題５がすべて TLE だった。アルゴリズムのオーダーが間違っている。N の二乗に BIT 由来の log をくっつけたのが良くなかった。■提出 #27509632 (TLE×15)。同じ TLE とはいえ実行時間は 44xx ms から 40xx ms に改善している。ここからは定数倍の改善で 100 ms を稼げばなんとかなる。この提出では二重ループの内側で BIT を利用するのをやめて N^2 のループで前処理をした。処理を１か所にまとめようとしてループを重ねて計算量のオーダーを悪化させるより、同じオーダーのループを２つ並べる方が速いということが盲点になっている。Maximize GCD のときも気がつけなかった>20210919p01.03。今回のメインループは N^2 なのだから、大概のことが前処理でできる。BIT の代わりになる N 個の累積和(配列)を用意しても許される。■提出 #27510644 (AC / 3120 ms)。前処理で扱う配列の長さを必要な分だけに切り詰めた。要素数の合計が N*N から N*(N+1)/2 に減ったと思う。あとは配列参照を減らしたり数字の微調整をなくしたり reverse_each をなくすために最初から逆向きの配列を用意したりという爪に火をともす努力。そういうの好き。結果として AC 提出が一番短くなって 277 Byte。