今日解いた競プロの問題。
競プロ典型90問
030 K Factors: 1~Nまで全て素因数分解すれば$O(N\sqrt{N})$で解けるが、これでは遅すぎるのでOsa_k法で高速化すると$O(N\log N)$になる。$N=10^7$なので$N\log N$が通るかどうかは微妙なところだが、C++ならギリギリ通る。配列にvectorを使ったらTLEしたので生配列を用いた。
こんなごり押し解法はまず想定解ではないだろうなと思ったので別のやり方も考えた。まずエラトステネスの篩でN以下の素数を全列挙。$O(N\log \log N)$になる。それからそれぞれの素数を素因数として使うN以下の数を、小さい素数からDFSで全探索。同じ数を二度調べることはない(はず)なので一応$O(N)$になっているはず？？300ms程度と余裕を持って通った。
想定解はもっときれいだった。問題としているのはそれぞれの数が何種類の素因数を持っているかなので、c[2], c[4], c[6]…に1を足す、c[3], c[6], c[9]…に1を足す、c[5], c[10], c[15]…に1を足す、という風にエラトステネスの篩のようなやり方で数えていくというやり方だった。頭が良すぎる。エラトステネスの篩と同じ遷移なので計算量は$O(N\log \log N)$になる。
017 Crossing Segments 難易度☆7だが自力で解けた。うれしい！
まず全組み合わせを調べて$O(M^2)$で解いた。これで小課題1は通る。$(L_i, R_i)$と$(L_j, R_j)$が交わっているか調べるとき、$L_j, R_j$の二つのうち片方が区間$(L_i, R_i)$の中に入っていてもう片方が区間$[L_i, R_i]$の外にあるならば交わっている。
次に、「区間を条件に数えている」あたりが高速化できそうに見えたので高速化した。
まずそれぞれの点について辺情報を持っておく。(例えばgという2次元配列を持っておき、(L,R)=(3,5)という線分があったらg[3].push_back(5), g[5].push_back(3)としておく。)
そして$(L_i, R_i)$と交わる線分を列挙する場合、$g[L_i + 1]$から$g[R_i – 1]$までの各点について、$L_i – 1$以下の値と$R_i + 1$以上の値の数を調べる。事前にソートしておけば二分探索で解くことができる。二重にカウントしてしまうので÷2することにだけ気を付けると$O(MN\log N)$で解けるはず。
$MN=10^8$なのでかなりきつく、そのままではTLE。よく考えたら$L_i-1$以下の値と$R_i + 1$以上の値の数の両方を数えていたのをどちらか片方数えるだけにすれば、そもそも二重にカウントすることはないので÷2する必要もない。辺も両側から張る必要はない。これに気を付けたら2倍高速化になって通った。
最後、「区間内の全ての点について数えている」あたりが高速化できそうに見えたので高速化した。
考察のためにLとRを二次元平面にプロットしてみたら、各辺についてある矩形領域の中の点を数えればいいことが一瞬で分かってしまった。こういう場合は平面走査法をすれば通る。適宜ソートして区間の点の数の管理にBITを使えば$O(M\log N)$で通る。終わり。
気持ちよかった～。
なんかすごそうなのでメモ。Chromiumのアーキテクチャの解説を東大講義かなんかでやってたらしい。
斎藤環「ひきこもりはなぜ『治る』のか？」読了。
- 義務と欲望の区別がつかない状態だと身動きがとれなくなる、というのはかなり心当たりがある話だと思った。しかしここで言う「義務」の正体が今一つ掴めなくて消化不良。
- 他者との対話をするにあたり、メールや電話ではダメで直接会って話をするのでないといけない、というのをかなり念押ししていたのが気になった。それなり説明もしていたが今一つピンと来ず。思うに、「勘ぐり」が発生するようなコミュニケーションではいけないのだという話と解釈した。
- 「他者との対話」の必須性を理論的な面から説明してくれたのがかなり良かった。
昼にチャーハンを作った。チャーハンを作るのにちょっとずつ慣れてきている。
腕立て伏せをやった。明日は腹筋。
Categories: 未分類