最終更新: 2020-10-18T20:31+0900
D 問題をしばらく考えて、
完全に内 = lambda{|n,a|
next (1+(n-a).abs).pow(2,M)
}
はみだし = lambda{|n,a,y|
n,a = a,n if n < a
y = a-1 if a-1 < y
next [完全に内[n+y,a]-完全に内[n,a],0].max
}
みたいな関数を書いたりしていたんだけど、ここから詰め切れる見通しが立たなかったので E 問題に手を出した。
方針はすぐに決まった。逆に考える。照明の置き方が 2^k 通りを網羅しているのだから、照明の置き方を考える必要がない。あるマスを照らす照明の置き場所が何か所あるかを数えることにする。
もちろんグリッドを１マスずつ移動しながら４方向に探索を進めるようでは TLE を免れない。N の上限が 2000 の時に 2N^3 マスの走査は認められない。
lambda P が４方向の探索を省力化する工夫なんだけど、２回の P の合計が後半の N^2 のループと同じくらいの重さであり、N^2 の上限が 400 万だということはループの中身がごく簡単な処理でなければ Ruby は１秒２秒で終了しないので、N^2 ×２の結果は TLE だった。
TLE の山を見てわかる通り、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば考えるより先に手を動かすのみ。
構造はほとんど同じ。lambda P の代わりの lambda F が４、５倍速いおかげで AC になった模様。スクリプト言語は自分で書いたスクリプトとランタイムライブラリの処理速度に雲泥の差があるので、プリミティブな処理を自分で書かずにいかに丸投げするかが肝要。
それと、２の冪乗を含む掛け算は展開すると一部がループの中身に関わらない定数になって外に出せる。２のＫ乗を１回だけ計算しておけば、ループの中の２の累乗計算は１回だけでいい。もちろんその計算結果は２回目３回目に備えてメモしている。
最終更新: 2020-10-17T17:20+0900
C 問題が解けなくて大爆死した回の ABC。「時間内に B 問題までしか解けなかったので今日の日記は C 問題」。F 問題が解けたら D と E も解けたつもりでいいんじゃないかな？
どういうデータであればクエリに答えが出せるか、どういうデータ構造であればひとつひとつのクエリに妥当な時間で答えが出せるか、とっても考えた。
「LOC (last occurrence of colors)」とか「QIR (q in range)」といった名前をとっかかりに部分的に形を作っていった結果、移動する終点に合わせて始点用のデータを(事前に用意するのではなく)継続的に発展させていくやり方に落ち着いていた。
色の列を空間としてではなく時間として処理すること*が振り返ってみての転換点。意識してではなく手探りで進めるなかでの変化だったけど。
でも TLE。ソート列やハッシュ表といった素朴な構造ではダメみたいだ。
BIT を持ち出しても TLE とは恐れ入りました。ソースコードが長くなるのが仰々しくて嫌だとか言っていられない。
TLE の山と AC 提出の実行時間を見るに、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば(略)。
配列と BIT に余分な要素を付け加えて単項マイナス演算子と引き算の数を減らしたり、配列の初期値を工夫してループの中の if を取り除いたり、1-origin な入力値を 0-origin に加工するのをやめたり、i-=i&-i を i&=i-1 に代えて演算子を１つ減らしたり、といった泥臭い改善の成果で AC。
こういう脳筋的努力は考察不足の可能性がちらつくと身が入らないのだけど、その心配はなさそうなので心置きなく。
これが Ruby で一番速い(しかも Ruby で一番早い AC でもある)。速さの秘密はよくわからない。クラスやメソッドなしですべてが一体だからだろうか。 初めて見たのだけど BIT の初期化をするこの行……
b = (0..n).map{|x|x&-x}
BIT 実装のキーでもある LSB を蓄えるこれは公差１の等差数列を初期数列にしようとすると現れる。蟻本の図を見ていたのだけど、LSB は内部配列の要素が分担する重みに対応している。倍率(公差)は好きに決めたらいいだろう。
BIT の初期化が多少複雑になっても実行時間でペイするのは変数 u の存在がある。自分の提出で答えを設定する式は Ans[q] = r-l+1-Dup[N-l] (変数 Dup が BIT) だけど、BIT の初期値の工夫により -l が消せても +1 も N-l も残る。そもそも BIT を使用する向きが違っているのだ。BIT から２回値を参照するのを嫌って自分は向きを決めたけど(※BIT の操作が一番のホットスポット)、変数 u があれば参照が１回節約できる。参照が同じ１回なら他の部分の有利が生きるということなのだろう。
* この「空間」と「時間」はユニバーサルな表現ではなかったかもしれない。三次元に囚われた話者の感覚に根差した主観的な意味が込められていて、理解する前提条件になっていると思う。