脳log[20220111]

2022年01月11日 (火) [AtCoder] 精進。第九回 アルゴリズム実技検定 過去問-M「名前の変更」。やることは明確で簡単(英語の問題名が「Deadnames」ってこれヒントですよね？ 言語差別だー)。問題は制約の大きさ。BIT でやった>提出 #28465041 (AC / 1054 Byte / 2778 ms)。提出したスクリプトで BIT#index が担当する、値から添字を逆引きする処理をこれまで書いたことがなく、できるかどうか、どうやるのかも知らず、デバッグに大変苦労した。そういう処理を書かなくても BIT#[] メソッドと二分探索を組み合わせて代わりにすることはできるだろうけど、計算量が log^2 になるのが問題になりそうだった。その失敗は LCA のダブリングを初めて書いたときにすでに経験している>20210617p01.02。log が log^2 になったとき 2778 ms が制限時間の４秒におさまるかどうかは、どうだろう。ところで、サイズ N の BIT を N より多く確保して許されるかどうかは運でした。■Python で一番速い提出では BalancingTree という構造を使っていたが知らない>#28312971。その次の人は AVL 木という名前の構造を使っていたが知らない>#28339871。Python で一番短くて速い提出が２つのメソッドと２つの配列で何をやっているのかはさっぱりわからない>#28288268。■どうせ運に任せるのなら N×N の規模の BIT を１つだけ使うのでも良かったのでは？>提出 #28467644 (AC / 757 Byte / 2894 ms)。ちょっとだけ遅くなった。