AtCoder Regular Contest 006 - C - 積み重ね
最初30の箱の上には合計30までしか載せれないかと思って、激ムズじゃんと思ったけど、カウントするのは一つ上だけっぽいのでそうでもなかった
https://gyazo.com/503b41b5dbaa7cd397340cc2cbae1a66
考えたこと
順番を考慮しないといけない(考慮しないと1つでいけちゃうし)
箱を1つづつ出していって、すでに置かれている段ボールの上に置けるなら置く、置けないならそれをベースにする
問題は下にできる段ボールの候補が複数ある時
取り出す段ボールの重さが30だとして、下における段ボールとして、30, 100, 200とあった時, どこに置いても良いか?
それはNGで、もし200の上に置いてしまったら、30, 100, 30となってしまう。
もし200を残していれば、101~200までが来たときに、200の上におけることができるけど、それができなくなってしまう。
というわけで、下にできる箱の中から一番軽いやつを選ぶ必要がありそう。
これは二分探索でいけそう
実装どうするか
二分探索でいけそうなのはわかったけど、実装どうする?
空のvectorを用意してあげて、シミュレートしてあげれば良さそう
積み重ねるのを、そのインデックスの値を更新するという作業で代替する感じで
例として、以下の入力例をvectorがどのようになるか考えてみる
https://gyazo.com/565c82b4cedf505a91b1b671fc418e0a
code: vector.cpp
// 空で生成
vector<int> ans;
// 1つ目は4, 空なので、1つ目は必ずpush
ans.push_back(4);
// 2つ目は3, lower_boundで二分探索する
// lower_boundは指定した値以上のイテレーターを返す(以上がない場合はans.size()のイテレーター返す)
auto itr = lower_bound(ans.begin(), ans.end(), 3);
auto index = itr - ans.begin(); // これは0(4 >= 3なので)
// 4を3に更新する(4の上に3を置く)
// 3つ目は1, 画像サンプルと違うけど、これも同様にlower_boundしたら、3の上におけるので置く
// 4つ目は2, lower_boundしたら、これより大きい値がないので、新しくpushする
ans.push_back(2);
// 5つ目は1, lower_boundしたら、1の上におけるので置く
// 最終的には以下のような重ね合わせになる
こんな感じ、細かいのは以下の提出コード参照
lower_boundは通常ソートされたvectorに対して実行しないといけないけど、この入れ方でやっていくと、常にvectorは昇順ソートが保たれているので実施不要
提出したコード
code: C.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
int n; cin >> n;
vector<int> w(n);
vector<int> ans;
rep(i, n) {
// 初回は必ず挿入
if(ans.size() == 0) ans.push_back(wi); else {
auto itr = lower_bound(ans.begin(), ans.end(), wi); auto index = itr - ans.begin();
if(index >= ans.size()) ans.push_back(wi); }
}
// 最終的なvectorの長さが解
cout << ans.size() << endl;
return 0;
}