ABC167振り返り

ABC167の振り返りをします。

結果は16分A,B,C三完でレートが冷えてしまいました。

D問題でたくさんWAを出してしまいました。

できるはずだと感じた問題ができないと印象に残ります。

ABC164のD問題と今回ABC167のD問題はこれから先も覚えているんじゃないかと思います。

自分のratedコンテストは毎週あるのでできることを増やして実力を上げていきたいです。

コンテスト中

C問題

N <= 12なので全探索しても十分間に合います。
慣れていたのでスムーズにできました。

int main(){
 ll N , M , X; cin >> N >> M >> X;
 vector<ll> c(N);
 vector<vector<ll> > a(N, vector<ll> (M, 0));

 rep(i,N){
   cin >> c[i];
   rep(j,M) cin >> a[i][j];
 }


 ll ans = INF;
 rep(i , (1 << N)){
   vector<ll> score(M);
   ll tmp = 0;
   rep(j, N){
     // j buy
     if( (i >> j) % 2 == 1 ){
       tmp += c[j];
       rep(k, M){
         score[k] += a[j][k];
       }
     }
   }
   bool check = true;
   rep(l,M){
     if(score[l] < X) check = false;
   }

   if(check){
     ans = min(ans , tmp);
   }
 }

 if(ans == INF) cout << -1 << endl;
 else cout << ans << endl;
}

D問題

問題をみて実際にやってみて5分もかからないで解法は思い浮かびました。

しかし、ベクトルaの値に合わせて移動先のベクトルを1-indexで書いてしまい、周期で割った余りが0の時の処理を誤って時間が過ぎ去ってしまいました。

しっかりとコーナーケースを見直しながら0-indexでわかりやすいコードを書かなければと再認識しました。

コンテスト後

D問題

D - Teleporter

ベクトルaを0-indexにして、移動先のベクトルの先頭にも0を追加することでACできました。

int main(){
 ll N, K; cin >> N >> K;
 vector<ll> a(N);
 rep(i,N) cin >> a[i];
 rep(i,N) a[i]--;

 ll zan = K;
 ll now = 0;
 map<ll,ll> m;
 m[0] ++;
 vector<ll> tr;
 tr.pb(0);
 while(1){
   // 移動してzanが0になったら終了
   now = a[now];
   zan--;
   if(zan == 0){
     cout << now + 1 << endl;
     return 0;
   }
   tr.pb(now);
   // mapが重複したらloopの出来上がり
   m[now]++;
   if(m[now] > 1) break;
 }

 // cirを求める
 ll si = tr.size();
 ll start = 0;
 rep(i,si - 1){
   if(tr[i] == tr.back()){
     start = i;
   }
 }
 // si - 1 と startにある状態
 ll cir = (si - 1) - start;
 // marが0ならstartに戻っている状態
 ll mar = (K - start) % cir;

 cout << tr[start + mar] + 1 << endl;
}

コンテスト後の解説放送でダブリングというテクニックがあるのをしりました。

非常にわかりやすく、プログラムのアルゴリズムっぽく、細かいことを気にしなくていいので便利だと思いました。

順番に2^x回後の移動先を求めていき、それを元に実際の移動を行うというアルゴリズムです。

このテーブルの表の作成にO(N logK)で実際の計算はO(log K)で計算できます。

int main(){
 ll N, K; cin >> N >> K;

 // to[i][j] = j kara 2^i回の操作でいく場所
 rep(i, N){ cin >> to[0][i]; to[0][i]--;}
 rep(i,D - 1) rep(j,N) to[i + 1][j] = to[i][to[i][j]];

 ll now = 0;
 bitset<65> tmp(K);
 rep(i,65){
   if(tmp.test(i)) now = to[i][now];
 }
 cout << now + 1 << endl;
}

E問題

E - Colorful Blocks

組み合わせの問題
累乗の計算や組み合わせの計算はやったことがあったのでE問題にもしっかり時間を投入したかったです。

N個、M色、K回まで連続okでの並べ方の総数

x回連続する時は、まずN - x個を並べるので M *(M -1)^(N - x - 1)　通り
それぞれに対して、連続するところを選ぶのが N 個の間の N - 1個の中からx個選べばいいのでN -1 C x　通りあります。

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
   long long res = 1;
   while (n > 0) {
       if (n & 1) res = res * a % mod;
       a = a * a % mod;
       n >>= 1;
   }
   return res;
}


// テーブルを作る前処理
void COMinit() {
   fac[0] = fac[1] = 1;
   finv[0] = finv[1] = 1;
   inv[1] = 1;
   for (int i = 2; i < MAX; i++){
       fac[i] = fac[i - 1] * i % MOD;
       inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
       finv[i] = finv[i - 1] * inv[i] % MOD;
   }
}

// 二項係数計算
long long COM(int n, int k){
   if (n < k) return 0;
   if (n < 0 || k < 0) return 0;
   return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main() {
   // 前処理
   COMinit();

   ll N ,M ,K; cin >> N >> M >> K;

   ll ans = 0;
   rep(i, K + 1){
     ans += ( M * modpow(M - 1 , N - (i + 1) , MOD) % MOD ) * COM(N - 1, i) % MOD;
     ans %= MOD;
   }
   cout << ans << endl;
}

うーん、コンテスト後に見るとD,E共にさらっとできてもいいよなあと思ってしまう。