/ 最近 .rdf 追記 編集 設定 本棚

脳log[20190916] AtCoder Beginner Contest 141/D 問題 Powerful Discount Tickets



2019年09月16日 (月)

最終更新: 2020-05-06T23:25+0900

[AtCoder] AtCoder Beginner Contest 141D 問題 Powerful Discount Tickets

Ruby による提出一覧

  1. 最初の提出 (TLE)

    問題文に書かれた操作をそのままコードにしたらほとんどが TLE で全然ダメだった。ソート済み配列に find_index を使ったのが間違い。

  2. 2番目の提出 (TLE)

    find_index を bsearch_index に置換したら3つを除いて AC になったが、やはり時間をかけすぎている。

  3. 後日の提出 (AC / 221 ms / 30216 KB)

    Ruby で一番スマートな解法にくらべてメモリも時間も倍以上かかる力業。例によって例のごとく風呂場で思い付いた。

    あとで知ったのだけど、Ruby には Integer#bit_length という便利メソッドが予め用意されていた。Ruby 1.9 にはなかったメソッドだ。しかしこの前ランタイムエラーを食らったから、AtCoder の Ruby(2.3.3) には Array#sum なんていかにもありそうなメソッドがまだ実装されていないことは知っている。参照してるドキュメントのバージョン(複数)も、ローカルにインストールしてる Ruby のバージョン(複数)も、全部がばらばらなんだよなあ。

  4. 後日の提出(bit_length を使った版) (AC / 149 ms / 11776 KB)

    少し前(20190628)に見かけた MSB 関数をコピペ利用する代わりに組み込みの Integer#bit_length を使うようにしたら、アルゴリズムの優劣は覆せないものの、メモリは同程度、時間は倍に至らない程度にまで改善した。たぶん2回ソートしてるのが良くない。割る2をシフト演算に読み替えて応用が利かなくなってるのに、速さで負けてるあたりがなお良くない。

  5. 番外1:最初の提出でソート済み配列の代わりにヒープを使っていたら (AC / 803 ms / 13604 KB)

    TLE(2秒越え)にくらべたらまあまあ悪くないタイムでやんの。

    訂正:提出したスクリプトに max, min = @h[0], @h.pop という行があるが、min は最小の要素ではない。単に末尾の要素。

  6. 番外2:番外1のチューニング (AC / 549 ms / 10252 KB)

    1. loop メソッド を while 文に。(Q#up_heap, Q#dn_heap)
    2. 要素の交換を繰り返すのではなく、位置が確定してから一度だけ代入するように。(Q#up_heap, Q#dn_heap)
    3. @h.size 値をキャッシュ。(Q#dn_heap)

    これで3割ちょっとの時短。でも JavaScript(Node.js)の提出でもヒープを実装してるのだけど、そちらは 100 ms 台で完了しているのだな。それも値の合計に Q.pop を使用していながら。値の取り出しとそれに続くノードの降下が一番時間を食うというのに。

 Ruby で一番速い解答に学ぶ

2本目の待ち行列(FIFO)を用意すればそれをソート済みに保つのは雑作もない(※)、というのがこの問題の肝であった。長さ M を確保しておけば固定長配列で十分でもある。

1本でやろうとするから、余計な面倒と時間コストがかかる。

※やっぱりまだちょっとわかってないかも。割る2をして2本目の待ち行列の末尾に加える要素と、それまで末尾だった要素の大小関係が一見ではわからない。これがわからないから、毎度のソート(順序維持)操作をしてしまう。

たぶん2番目の待ち行列に飛び込むタイミングがキー。そこから導かれる。でも、うーん、はっきり見えない。操作の前後で2本目の待ち行列の全要素が重なりなく前後に位置するというのが。