AtCoder Beginner Contest 144 - zeronosu77108’s blog

ABCの3完でした．
DとEは時間内に見ていたのですが，Dは場合分けがダメでした（数式でゴニョゴニョして atan しようとしていた）．

E は，ソートして反対向きにマッチングさせるっていう所までは考えたんだけど，その後の処理が分かりませんでした．
二分探索すれば良かったらしい．

f:id:zeronosu77108:20191103163004p:plain

A - 9x9

九九を覚えたって可愛いな〜と思いながら書いてました．
まぁ，そんな感じ．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int a,b;
  cin >> a >> b;
  cout << ((a<=9&&b<=9)? a*b : -1) << endl;
}

B - 81

問題文

1 から 9 までで商が9以下になって，余りが0なら満たします．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int n;
  cin >> n;
  bool ans = false;

  for (int i=1; i<=9; i++) {
    if (n/i<=9 && n%i==0) ans = true;
  }

  cout << (ans? "Yes" : "No") << endl;
}

C - Walk on Multiplication Table

問題文

愚直に探索するだけです．
$i \times j$ が $N$ になる組み合わせを全部探して，その和の最小値を求めます．
ただ，計算量を減らす必要があって， $\sqrt{N}$ まで探索するようにします．

10 の約数は， 1,2,5,10 だけど， $\sqrt{10}=3.1\cdots$ まで探索したら， $\frac{10}{1} = 10$ ， $\frac{10}{2} = 5$ となって， $\sqrt{10}$ より大きい値は探索しなく良いです．

これで探索範囲が $10^ {12}$ から $10^ 6$ になるので， $\mathcal{O}(N)$ でも間に合います．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  long n;
  cin >> n;
  long ans = LONG_MAX;

  long stop = sqrt(n);
  for (int i=1; i<=stop; i++) {
    if (n%i==0) ans = min(ans, i+n/i);
  }
  
  cout << ans-2 << endl;
}

D - Water Bottle

問題文

解説をなんとなく聞いて，自分で式おこしして解いてみました． $A \times B$ の面積で考えることができるので，最初に次元を落としておきます．

そして， $A \times B$ の面積の半分を超えない場合は，単純な三角形で考えることができます．
面積の半分を超える場合は，四角形の上に三角形が乗っているような形になるので，三角形部分を atan すれば良いです．

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  long double a,b,x;
  long double ans;
  cin >> a >> b >> x;

  x /= a; // 奥行きを消す（平面で考える）

  // 半分より多いか少ないかで場合分けをする
  if (x <= a*b/2) { 
    ans = atan2(b, 2*x/b);
  } else {
    ans = atan2(2*(b-x/a), a);
    // 反対側の三角形から高さを求める．
    /*
      h = 2*(a*b -x) / a
        = 2*(b - x/a)
    */
  }

  cout << setprecision(14) << ans * 180.0 / M_PI << endl;
}

E - Gluttony

問題文

基本的に，片方を昇順にしてもう片方を降順にして同じインデックスのものを組み合わせると最小値になります．
このときに， $K$ 回の操作を上手くしたときの最小値を求めるのが分からなかった．

こういう問題は二分探索するみたいです．
コンテスト後に解いたんですけど，二分探索書き方忘れていて，苦労しました．

後は，long long じゃないと通らなかった…

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;


int main() {
  long long n,k;
  cin >> n >> k;
  vector<long long> a(n);
  vector<long long> f(n);

  for (int i=0; i<n; i++) cin>>a[i];
  for (int i=0; i<n; i++) cin>>f[i];

  sort(a.begin(),a.end());
  sort(f.rbegin(),f.rend());

  long long l = -1;
  long long r = 1e12;
  while(l+1 < r) {
    long long g = (l+r)/2;
    bool flag = true;

    long long count = 0;
    for (long long i=0; i<n; i++) {
      count += max(0LL,(a[i] - g/f[i]));
      if (count > k) {
        flag=false;
        break;
      }
    }
    (flag? r : l) = g;
  }

  cout << r << endl;
}