最終更新: 2020-12-01T21:25+0900
今週は ABC がないようなので精進である。D 問題が「コンテスト時間中には解けなかった」ので E 問題は問題文を読みさえしなかった。
一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、４要素の配列でまかなえることの発見が。
今のところ２番目の提出より倍くらい速いみたい。だけど書き方による違いかもしれないね。
この人の名前は AtCoder を初めて日記に書いた 20190907 のこの部分(20190907p01.05)で初めて目にした。このときも Python で一、二を争うくらい速くて、同じくらい速い他の複数の提出から参考にしたと参照されていた。
参考にできるところがあるだろうか。
自分のスクリプトで気になっているのが r0[c] = vs.max と書いた部分で、長さ 4 の vs 配列のうち 1,2,3 番目は基本的に昇順ソート済みなのだけど、0 番目にイレギュラーが飛び込んでくるせいで vs[3] や vs[-1] とは書けずに vs.max と(４要素とはいえ)配列を走査するほかなくなっている。
up = dp[i - 1][j][3] for w in range(4): dp[i][j][w] = max(dp[i][j - 1][w], up)
上のように、隣の行から値を引っぱってくるときに最大４要素を更新すればすべてソート済みであるとして末尾の要素を最大値として取り出すことができるんだけど……
もうわからぬ。
違いは入力 RCV を配列に記録するかハッシュテーブルに記録するかだけ。速くてメモリ食いが配列。遅い方がハッシュテーブル。要素数が少ないときはメモリ食いなのもハッシュテーブルの方なのであって、(メモリと GC が気にならない限り)いつでも配列を使っていきたいんだけど、この問題について言えば、R×C に比べて K がかなり少ないみたい。制約が「1 ≤ K ≤ min(2×10^5, R×C)」だから、最悪の場合が 900 万になるか 20 万になるかという違い。
ところで、いくつか見た感想なんだけど、作業配列は C+4 要素で十分だと思うんですよ。C×4 でも C×4×2 でもなく。入力を記録する R×C サイズの配列の前では霞んでしまう違いだけども、numpy の場合のパフォーマンス特性はわからないけども、要素の更新量は確実に減る。
Python で一番速い提出 #16084621 を読んだ。コンパイル済みのバイナリを書き出して実行するなら Python である理由がないじゃん、と思ったんだけど、元になった Python のソースをちゃんと読めるようにしてくれている。コンパイル前のソースが Python なのだった。
長さ C の作業配列が昇順ソート済みだという特性が活用できていなかったことがわかったので、それを踏まえたコードに。あまり速くはならず。結局 R×C 回配列を更新するところは変わりがないから。
配列を昇順ソート済みにするための書き込みを省いて、配列の重複のない範囲から最大値を抽出するだけにすれば良くなると思った。倍遅くなってメモリ消費も激増した。むしろ逆で、予想外のメモリ消費がスローダウンを招いた？ Array#[] か Array#max に何かある？
vs[0] = [vs[0],r0[c0..c].max].max # r0 に関わらない処理 r0[c] = vs.max
だったものを
vs[0] = [vs[0],r0[(c0..c).max_by{|i|r0[i]}]].max
# r0 に関わらない処理
r0[c] = vs.max
に書き換えたところ、１つ前の異常なメモリ消費、異常な実行時間だったものが、２つ前よりメモリも時間もやや悪いという、予想の範囲内の結果に収まった。
いや、悪くなってるのはがっかりなんだけど、１つ前の悪くなり方はやはり尋常じゃなかった。配列に最大値を聞くのではなく、添字の範囲を使って配列の最大値を求めるという回りくどいやり方より遙かに遅かったのだから。
素直なやり方で予測可能な結果が出るなら速かったりしないかなあ。
困ったときのセグメントツリー。もう３回目の実装なので空で書いてバグも無し(でも一応内部データを目視するテストはした)(１回目と２回目は空で書いてバグだらけ)。メモリ参照の局所性なんて関係ないハードウェアから遠い言語でできる悪あがき。今のところのベスト。こんな作業ってアルゴリズムひとつで桁違いの差をつけて置いて行かれる類のものだ。楽しくはあるけどこれで終わり。
@l の利用場所すべてで @l+1 って書いてるから @l の定義から -1 を削っておけば良かった。
* コンパイル済みのバイナリ展開とか。