2018-12-17から1日間の記事一覧

単調増加を見抜いてしゃくとり方をするとO(N^2) -> O(N)になった

提出 atcoder.jp 最後の2つの提出を見比べてみると どちらも2重のforなのでO(N2)に見える カット位置の単調増加を利用して、forの初期位置に前回のforの結果を利用 TLEにならなくなり、通った 学び 単調増加の性質がないか考える。あったら利用する 左から右…

【C++】pairのsecondを基準にソート(abc103_d)

提出 beta.atcoder.jp 抜粋 pairの比較関数を定義すればいい bool compare_by_b(pair<int, int> a, pair<int, int> b) { if(a.second != b.second){ return a.second < b.second; }else{ return a.first < b.first; } } int main(){ ... vector<pair<int, int> > pairs(M); // 入力 FOR(i, 0, M)</pair<int,></int,></int,>…