ヒストグラム内の最大長方形を求める

ライブラリ

Quiz

AC

解法

（１）

  • 列ごとに下にカウントしていけばO(WH)で求まる

f:id:peroon:20191127195732p:plain

（２）

f:id:peroon:20210124005734p:plain

全体の計算量

  • (1)がO(WH), (2)がO(WH)なので、全体としてもO(WH)

code

// ヒストグラムを与えると、最大の長方形の面積を返します
// 計算量 O(N)
ll largest_rectangle_in_a_histogram(VI& V){
  ll ma = 0;
  stack<PII> st;
  ll N = SZ(V);
  rep(i, N){
    ll h = V[i];
    // スタックが空ならそのまま積む
    if(st.size()==0){
      st.push({h,i});
    }
    // 高さが同じ
    else if(st.top().first==h){
      continue;
    }
    // より高いものが来た
    else if(st.top().first<h){
      st.push({h,i});
    }
    // より低いものが来た
    else{
      ll last_pos;
      // スタックの方が高いものは全部取り除いて精算する（面積を求める）
      while(st.size()>0 && st.top().first>h){
        auto pa = st.top(); st.pop();
        ll area = pa.first * (i-pa.second);
        chmax(ma, area);
        last_pos = pa.second;
      }
      // 今回の値をスタックに積む（位置は、最後にスタックから取り除いたものの位置）
      st.push({h, last_pos});
    }
  }
  // stackに残っている分
  while(st.size()>0){
    auto pa = st.top(); st.pop();
    ll area = pa.first * (N-pa.second);
    chmax(ma, area);
  }
  return ma;
}

補足

類題

verified

gdbでsegmentation faultをした場所を特定する

f:id:peroon:20191127020740p:plain

環境

動機

  • segmentation faultしたとき、位置が分からなかった
  • gdbを使ってみよう

やったこと

  • sudo apt get gdb
  • gdb ./a.out
  • テストケース（テキストファイル）を入力したいので以下のようにした
run params ... < testcase1.txt

Program received signal SIGSEGV, Segmentation fault.
0x000000000800a67b in main () at answer_aizu_2709_20191127.cpp:174
174             if(dp[next]==inf){
  • めでたしめでたし

at()で防御力高く

  • vectorを使っているならA[123]とせず、A.at(123)とすることでsegmentation faultが発生したら教えてくれる

追記

  • 特定できない時もあった
  • 大抵配列アクセスなので、怪しい箇所をA[123]ではなくA.at(123)のように書き換えていったほうがすぐ見つかりそう

C++ 文字列 一括置換 

// https://www.sejuku.net/blog/54493
// を少し書き換えたもの
// 参照なので書き換えます
string replace_all(string &s, string from, string to) {
    ll pos = s.find(from);
    while(1){
      pos = s.find(from, pos);
      if(pos==string::npos) break;
      s.replace(pos, from.length(), to);
      pos += to.length();
    }
    return s;
}

使い方

s = replace_all(s, "ABC", "B");

verified

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4008789#1

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

Invest Master (AOJ 2607) ”個数制限なし”ナップサック

ライブラリ ナップサック

解法

  • 毎日売ると考えてよいので、今日と明日だけを見て利益を最大化すればいい
  • 画像のように荷物に置き換えて、個数制限なしナップサック問題を毎日解けばいい
  • コードは蟻本p58にある
  • 計算量 O(NC)
    • N : num
    • C : capacity

f:id:peroon:20191126153255p:plain

code

  • 自分なりに再利用可能にしてみた (※個数制限なし)
  • 何度もDPするので、毎回DPテーブルを初期化することを忘れずに
// i : 個数
// j : capacity
const int N_MAX = 100; // 個数
const int CAPACITY_MAX = 10000; // キャパシティ
ll dp[N_MAX+1][CAPACITY_MAX+1];
void reset(){
  rep(i, N_MAX+1){
    rep(j, CAPACITY_MAX+1){
      dp[i][j] = 0;
    }
  }
}

// !!!個数制限なし!!!ナップサック
// V : value
// W : weight
// C : capacity
ll knapsack(VI& V, VI& W, ll C){
  reset();
  ll n = V.size();
  rep(i, n){
    rep(j, C+1){
      if(j<W[i]){
        dp[i+1][j] = dp[i][j];
      }else{
        dp[i+1][j] = max(dp[i][j], dp[i+1][j-W[i]] + V[i]);
      }
    }
  }
  return dp[n][C];
}

verified

2点を通る円の中心を(2つ)求める AOJ 1132 Circle and Points 円で囲める点の最大値

ベクトル 幾何 複素数

f:id:peroon:20191126035334p:plain

設定

  • ２次元平面上の２点を与えられた時、そこを通る円が存在するなら２つある
  • その円の中心２つを求めたい
  • 半径rは与えられるとする

解法

  • ２次元ベクトルで考える（プログラム的には複素数complexを利用する）
  • ２点の中央ｃから垂直方向に単位ベクトルｎを考える（画像参照）
  • それを長さｘ分だけ伸ばしたところが円の中心で、ｘはピタゴラスの定理から求まる
  • 垂直ベクトルについて、(a, b)に垂直なベクトルは(-b, a)である（内積が０）

code

typedef complex<double> C;
#define X real()
#define Y imag()

// 2点を与えると, それを通る半径rの円の中央2つを返す
vector<C> f(C a, C b, double r){
  vector<C> ret;
  
  // a, bの距離が大きすぎると作れない
  {
    double d = abs(a-b);
    if(d>2*r) return ret;
  }

  C c = (a+b)/2.0;

  double temp = r*r - norm(a-c);
  double x = sqrt(temp);

  //中央に向かうベクトル
  C d = c-a;
  C e = {-d.Y, d.X}; // 垂直ベクトル
  C f = e / abs(e); // 単位ベクトル

  ret.push_back(c+x*f);
  ret.push_back(c-x*f);

  return ret;
}

verified✅