Asa's Blog

ABC207

Tags: AtCoder  ABC  Competitive-Programming 

Published on 2021.06.26. Last Modified on 2021.06.22.

今回は 3 完です。概要は以下のツイートの通りです。(双括型)

問題概要

A

3 枚のカード($A,B,C$)のうち 2 枚をとったら、その和の最大値は?

B

最初、水色ボールが $A$ 個入っている。水色 $B$ 個と赤色 $C$ 個を追加する操作を好きなだけ繰り返して水色の個数が赤色の個数の $D$ 倍以下にするとき、手数の最小値はいくら?無理なら -1

C

$N$ 個の区間。$1 \le i \lt j \le N$ な 区間 $i$ と 区間 $j$ が共通区間を持つのはいくつ?
ただし、

  • $t_i = 1$ なら、 区間 $i$ は $[l_i,r_i]$ (閉区間)
  • $t_i = 2$ なら、 区間 $i$ は $[l_i,r_i)$ (半開区間)
  • $t_i = 3$ なら、 区間 $i$ は $(l_i,r_i]$ (半開区間)
  • $t_i = 4$ なら、 区間 $i$ は $(l_i,r_i)$ (開区間)

提出

ここから 全体の提出結果がわかります。

A

提出 #23756680 - AtCoder Beginner Contest 207

最大値を求めるので、総和から最小値を引くだけ。
式にすると、 $a+b+c-\max (a,b,c)$

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  cout << (a+b+c - min(a,min(b,c))) << endl;
  return 0;
}

JS とかだと min(a,b,c) でできるだけど、C++だと min(a,min(b,c))) でやるのがちょっと面倒。
min({a,b,c}) でできるみたい。知れてよかった。

提出時刻は 21:01:25。だけど机の周りになぜか虫が群がっていて後処理で 50 秒くらい食ったので、実質 30 秒()。

B

提出 #23762351 - AtCoder Beginner Contest 207

N を操作回数として、不等式を立ててみると、$A+BN \le DCN \rightarrow A \le N(DC - B) \rightarrow \frac{A}{DC-B} \le N$ になるので、最小値は $\mathrm{ceil}(\frac{A}{DC-B})$ になります。
$DC-B \lt 0$ となると、$N \lt 0$ になってしまうので、この場合 -1 を出力します。
ちなみに、$DC-B = 0$ となる場合、不等式に代入してみると $A \ne 0$ となるので、$DC-B = 0$ の場合は考えなくて良いと思います。(提出後の考察)

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

int main(){
  double a,b,c,d;
  cin >> a >> b >> c >> d;
  int x = ceil(a/(d*c-b));
  if(x<0){ cout << -1 << endl; }
  else{ cout << x << endl; }
  return 0;
}

提出時刻は 21:06:15。脳内で考えた後、ノートに書き直したので少し時間がかかってしまった…。

C

提出 #23776113 - AtCoder Beginner Contest 207

$l_i, r_i$ は整数なので、端点が含まれないなら $\pm 0.1$ してあげて全部閉区間にしちゃいました()。きちんと double 型で入力する必要がありますね。
そして、$l_i \le r_j$ かつ $l_j \le r_i$ ならば大丈夫です。
(解説では $\max(l_i, l_j) \le \min(r_i, r_j)$ とやっていました。なるほど。)

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define loop(i,n) for(ull i=0;i<n;i++)

int main(){
  int n;
  cin >> n;
  vector<vector<double>> a(n,vector<double>(2,0));
  loop(i,n){
    double t,l,r;
    cin >> t >> l >> r;
    if(t == 2){ r-=0.1; }
    if(t == 3){ l+=0.1; }
    if(t == 4){ l+=0.1; r-=0.1; }
    a[i][0] = l;
    a[i][1] = r;
  }
  ull c=0;
  for(ull i=0;i<n-1;i++) for(ull j=i+1;j<n;j++){
    if(a[i][0] <= a[j][1] && a[j][0] <= a[i][1]){
      c++;
    }
  }
  cout << c << endl;
  return 0;
}

提出時刻は 21:24:57。最初 int 型で入力しててあれ?ってなってました。

結果と感想

はい、水パフォでした。やった。今回は比較的難しかった…?
次も同じくらいのパフォーマンスで緑勢になれるかも…!?

入緑が見えてきた...!(フラグ)

keyboard_arrow_up