# 芝浦ばちゃ#8

# A - Garden

# 概要

  • A×BA \times Bの畑に, 幅1の道を2本引いた時の畑の面積を求めよ

# 解法

  • 畑を平行移動すれば, (A1)×(B1)(A-1) \times (B-1)となることがわかる

# 提出コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int a,b; cin>>a>>b;
  cout<<(max(0, (a-1)*(b-1)))<<endl;
  return 0;
}

# B - Snake Toy

# 概要

  • 長さがlil_iである棒がNN本ある
  • この中からKK本選んだ時の長さの総和の最大値を求めよ

# 解法

  • 大きい順に選べば良いのは自明
  • したがって, ソートして大きい方からKK本選んだものの総和が答え

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

signed main() {
  int n,k; cin>>n>>k;
  vector<int> l(n);
  for(int i=0;i<n;++i) cin>>l[i];

  sort(l.begin(), l.end(), greater<int>());

  int ans = 0;
  for(int i=0;i<k;++i) {
    ans += l[i];
  }
  cout<<ans<<endl;
  return 0;
}

# C - Big Array

  • 問題文を読みましょうね(自戒の念)

# 概要

  • ai数a_ibib_i個入れる」というクエリがNN回渡される
  • この挿入操作後の数列において, KK番目に小さい数を求めよ

# 解法

  • NN個のクエリを全部実行した時に, 何の数字がいくつあるかをメモしておけば良い
    • そうすれば, 前からKK個数えるだけで解が出るので

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

signed main() {
  int n,k;cin>>n>>k;
  
  map<int,int> mp;
  for(int i=0;i<n;++i){
    int a,b; cin>>a>>b;
    mp[a] += b;
  }

  int cnt=0,ans=-1;
  for(auto &&mi: mp){
    cnt += mi.second;
    if(cnt >= k) {
      ans = mi.first;
      break;
    }
  }
  cout<<ans<<endl;

  return 0;
}

# D - Katana Thrower

# 概要

  • NN本のKATANAKATANAがあり, 次の攻撃ができる
    • aia_iのダメージを与える.その後, 繰り返し使える.
    • bib_iのダメージを与える.その後, 二度と使用できない.
  • この時, HHのダメージを与える際の最小の攻撃回数を求めよ

# 解法

  • 少し考えると, 繰り返し使用するKATANAKATANAは1本だけストックしておけば良く, 他のKATANAKATANAは投げてしまって良いことがわかる。

    • 経験値効率の良いクエストに潜り続けて, 効率の悪いダンジョンは1回だけ石回収しに行くみたいな感じ(違います)
  • したがって, 解法は次のとおり

    • 繰り返し使用するaia_iの最大値を取得する
    • bib_iを大きい順にソートする
    • aia_iの最大値よりも大きいものだけを投げる
    • 投げ終わったら, 残りはaia_iの最大値を与え続ける

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

signed main() {
  int n,h; cin>>n>>h;

  vector<int> b(n);
  int _max=0;
  for(int i=0;i<n;++i) {
    int p,q; cin>>p>>q;
    _max = max(_max,p);
    b[i] = q;
  }
 
  sort(b.begin(), b.end(), greater<int>());
  
  int ans=0, sm=0;
  for(int i=0;i<n;++i) {
    // 降るよりも効率の良いKATANAがあれば, 投げる
    if(b[i] > _max){
      sm += b[i];
      ++ans;
    }
    if(sm >= h) break;
  }
 
  // 投げた後に, ひたすら効率の良いKATANAを降り続ける
  if(sm < h) ans += (h-sm + _max-1)/_max;
  cout<<ans<<endl;
  return 0;
}
  • お疲れ様でした
Last Updated: 2019-4-2 12:55:01