二分探索 （木じゃなくて）
線形探索と二分探索
探索問題において、"普通"の探し方が先頭から末尾まで一つずつ見ていくのが、線形探索
ソート済みの未探索の要素の真ん中を調べ、その値で探索済み未探索を分ける。これを繰り返すのが二分探索
atcoderでTLE
pythonで競技プログラミングをするとタイムアウト(TLE)することがよくあるが、abc146のC問題を何も考えずに解いていたら、TLEになってしまった。
コードの一部
手持ちのお金で変える最大を求める問題で、 言い換えると条件式に当てはまる最大を求める問題だった。
a,b,x = map(int,input().split()) def can_buy(arg): p = a * arg + b * len(str(arg)) return p <= x # true or false done = 0 uncheck = 10 ** 9 + 1 while uncheck - done > 1: p = (uncheck+done) // 2 if can_buy(p): done = p else: uncheck = p print(done)
要点
二分探索をする際は、以下の要素で書けばいい
- 条件判定する関数を作成
- 絞り込むための0から増加する変数と最大から減少する変数を定義
- 探索する範囲を割る2して、徐々に狭めるために、判定するたびに上記変数を更新
- whileで3を繰り返す
主成分分析PCA
主成分分析と固有値問題の関係
主成分分析PCAは固有値問題を用いる。どんな関係があるのだろうと疑問に思った。
主成分分析PCAとは
データ分析において面倒な変数が多い状況を解消するために、情報量を減らさずに次元圧縮(変数の削除)をする手法。
固有値問題とは
線形代数でよくある、行列の固有値と固有値ベクトルを求めよ系の問題のこと。
関係は？
共分散
次元圧縮において、情報量を減らしたくない。よって、次元圧縮した結果、変数は減っていてなおかつ共分散を取って一番バラけている状態が理想である。
(引用)
分散を計算するのに、行列計算が便利だから行列を使う。
固有値問題
データを共分散行列で表し、それに対し分散が最大となる方向を求める式が途中で固有方程式になるためである。 (ラグランジュの未定乗数法は制約条件がある固有値問題の解法の一つ。)
固有方程式が現れて、それを解く固有値問題に落とし込むことができるのは、固有値ベクトルの性質として固有値ベクトル同士直交することと、単位ベクトルがノルムである条件からだと思うが、よくわからない。
この問題においては、固有値はすなわち分散である。 結果として、固有値問題を解くだけ分散の最大が得られる。
主成分分析PCAの主なアルゴリズム
- 分散の最大値が大きいベクトルを見つけ、第一成分とラベル付けする
- 第一成分と直交する方角のうち、最大の分散があるベクトルを見つけるこれを第二成分とする
この方向を見つけるという行為が固有値ベクトルを求めるということと同義である。
参考文献
主成分分析PCA
主成分分析と固有値問題の関係
主成分分析PCAは固有値問題を用いる。どんな関係があるのだろうと疑問に思った。
主成分分析PCAとは
データ分析において面倒な変数が多い状況を解消するために、情報量を減らさずに次元圧縮(変数の削除)をする手法。
固有値問題とは
線形代数でよくある、行列の固有値と固有値ベクトルを求めよ系の問題のこと。
関係は？
共分散
次元圧縮において、情報量を減らしたくない。よって、次元圧縮した結果、変数は減っていてなおかつ共分散を取って一番バラけている状態が理想である。
(引用)
分散を計算するのに、行列計算が便利だから行列を使う。
固有値問題
結論から言うと、共分散行列に対し固有値問題を解くと固有値と固有値ベクトルが得られ、その固有値はすなわち分散である。 よって、固有値問題を解くだけ分散の最大が得られる。
ラグランジュの未定乗数法は制約条件がある固有値問題の解法の一つ。
主成分分析PCAの主なアルゴリズム
- 分散の最大値が大きいベクトルを見つけ、第一成分とラベル付けする
- 第一成分と直交する方角のうち、最大の分散があるベクトルを見つけるこれを第二成分とする
参考文献
paizaでAランクを取った。
経緯
就活のために先輩がやっていた競技プログラミングサークルへ参加し、atcoderでいろはを学んだ。
しかし、atcoderが思うように伸びなかったので気分転換にpaizaをやっていたら、以外にも苦労なくAランクまで行った。
道筋
qiitaでatcoder虎の巻みたいなものをまとめてくれている有志の記事があるのでそれを眺める。
自分の言語(自分の場合python)で絞り込んだ。
atcoderの優しい問題を解き、入出力の方法の王道を知る。
難しいアルゴリズムの勉強は少しずつでいいので精神がやまない程度に。
手を付けて解けなかった問題は、atcoderで他の人の解答を見まくって、真似る。
(変態みたいな解き方を真似しないように、複数人の解き方を見る)
結論
Atcoder をqiitaを見ながら解く。
paizaはランクが上がるのが直ぐだからやる気が出て良い。
併用するべし。
slackの@hereってなに
だれに通知するか選択できる
@here
アクティブなメンバー全員に通知を送る。
非アクティブのメンバーには送らない。
@channel
すべてのメンバーに通知を送る。
メンバーがアクティブかどうかは関係ない。
なので @here より強力。
pythonで競技プログラミングする際
再帰で書いたが、、、
再帰でpaizaのコードを解いた。
しかし、テストケースでコケる。自前ではその入力を知れないから理由がわからない。
原因 再帰の限界が初期設定10000
④再帰限界 Pythonでは再帰限界が1000回まで決められているので、再帰を使う際はこの限界を上げてあげる必要があります。 具体的には以下のようなものを冒頭に書きます。
import sys sys.setrecursionlimit(4100000)
結論
勉強になります。
引用元
[https://juppy.hatenablog.com/entry/2019/06/14/Python競技プログラミング高速化tips%28PythonでAtcoderをやる際に個:title]
