脳log[20221208]

2022年12月08日 (木) [AtCoder] 精進。CODE FESTIVAL 2016 qual C-D「Friction」(黄 diff)。AC じゃないよ、部分点だけ。ローカルで最大ケースが安定して 50 秒だから、ジャッジサーバーが倍速だとして 13 倍の定数倍改善で通ると思う。■まずは問題を理解する。摩擦が発生するのは列と列のあいだ。最小単位２列について考える。戦略としては右をどんどん下げていくか、左をどんどん下げていくか、どこかのレベルからは左右を交互に下げていくことで摩擦を最小にできそう。端っこを除いては摩擦面が左右にあるけど、それによって一面の都合によって下げたいけど他面の都合で下げたくないというジレンマは生じなさそう。全体を通して下げる順番を調整すればどの摩擦面にとってもベストな選択が可能。そういう調整が可能なので列を下げるか上げるかには違いがない。一貫してさえいれば、配列を反転したりしなくていいし、頭の中を決まった方向に整理したりしなくていい。■提出 #37100541 (300 点 / TLE×13)。メモ化 DP。提出総数が少ないというのはあるけど、Ruby によるすべての提出を見ても AC がない。できるはずだ。■累積和の要素数をケチったのとメモを Hash から Array に代えたら 24 秒になったけどこれは２倍の改善でありあと６倍足りない。しかも答えが一部合わないし。■答えが合った。コードテストで 10.X 秒だからやっぱりあと６倍(切り上げ)の改善が必要。■メモ配列を無理に１次元化せず２次元配列にしたら 8.2 秒になった。■演算子をケチって 7.6 秒になった。■lambda を普通のメソッドにして 6.9 秒。AC は 2 秒……。再帰じゃなくてメモ配列を埋める普通の DP にしたらどうかなあと思うけど、右を下げる遷移と左を下げる遷移をどんな感じで一列に並べてループにできるか迷う。■どうも考察が足りてないみたい。こちらの提出 #949122 (PyPy / AC / 989 ms) を Ruby に移植してみたら 4.6 秒だった>提出 #37243589 (TLE×12)。よくわからない遷移。そしてすでにミニマムなこの解答を倍以上速くすることは無理だ。Ruby の将来に期待！