「小技」の記事一覧

平方分割で区間の最大値を求める大量のクエリに対応するの続きです。前回は最初に整数の配列が与えられましたが、その配列の値が更新されることはありませんでした。今回はある区間の最大値を求める ＋ ある区間で配列の値が更新される・・・

続きを読む

最初に大きなサイズの配列が与えられ、そのあと区間[a, b]の値にXを加えよとか、区間[c, d]の最大値を求めよとか、区間[e, f]の総和を求めよというクエリが大量に飛んできて、しかもそれらの結果を2秒以内に返せとい・・・

続きを読む

二分探索法を活用することで全探索をするよりも計算量を減らすことができます。 全探索でもできるが・・・ A05 – Three Cards 赤・青・白の 3 枚のカードがあります。 太郎君は、それぞれのカードに・・・

続きを読む

変なタイトルですが、こんな問題です。 パイプを切り出そう n 本のパイプがあり、長さはそれぞれ A_1, A_2, …, A_n です。今、n 本のパイプから k 本の同じ長さのパイプを切り出すことを考えます・・・

続きを読む

C# 二分探索法で配列のなかから最も近い値を取得する binary-search-nearest-value 二分探索法はソート済みの配列において、検索する間隔を半分に分割しながらデータを探し出すアルゴリズムです。先頭か・・・

続きを読む

プログラムで小数点以下の計算をおこなうと誤差が生じることがあります。コンピュータの場合、二進法で計算の処理をおこなっていますが、小数点以下の数を2進数で表現できない場合があり、人間目線だと意外なところで誤差が発生すること・・・

続きを読む

点（x, y）と線分（点A（x1, y1）と点B（x2, y2）を結ぶ線分）の最短距離を求めます。いろいろなやり方があるかもしれませんが、鳩は以下のように考えました。 平行移動と回転移動で最短距離を求める 全体を平行移動・・・

続きを読む

タイトルそのままです。「連続する部分列の総和が0になる場合」が何通りあるのかを数えます。これもループを何重にも回すのではなく1回で終わらせます。累積和をつかえば配列が長くても一発で終わります。 これはAtCoder 20・・・

続きを読む

連続する部分列の総和を最大にする方法を考えます。 間違ってはいないが時間がかかる まずは何の工夫もない方法から。二重ループですべての部分列の総和を計算してそのなかから最大値を求めようとしています。与えられた配列が短ければ・・・

続きを読む

Google スプレッドシートに書かれているurlからタイトルとmeta descriptionを取得するの続きです。他の言語、PythonとPHPでも同じことをやってみます。 Pythonの場合 Pythonでスプレッ・・・

続きを読む