README
¶
ABC149 感想
久しぶりにunratedとなってしまった。 おそらく途中離脱者も多くいたと思われるので、推定パフォーマンスはわからない。 Dまでしか解けなかったがおそらくいいとこ水パフォだと思われる。
- A問題はただ文字列をconcatして出力するだけ。
- B問題は意外と苦手な
O(1)算数、とはいえ落ち着いてやれば簡単。 - C問題は素数の「密度」みたいなものを問う問題。
xが与えられるのでそれ以上の最小の素数を答えよ、という問題。- なんとなくで
1000000ぐらいまで素数を求めればいいだろうと思ってエラトステネスの篩を貼った。 - が、普通に
xから素数判定を愚直にシミュレーションしていけばどこかで簡単に見つかってしまう。
- D問題はDP、、ぽいがよくよく見ると
mod kごとに文字列を取り出して処理すると、貪欲的に解けてしまう。 - E問題はcake123を強くしたような問題。
- 制約が厳しいので、cake123のやり方では解けない（多分）。
- 高速フーリエ変換の初歩的な問題ともなるらしいので、いつか思い出して解き直したい。
E問題復習（2020-01-09）
公式Editorialの累積和をフル活用して O(nlogn) で求めるやり方はよくわからなかった。
その代わりにkmjpさんのブログ解説記事で説明されている、
O(n(logn)^2) のやり方はわかりやすかったため、こちらを実装してみた。
まず、ある x で、ペアの和が x 以上となるものが m 通り以上存在するような x の「最大値」を、
二分探索によって求める（ x は小さいほどそれ以上のペアの数は多くなるので、最大値がほしい）。
そして大きなゴールとして、「 x 以上の和を持つペア全てについて総和を計算する」というものを置く。
これ自体は、再び二分探索をするのと、累積和を併用することによって求められる。
しかし、それによって m 回以上の握手が行われているため、余分に足し算されていることが気になる。
実は、これは後で微調整ができる。
なぜなら、先に求めた x とは境界値であるため、 x+1 とした場合は m 通りに満たなくなる。
つまり、 m 回を超過した分はすべてペアの和が x ぴったりの握手と言えるため、
超過分を e とすると、 x*(m - e) を引き算してやることで、微調整が正しくできる。
計算量のボトルネックは、 x を求めるところで O(n(logn)^2) となる。
実装してみた感想
典型: 二分探索の中で O(nlogn) の判定を行う O(n(logn)^2) のアルゴリズム
。。という風に言えるのかもしれないが、結構複雑だった。
めぐる式二分探索はネストされるとかなりコード行数が増えて慌てることになる。 無名関数をやめて、適宜関数定義として外に定義しないと混乱する。 また、変数名の変更も検討したほうが良い。 とにかく、実装は慎重にすすめる。
また、改めてめぐる式の以下の大事な点を認識したい。
- 最初に設定された
ng, okは絶対にmidには入らない。 okは一回も動かない場合がある。- 最終的に
okが参照すべきものとなる。
忘れていたわけではないが、忘れたときには備えておきたい気がする。
Directories