競プロ日記#25/09/16

AtCoder

AtCoder Beginner Contest 085

C - Otoshidama

• 万札、五千円札、千円札のうちどれか二つを固定すれば必然的に残りの1つの枚数が確定するというパターン。
• 変数名がダメすぎるのだが競プロなのでご愛敬（余談ですが最近「プログラマー脳」という本を読んでおり、とても面白いです。「その本を読んでてこの変数名になるのはやばい」というツッコミ待ちです。）

int main() {
    ll Mansatsu = 10000;
    ll Gosensatsu = 5000;
    ll Senensatsu = 1000;
    ll N,Y;
    cin >> N >> Y;
    vector<ll> A(3);
    A[0] = -1;
    A[1] = -1;
    A[2] = -1;
    for (ll i = 0;i <= 2000;i++){
        for (ll j = 0;j <= 2000;j++){
            ll rest = Y - Mansatsu*i - Gosensatsu*j;
            if (rest < 0) continue;
            if (rest % Senensatsu != 0) continue;
            ll k = rest / Senensatsu;
            if (i + j + k != N) continue;
            A[0] = i;
            A[1] = j;
            A[2] = k;
            break;
        }
        if (A[0] != -1) break;
    }
    cout << A[0] << " " << A[1] << " " << A[2] << endl;
}

典型90問

016 - Minimum Coins（★3）

• A,Bを決めればCの値が必然的に決まるから探索範囲を絞れるという問題
• 流石に二回目で復習だったので解けた。
• より厳密にはk = rest / Cのkが10000を超えないかを確認してもよかった（とはいえこれは課せられた制約ではなくて前提条件なので必要ないと言えばないと思う）

int main() {
    long long N,A,B,C;
    cin >> N;
    cin >> A >> B >> C;

    long long ans = LLONG_MAX;
    for (long long i = 0;i <= 10000;i++){
        for (long long j = 0;j <= 10000;j++){
            long long rest = N - A*i - B*j;
            if (rest < 0) continue;
            if (rest % C != 0) continue;
            long long k = rest / C;
            ans = min(ans, i + j + k);
        }
    }

    cout << ans << endl;
}

033 - Not Too Bright（★2）

• 復習で解くのは二回目だった

    if (isEvenH && isEvenW){
        ans = (H/2)*(W/2);
    } else if (isEvenH && !isEvenW){
        ans = (H/2) * ((W/2) + 1);
    } else if (!isEvenH && isEvenW){
        ans = ((H/2) + 1) * (W/2);
    } else {
        ans = ((H/2) + 1) * ((W/2) + 1);
            
    }
    cout << ans << endl;

• の様に縦横の偶奇で場合分けするところまでは思いついたがコーナーケースでこけまくった
• 過去問ではWAの時のテストケースのファイル名からヒントを貰えたが本番は確かファイル名わからないよね...？
• H == 1 || W == 1のケースの考慮をして終了

int main() {
    long long H,W;
    cin >> H >> W;
    bool isEvenH = (H % 2 == 0);
    bool isEvenW = (W % 2 == 0);
    long long ans = 0;
    if (H == 1 || W == 1){
        ans = max(H,W);
        cout << ans << endl;
        return 0;
    }
    if (isEvenH && isEvenW){
        ans = (H/2)*(W/2);
    } else if (isEvenH && !isEvenW){
        ans = (H/2) * ((W/2) + 1);
    } else if (!isEvenH && isEvenW){
        ans = ((H/2) + 1) * (W/2);
    } else {
        ans = ((H/2) + 1) * ((W/2) + 1);
            
    }
    cout << ans << endl;
}

• ただ、厳密には偶奇で分けるというよりは縦横についてともに奇数列に置くのが最大という考え方。それなら細かい場合分けも不要