AtCoder Beginner Contest 152（ABC152） - 接着剤の精進日記

ABCEの4完で冷えは回避
D解けなかったの反省だね
ところで水色streakがようやく2になりました（ええ…）

A - AC or WA

$N == M$ ならYes
なんだけどAC、そのまさかだよをやった人がいるっぽい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    if(N == M) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Comparing Strings

言われた通りの文字列を2つ作って比較する
ループで書いちゃったけど宣言のときの初期化で作れるよね確か
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    string S, T;
    REP(i, b) S += a + '0';
    REP(i, a) T += b + '0';
    if(S < T) cout << S << endl;
    else cout << T << endl;
}

C - Low Elements

頭　が　バ　グ　っ　た　笑
ぱっとセグ木が浮かんでいやいや、と思い直し左右からのminを思いつき
冷静に考えると右側からいらないので左からのminを配列でもって比較する
よくよく考えると配列にする必要すらなくて頭からminを更新していくだけでいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> P(N), mi(N+1,INF);
    mi[0] = INF;
    REP(i,N){
        cin >> P[i];
        mi[i+1] = mi[i];
        chmin(mi[i+1], P[i]);
    }
    int cnt = 0;
    
    REP(i,N){
        if(P[i] <= mi[i+1]) cnt++;
    }
    cout << cnt << endl;
}

D - Handstand 2

これ難しくない？全然わかんなかった
桁dpとか頭と後ろが決まれば間に入れれる数は頑張れば求めれそうとか色々考えたけどどれも実装が怪しいので一回パスしてEを見に行った
解説を見るとN以下の数字の先頭と後ろのペアは一意になるのでそのペアをかけ合わせてあげるといい（天才か？）
提出コード

ll cnt[10][10];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    
    for(int i=1;i<=N;i++){
        int pre = i % 10;
        int top = i;
        while(top >= 10) top /= 10;
        cnt[top][pre]++;
    }
    ll ans = 0;
    for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) ans += cnt[i][j] * cnt[j][i];
    cout << ans << endl;
}

E - Flatten

問題眺める、サンプルを見る、LCMじゃんとなる
Nが大きいので愚直にLCMをやると壊れちゃう（一瞬pythonの多倍長で殴ることを考える）
冷静になるとLCMは素因数で管理出来るので各素因数の最大をmapか何かで持っておく
それが求め終わったらLCMをmodを取りながら計算し、LCMと $A_i$ の逆元をかけ合わせていく
んだけど、modintにおまかせ（modintが楽すぎる）

//modint 部分省略

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    map<ll, ll> mp;
    vector<ll> a(N);
    REP(i,N){
        cin >> a[i];
        auto res = prime_factorize(a[i]);
        for(auto x : res){
            if(mp[x.first] >= x.second) continue;
            mp[x.first] += (x.second - mp[x.first]);
            //cout << mp[x.first] << endl;
        }
    }
    mint LCM = 1;
    for(auto x : mp){
        mint tmp = mod_pow(x.first, x.second, MOD);
        LCM *= tmp;
    }
    mint sum = 0;
    //cout << LCM << endl;
    REP(i,N){
        sum += LCM / mint(a[i]);
    }
    cout << sum << endl;
}