AtCoder Beginner Contest 120(ABC120)3完

自分の考察まとめとして、コンテスト中に解けた問題までブログを書くことにしました！氷河期以外はなるべく続けて行こうと思います！

A - Favorite Sound

問題文

高橋くんは、自動販売機でジュースを買ったときの音が好きです。

その音は $1$ 回 $A$ 円で聞くことができます。

高橋くんは $B$ 円持っていますが、お気に入りの音を $C$ 回聞くと満足するため、 $B$ 円で最大 $C$ 回まで聞けるだけ聞きます。

高橋くんはお気に入りの音を何回聞くことになるでしょうか。

制約

入力は全て整数である。
$1 \leq A, B, C \leq 100$

考察

この問題は、「所持金を全て使って音を聞ける回数」と「聞くと満足する音の回数」の小さい方の値が答えとなります。

所持金を全て使って音を聞ける回数は、int型同士の割り算の特徴である「切り捨て」
ex) (int)5/2==2
を使うことによって、「所持金を全て使って音を聞ける回数」は「b/a」と書くことができます。

実装例

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 ll a,b,c;
 cin>>a>>b>>c;
 cout<<min(c,b/a)<<endl;
}

B - K-th Common Divisor

問題文

正整数 $A, B$ が与えられます。

$A$ も $B$ も割り切る正整数のうち、 $K$ 番目に大きいものを求めてください。

なお、与えられる入力では、 $A$ も $B$ も割り切る正整数のうち $K$ 番目に大きいものが存在することが保証されます。

制約

入力は全て整数である。
$1 \leq A, B \leq 100$
$A$ も $B$ も割り切る正整数のうち、 $K$ 番目に大きいものが存在する。
$K \geq 1$

考察

まず制約がA,B<=100なので、約数全列挙などせずに101から1まで順にAをhogeで割った余りが0&&Bを割った余りが0の時をカウントしながら全探索すればよさそう。
ここで注意したいのが、AもBも割り切れる正整数のうちK番目に大きいものを出力しなければならないところ。これに引っかかって実装しなおした人多いのでは？(私もです)勝手に頭の中で小さい順に書き換えてしまう癖は良くないですね!ちゃんと問題文は読みましょう(自戒)

実装例

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
　ll a,b,k,cnt=0,ans;//cntの初期化(0の代入)は忘れずに！！！
　cin>>a>>b>>k;
　for(int i=101;i>0;i--){
　　if(a%i==0&&b%i==0){
　　　cnt++;//初期化しないと++動作が不安定になります
　　}
　　if(cnt==k){
　　　ans=i;
　　　break;
　　}
　}
　cout<<ans<<endl;
}

C - Unification

問題文

机の上に $N$ 個のキューブが縦に積まれています。長さ $N$ の文字列 $S$ が与えられます。

下から $i$ 番目のキューブの色は、 $S$ の $i$ 文字目が 0 のとき赤色、1 のとき青色です。

あなたは、赤色のキューブと青色のキューブが隣り合っているような部分を選んで、それら $2$ 個のキューブを取り除く操作を何度でも行えます。

このとき、取り除いたキューブの上にあったキューブは真下の物体の上に落下します。

最大で何個のキューブを取り除けるでしょうか。

制約

$1 \leq N \leq 10^{5}$
$| S | = N$
$S$ の各文字は 0 または 1 である。

考察

違う色が重なったときに、2個のキューブを消すらしい。

ということは、先頭から順に配列を見ていって、赤(青)が来たときに、それまでに消えていない別の色　青(赤)が1つでもあれば「取り除けるキューブ+=2」と「青(赤)の残り個数のカウント-=1」を、全くない場合(0個のとき)　現在参照している色　「赤(青)の残り個数のカウント+=1」していけばよさそう

実装例

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
　string s;
　cin>>s;
　ll ans=0,cnt_0=0,cnt_1=0;
　for(int i=0;i<s.length();i++){
　　if(s[i]=='0'){
　　　if(cnt_1==0)cnt_0++;
　　　else{
　　　　cnt_1--;
　　　　ans+=2;
　　　}
　　}
　　else{
　　　if(cnt_0==0)cnt_1++;
　　　else{
　　　　cnt_0--;
　　　　ans+=2;
　　　}
　　}
　}
　cout<<ans<<endl;
}

感想

今回は3完14:07で787位でした。

目標にしていた全完はまたも叶わず、、、　いつ全完できるんだか、、、

次回のコンテストはAGCなので早解きでワンチャンレートが上がればいいなーという体で参加したいと思います。(ただ参加者のレベルが上がっているので1完じゃあ厳しいかな...)

水色に早くなりたい！！！！！！！！(あと+265)

記事を見てくださりありがとうございました

ご意見や間違い等ございましたら、コメントよろしくお願いします！！

||||>||#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18
bool comp(const pair<int,int>& a,const pair<int,int>& b){
    return a.second<b.second;
}
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    cout<<min(c,b/a)<<endl;