問題 atcoder.jp 問題概要 長さLの木材がある．以下のQ個のクエリを処理せよ． i番目のクエリは(ci,xi)で与えられる． ci=1のとき：木材の左端からxiの地点で木材を切る． ci=2のとき：木材の左端からxiの地点を含む木材の長さを出力する． 1≤L≤109 1≤Q≤2×10…

問題 atcoder.jp 解法その1 numpy + njitを使ったO(N3)解法 なんと、何も考えずに問題通り、総当たりコードを書くとACしてしまうという解法。 マジですか。 AtCoderのPythonではnumpyが使用できるが、njitを使って関数の実行速度を高速化。 実行すると、1731…

問題 atcoder.jp 解法 数列A、数列Bが2 x 105なので、A,Bの全要素に対して総当たりだと、2 x 105の2乗なので108越えでTLE確実。 なにか最適化する必要がある。 おそらく二分探索だろうと、検索したところ、そういえばbisectという便利ライブラリがPythonには…

AtCoder ProblemsにRecommendationって機能あって、ユーザことにオススメの難易度の問題を勧めてくれるんですよね(Atcoder Problems -> User -> Recommendation)。 茶diffやるべきだろうなと思ってたら、見事に茶の問題ばかり勧められるので、素直にやってき…