最終更新: 2022-02-11T22:02+0900
先日解いていた「JOIG 2021/2022 本選競技課題」(テストケースのダウンロードができる) の F 問題へのこの提出に関して>20220129p01.05。
Hash#shift を意味がある限り繰り返したあとで Hash#clear を呼ぶようにしている(25 行目)。shift は破壊的なメソッドだから shift を十分に呼び出した後の Hash は空になっているはずで、clear を呼ぶ意味はなさそうに思える。それでも呼ぶようにしているのは、これがないとテストケースの in/05-01.txt に限ってスクリプトの応答がなくなって TLE になると思ったから。少なくともローカル Windows 環境では Ruby-2.7 と Ruby-2.5 で止まる。Ruby-1.9 は平気。他のテストケースでは止まらないけど、問題のケースでは必ず止まる。止まるタイミングはバラバラだけど、いずれも Hash への代入で止まっているようだった。
再現スクリプトはこんな感じ(これを見つけたから日記に書いている)。他所で再現するかは、どうでしょうね。
Many = 100 # 10 回では少ない。テキトーに大きく。
Some = 100 # ウチでは 30 回目までは到達しない。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]
Some.times{|some|
warn "#{some} begin"
hash = {}
Many.times{
some.times{|j|
k = Random.rand 0..Many
hash[k] = 1 # maybe hang
}
0 while hash.shift
}
warn "#{some} end"
}
warn :exit
Ruby-2.5 と Ruby-2.7 では "N begin" (N は 20 前後) を表示して止まる。2.5 より 2.7 の方が早く止まるという傾向はあるけど、具体的な回数にはバラツキがある。それはまあ乱数を使ってるからだと思うけど、ハッシュのキーを k に代えて j にしたり、シャッフルした順列にしたりすると止まらなくなるので(正常動作)、乱数は外せない。
こういう Issue「Bug #17779: 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる - Ruby master - Ruby Issue Tracking System」を思い出したけど、全然関係はなさそう？ 全然わからない。
AtCoder のコードテストを使わせてもらったら(目的外失礼)、こういう結果。AtCoder の Ruby も今のバージョンは 2.7。
| 終了コード | 9 |
| 実行時間 | 10501 ms |
| メモリ | 9112 KB |
標準エラー出力は 30 begin で途切れている。完走しても 10 秒もかかるはずないから、ハングして実行を打ち切られたのだと思う。コードテストとジャッジサーバーが同じだとして、ジャッジサーバーのスペックはこう>Linux ip-***-***-***-*** 4.15.0-1041-aws #43-Ubuntu SMP Thu Jun 6 13:39:11 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux*⁑。
Ruby-3.1 が「ウチの Ruby」に今日加わりました。大体ループの 20 から 30 回目で止まるんだけど、弾みで 2 回だけ完走したりもした。
パラメータが２つもあると面倒なので。
改訂するにあたって予想外に止まらなくなったりした(正常動作)のを通して、たぶん直接的な原因もわかった。
# ウチではだいたい 20 から 30 回で "empty?: true" を最後にして止まる。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]
# ウチの Ruby-3.1: ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x64-mingw-ucrt]
H = {}
100.times{|n|
while H.size < n
k = Random.rand 0..1<<30
H[k] = 1 # たぶんここで止まる。
end
warn "size: #{H.size} before shifting."
H.shift until H.empty?
raise if H.shift # no exception. だけど Hash が空になった後の shift が後でハングをひき起こす？
warn "empty?: #{H.empty?}"
}
warn :exit
Hash を空にする方法として 0 while H.shift を選ぶとその後の Hash#[]= でハングするが、Hash を空にする方法として H.shift until H.empty? を選ぶとハングしなかった。条件を揃えていくと、Hash#empty? が作用してハングを回避しているのではなく、Hash が空になったあとの Hash#shift がハングをひき起こしているようだった。ちなみに Hash#clear にハングを回避する効果があるらしいのは、JOIG の問題への提出で確認済み(とはもう書いた)。
投稿して次に見たときにはすべてが終わっていた。早いぜ。
こういう仕組みだったようです。
メモ：entries_bound は使用中のビン（DELETEDになったビンを含む）の数に（ほぼ）対応していて、これをみてテーブルをリビルドしている（rebuild_table_if_necessary）。空のハッシュに対する Hash#shift はなぜか entries_bound を 0 にしているので、リビルドすべきタイミングを逃し、ビンがすべて使用中になった状態で空きビンを探そうとするので無限ループに陥っていた（find_table_bin_ind）。
Strict-Transport-Security: max-age=31536000; includeSubDomains, max-age=31536000; includeSubDomains; preload が送られて来るようになって困っている。二重指定とカンマ区切りと。Firefox はコンソールに Strict-Transport-Security: サイトに指定されたヘッダーを正しく解析できませんでした。 とメッセージを出してページを処理してくれないのだけど、他に困っている人はいないのか。'L' でも 76 でもなくて ?L.ord なのよね。ま、５分(考えようによっては５分50秒)の違いは大差ないやろ。■@2022-01-31 01:12 提出一覧から 2022-01-30 21:25:29 の提出が消えたみたい。ペナルティ５分が消えて嬉しい。最終更新: 2023-07-22T23:29+0900
- タクシーが赤色の場合，乗車後の所持金が a−1 円になる．
- タクシーが青色の場合，乗車後の所持金が「a÷2 を整数に切り捨てた値」円になる．
町 1 から出発し，1 円以上の所持金を残した状態で町 Tj に到着するために，最初に少なくとも何円の所持金を持っている必要があるか
問題のこの部分は、まあ、逆に考えます。所持金が１の状態でスタートして、所持金が +1 になる、×2 になる、というように。そうすれば初期金額を探索しなくて良い。ただしそれぞれの町をスタート地点に設定して町１への最短経路を繰り返し求めるということは許されていないので、スタート地点は町１のままにしておきたい。
ところが町１を１円でスタートして、+1/×2 しながら各町に着いたときいくらになっているかをダイクストラ法で求めてもサンプルが合わない。合わなかった。
たぶん、-1/÷2 の逆計算は +1/×2 でいいのだけど、((((-1)-1)÷2)-1)÷2 の逆計算は ((((×2)+1)×2)+1)+1 ではないとか、合ってるけどその通りに計算できていないとか、そういう理由。
わからんなりにテキトーに 2×2 の正方行列に 2 とか 1 とか 0 を割り当てて実際に計算してみれば、必要な係数が２つだということと、それをどう変化させればいいのかがわかった。スクリプトの中の x,y = x,x+y と x,y = x+x,y というのがタクシーごとの変化。式を見ても意味はわからない。
逆計算がわかったからダイクストラ法で解けたかというと、小課題の４あたりから答えが稀にあわなかったり時間をオーバーしたりする。した。小課題の３までは問題のグラフが木だから複数の経路の競合がなかったのだな。
これはたぶん、ある町における状態というのが所持金というパラメータ１つで優先順位を付けられないせいだと思う。さっき x と y の式を２つ書いたけど、そして所持金というのが d = x+y で表されるのだけど、ある町からある町へ移動するにあたりどちらのタクシーを使っても所持金の変化は x+x+y == d+x で共通している。だけどその次の移動での増加量が x の値にのみ依存するので、x を増加させることで所持金を変化させたタクシーの方が分が悪い。
２つのタクシーの運賃を普通の経済感覚で比べてみると、どの場合でも所持金が１円減るだけの赤色のタクシーを利用できるときは利用して損をすることがないことがわかる。たぶん。01BFS みたいなステップを踏めば解けるような気がするなー。
頭の中が整理されていないので無駄がまだあると思う(嘘解法の可能性も大いにある)。でも１秒しかなかった JOIG-2021-F「デジタルアート (Digital Art)」(20211210p01) と違って制限時間が４秒もあったので間に合った。嬉しい。
D 問題まではやるだけだったけど、E 問題「エゴイ展 (EGOI Exhibition)」がまだ解けていない。価値の正負と絵の種類で場合分けとクラス分けをして DP をしようとしたんだけど……。
PQ#dn_heap がバグってるね。不等号の向きが逆。これは要するに、PQ には繰り返す幅優先探索の無駄を気休め程度に取り除く意味しかなく、実際にはその効果さえなかったということ。
PQ#dn_heap のバグをとったとしても定数倍が重いせいで、初期パラメータが異なる複数の地点をスタート地点に設定した幅優先探索のようなものを、距離の更新がなくなるまでぐるぐる回した方が速い。優先度付きキューを使うと確かに最短距離を複数回更新するという無駄はないのだけど。
Array をキューにするのと Hash をキューにするのでは Hash の定数倍が重い。キュー内で要素が重複することを気にせず Array につっこんだ方が速かったりする。
そんな(良くない)理由でメインループ内の前半のループのキューは PQ でも(後半のループのように) Hash でもなく Array になっている。
キューを２本持つことでプライオリティキューを使わないでもソート済みの状態を保ちながらキューを伸ばせる場合があるというのは、AtCoder について書いた２番目の日記に書いてある>20190916p01.01。今回もこれが使える。
863 ms というのは Ruby に限らない AC の中で１ページ目に入っているのだ(全部で９ページではあるのだけど)。
S[j]-S[i] で和を求めるときに、i<j でも j<i でも構わないということ。符号を入れ替えればいいだけ。そしてこの問題に関して言えば、問われているのが絶対値であることで符号の入れ替えさえ不要だった。絶対値が問題を面倒にしているとばかり思っていたぜ。■提出 #28807480 (AC / 232 Byte / 1853 ms)。累積和をソートすることも解を二分探索することも早くからわかっていた。二分探索の中で数列をスキャンする中で j<i となるケースを除外するために BIT なりで対数時間の処理を加えてしまうと Nlog^2 になって困ったなーと考えていた。事前にじっくり準備して BIT に頼らないデータ、それも N×N よりコンパクトなデータが作れないかなーと考えていた。実は j<i となるケースを除外する必要などなかった。累積和の使い方がわかっていない！ 精進の道とは自分のアホさを確認する道なのか。+/- に応じて +x/-x するというのが縦の見かたなら、M に応じて x を +1/-1 することが +x/-x する操作にそれぞれ何回寄与するかを考えるのが横からの見かた。提出 #28608177 (AC / 157 Byte / 72 ms)。気がつくと簡単に答えが出て気持ちがいい。■横からの見かたが培われたのはたぶんこのとき>「足し算とはそういうものだ、と言われたら言葉がない。私は足し算がわかりません。」 なんだ、より難しい類題を解説 AC していたから解けただけだった。