競プロ日記#25/09/03

典型90問

022 - Cubic Cake（★2）

• 3つの数字の最大公約数を求めてそれで各辺を割った値-1の和を取る
• この問題を解いていて分かったが、C問題レベルに関しては問題文とにらめっこするよりもSample1,2くらいの簡単な例からどういう法則があるかを見極める方が大事な気がした。
• 実際入力が（2,2,3）なら出力が4や入力が（2,2,4）なら出力が1の例から実際の直方体をイメージして気づいた

int main() {
    long long A,B,C;
    cin >> A >> B >> C;
    long long gcdOfAB = gcd(A,B);
    long long gcdOfABC = gcd(gcdOfAB,C);
    cout << A / gcdOfABC - 1 + B / gcdOfABC - 1 + C / gcdOfABC - 1 << endl;
}

024 - Select +／- One（★2）

• 差分を足した値とKの値の差の絶対値が偶数であればよい
  事には気づいていたのだが大前提となる操作回数 < Kの条件を完全に忘れていてペナった。悔しい
• ちなみに公式解説は差分の和とKの値の偶奇の一致を調べていたが本質的には同じことだと思うのでスルー

int main() {
    long long N,K;
    cin >> N >> K;
    vector<long long> A(N + 1);
    vector<long long> B(N + 1);
    A[0] = 0,B[0] = 0;
    for (long long i = 1; i <= N; i++) {
        cin >> A[i];
    }

    for (long long i = 1;i <= N;i++){
        cin >> B[i];
    }

    long long sumDiff = 0;
    for (long long i = 1; i <= N; i++) {
        sumDiff += abs(A[i] - B[i]);
    }

    if (K < sumDiff){
        cout << "No" << endl;
        return 0;
    }

    if (abs(K - sumDiff) % 2 != 0){
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

027 - Sign Up Requests

• ん～これ通るのか？という印象。正直TLEすると思って提出したらACしてしまった
• ユニークなIDを管理するためにSetを用意して、登録されたのが何日目かを記録するのにQueueを使って素直に実装しただけ
• ちなみに解説はMapで解いている

int main() {
    long long N;
    cin >> N;
    queue<long long> A;
    set<string> B;
    for (long long i = 1;i <= N;i++){
        string S;
        cin >> S;
        if (!B.contains(S)){
            B.insert(S);
            A.push(i);
        }
    }

    while (!A.empty()) {
        cout << A.front() << endl; 
        A.pop();       
    }
}

033 - Not Too Bright（★2）

• ん～こういう問題に弱い
• 冷静に考えたら上界:「2*2の領域の中で1個しか配置できない」、下界:「上下において奇数の場所に点灯させる」が一致することから一般化させても（i,j）が両方奇数となる場所に配置するのが最適となるらしい
• その個数は((H + 1) / 2) * ((W + 1) / 2)）とする。
• あとはコーナーケースである縦もしくは横が1の場合を排除する。
• 実装は以下の様にシンプルになる

int H, W;

int main() {
	cin >> H >> W;
	if (H == 1 || W == 1) cout << H * W << endl;
	else cout << ((H + 1) / 2) * ((W + 1) / 2) << endl;
	return 0;
}

055 - Select 5（★2）

• Nが100以下なので5乗すると10^10
• しかしnC₅の組み合わせを考えると係数が1/120となるためにギリギリ間に合うらしい。気づかなかった