Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

いっ・・・いもす法出たー

AOJのDSLを全部解きました。全部Rustです。

f:id:akiradeveloper529:20190307134651j:plain

内容としては

  • Union Find (重みつきもある)
  • セグツリー (遅延多め)
  • スライド
  • 圧縮
  • いもす法

です。重要なトピックが詰まってると思いました。

自分としては、AOJのライブラリコースの中ではこのDSLとDPL(動的計画法)のものは全部やろうと思っています。問題をランダムに雑食していくよりは、まとまったコースで重複なく学習していく方がエッセンスが整理された形で習得出来ますし、重複もないです。あとは蟻本などの本も、その本自体では整備されているので併せて学習しています。複数の本をやるとエッセンスが重複していることもありますが、「所詮は定数倍」「どうせ蟻本が一番重いから」と割り切ってます。私のあとに競プロ勉強を始める人の参考になればと思います。

最後の問題がいもす法

さて、DSLの最後の問題はいもす法でした。

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B

f:id:akiradeveloper529:20190307134704j:plain

座標が0-1000なのでグリッドを作ってシールを一つずつ張っていってグリッドの中身のカウントを増やしていくというのは11乗の計算になりますから明らかにアウト。いもす法の出番ということになります。

https://imoz.jp/algorithms/imos_method.html

いもす法のアイデアは、リンク先に詳しく書いてあるので再度説明する必要もないかと思いますが、「ある領域に全部何かを足すということは、その端っこに値をおいてから累積和をとることと同じだ」ということです。上の例であれば、ナイーブに考えると、(103)2 x 105というギャグのようなオーダがかかりますが、いもす法を使うと、最初に105コストを払って端っこに値をおいて、(103)2のスイープをすることですから、106オーダとなります。

f:id:akiradeveloper529:20190208154936j:plain

このアルゴリズムは、自力で思いつくのはかなり難しいと思います。何か工夫が必要であるということは誰でもわかると思いますが、では具体的にどうやって計算量を減らすかは、ふつうは思いつかないでしょう。

一つ前の問題も実はいもす法

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_A

f:id:akiradeveloper529:20190208155946p:plain

実は一つ前もいもす法といえばいもす法です。しかしこちらは、ナイーブにシミューレーションするのが無理ということに気づいたあとに、「時間ごとに出ていった人数と入った人数を計算してしまってからシミュレーションすれば良いでしょう」ということに気づけると思います。理由は、2次元のいもす法のようにシミュレーションからスイープへの飛躍がなくて、あくまでもシミュレーションに使うデータを最初にまとめて小さくしてるに過ぎないからだと思います。実際に私の自力解答は、enterとleaveという2つの配列を用意していますが、いもす法を前提とすれば1つで良いはずです。

    for t in 0..T+1 {
        cur_n = cur_n + enter[t] - leave[t];
        max_n = max(max_n, cur_n);
    }

しかし、これも実はいもす法だということが図を書けばわかります。lに入ってrに出たということは、言い換えるとlからr-1まではいたということで、lからr-1まで1を足せばよいということになります。つまり、いもす法に従えば、lに+1、rに-1をおいて右スイープをすればいいということになります。

f:id:akiradeveloper529:20190208160411j:plain