競プロ日記#25/09/23

AtCoder

典型90問

032 - AtCoder Ekiden（★3）

• 何度目かの復習にもかかわらずnext_permitationを使うところ以外定着していない...
• X,Yの二選手における険悪さを二次元のbool型配列で管理する

064 - Uplift（★3）

• 階差を考える
• 階差を考えるという発想自体がなかった。

069 - Colorful Blocks 2（★3）

• ちょっと難しかった。答えを出す式ans = (K * (K-1) * pow((K - 2),N - 2));はもちろん分かったのだがNが2以下の場合分けやpow((K - 2),N - 2)の部分の工夫が足りなかった
• しかし正直解説のポイントがイマイチ理解しきれない。
• ChatGPTに聞いてみると2進法を利用するイメージということで何となくつかめた

以下解説コードを一部抜粋

int main() {
	long long N; int K;
	cin >> N >> K;
	if (K == 1) {
		cout << (N == 1 ? 1 : 0) << endl;
	}
	else if (N == 1) {
		cout << K % mod << endl;
	}
	else if (N == 2) {
		cout << (long long)(K) * (K - 1) % mod << endl;
	}
	else {
		cout << (long long)(K) * (K - 1) % mod * binpower(K - 2, N - 2) % mod << endl;
	}
	return 0;
}

AtCoder Beginner Contest 183

C - Travel

• 類題である032 - AtCoder Ekiden（★3）に取り組んだ後なのに解けないの普通に不愉快。
• vecの初期化でミスらないようにする
• 次の都市を指したいならsum += T[vec[i]][i + 1]
• 「スタート地点を固定しない」と答えが倍増するのでスタート地点を0に固定する。そのために

vector<ll> vec(N - 1);
iota(vec.begin(), vec.end(), 1);

でvecを初期化する

int main() {
    ll N,K;
    cin >> N >> K;
    ll T[8][8];
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            ll a;
            cin >> a;
            T[i][j] = a;
        }
    }

    vector<ll> vec(N - 1);
    iota(vec.begin(), vec.end(), 1);

    ll ans = 0;
    sort(vec.begin(), vec.end());
    do
    {
        ll sum = 0;
        ll prev = 0;
    for (ll x : vec) {
        sum += T[prev][x];
        prev = x;
    }
        sum += T[prev][0];
        if (sum == K) ans++;
    }while(next_permutation(vec.begin(), vec.end()));


    cout << ans << endl;
}