BrownCoder

無能ですがAtCoderしてます。情報処理試験や機械学習、その他ベンダー資格時々数学など参考になった本の紹介や雑記を書いてます。

AtCoderBeginnerContest120考察

この記事をシェアする

ABC120に出ました。D問題でグラフ関係知識なさすぎて投げました。Cは一回シミュした後にあ、数えればいいだけか・・・と気づいて悲しい気持ちでコーディングしました。








A問題

A - Favorite Sound

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

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

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

制約
入力は全て整数である。
1≤A,B,C≤100

解説

C回ループを回して、b - a が正の数の時をカウントしてあげるだけ。最初実装ミスって焦った。よく考えたらmin取って商とる。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1<<29;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)


int main(){
    int a, b, c; cin >> a >> b >> c;
    int cnt = 0;
    rep(i, c){
        if( b - a >= 0){
            b -= a;
            cnt++;
        }
    }
    cout << cnt << endl;
}

B問題

B - K-th Common Divisor

問題文
正整数 A,Bが与えられます。
AもBも割り切る正整数のうち、K番目に大きいものを求めてください。
なお、与えられる入力では、AもBも割り切る正整数のうち K番目に大きいものが存在することが保証されます。

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

解説

愚直に割り切れるか剰余を使ってループを回していく。気をつけるところは大きい方からk番目なので後ろから検査していかなければいけない。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1<<29;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)


int main(){
    int a, b, k; cin >> a >> b >> k;
    int i = min(a, b), cnt = 0;
    while(1){
        if(a % i == 0 && b % i == 0){
            cnt++;
        }
        if(cnt == k) break;
        i--;
    }
    cout << i << endl;
}

C問題

C - Unification

机の上に N個のキューブが縦に積まれています。長さ Nの文字列 Sが与えられます。
下からi番目のキューブの色は、Sのi
文字目が 0 のとき赤色、1 のとき青色です。
あなたは、赤色のキューブと青色のキューブが隣り合っているような部分を選んで、それら 2個のキューブを取り除く操作を何度でも行えます。
このとき、取り除いたキューブの上にあったキューブは真下の物体の上に落下します。
最大で何個のキューブを取り除けるでしょうか。

制約
1≤N≤105
\|S\|=NSの各文字は 0 または 1 である。

解説

最初愚直に全探索シミュレートをしてしまいTLEでWA。すぐに0と1の最小個数を取ってあげてそれを2倍してあげればいいことに気づき、AC

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1<<29;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)


int main(){
    string s; cin >> s;
    int i = 0;
    int onec = 0, zeroc = 0;
    rep(i, s.size()){
        if(s[i] == '1'){
            onec++;
        } else {
            zeroc++;
        }
    }
    cout << min(onec, zeroc) * 2 << endl;
}

D問題

無向グラフを使ったDFSかBFSやればできそうだな〜でも全然わからねぇ〜と思いつつ退散。きっといつか解く。
と思ってたら残念ながらUnion-Findらしい。なにそれ。あとは自分で解く時用のメモ


f:id:noikari:20190303230857p:plain