Tea Break 002 お茶会

お茶会もとい有志のKakecoderに参加したのでABCみたいに記事書くよ
（CafeCoderに名前変わるらしいね）
難易度的にはAtCoderの灰〜茶色辺り対象らしく、実際の体感もそれくらい向けかなと思った
ぼくが茶色くらいのときにやりたかった〜
クオリティ高いと思ったのでぜひ頑張って欲しいね
公式解説
本番の提出コード残ってなくてサンプルしか合わせてないので間違ってたらごめんね

Green - Semiprime-like

素数かどうかを判定することで答えられるが
制約が小さいので全探索で

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for(int i=2;i<=100;i++){
        for(int j=2;j<=100;j++){
            if(i * j == N){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Ceylon - Trick of Treat

4つの合計が4の倍数かどうかで判定できます

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int sum = 0;
    REP(i,4){
        int a;
        cin >> a;
        sum += a;
    }
    if(sum % 4 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Earlgray - 最小全域木？なにそれおいしいの？

これすき
最小全域木で殴るのはそれはそうで
よく見るとi + jは単調増加していくのでiとjは出来るだけ小さいほうがいい
頂点1から全部の辺につなげることを考えるとiは1になって一番小さくなる
まず頂点1と2を繋いでその後頂点3を繋げることを考えると
頂点2と3を繋ぐ場合2 + 3 > 頂点1と3を繋ぐ場合 1 + 3で頂点1に繋ぐのが最適とわかる
あとは全部同じように繋げていくと、もしくはで出来る
解説PDFが親切で色々勉強になるのでぜひ読もう

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    ll sum = 0;
    for(int i=2;i<=N;i++){
        sum += 1 + i;
    }
    cout << sum << endl;
}

Keemun - Multiple Multiple

Dはbit全探索のD
茶色辺りならそろそろ抑えておきたい問題
細かいこと解説するよりけんちょんさんの記事見るほうがためになるので解けなかった人はみんな見ようね
qiita.com

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    ll ans = 3*LINF;
    ll mi = ans;
    for(int i=1;i<(1<<N);i++){
        ll tmp = 1;
        REP(j,N){
            if((i>>j) & 1) tmp *= A[j];
        }
        if(abs(M - ans) > abs(M - tmp)){
            ans = tmp;
            chmin(mi, abs(M - tmp));
        }
        else if(mi == abs(M - tmp)) chmin(ans, tmp);
    }
    cout << ans << endl;
}

おわりに

まだまだ発展途上みたいだけど問題の質も良かったのでぜひ続けて欲しいし頑張って欲しいね
AtCoder灰〜茶色辺りの人は勉強になるので是非参加してほしいね