ABC167自分なりのまとめ - 盆栽エンジニアリング日記

A- Registration

SとTの末尾以外を比較して一致していればOK

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  string s, t;
  cin >> s >> t;
  rep(i, s.size()) {
    if(s[i] != t[i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

B-Easy Linear Programming

A+BがKよりも大きいならばKが答え
A+BがK以下ならばA+BからK - (A + B)を引いたものが答え

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  ll result = 0;
  if( a + b <= k ) {
    result += a;
    k -= a + b;
  }else{
    result += k;
    cout << result << endl;
    return 0;
  }
  result -= k;
  cout << result << endl;
}

C-Skill Up

久しぶりのBit全探索
ある参考書を購入する場合は1,購入しない場合を0とすると、参考書の購入パターンは12桁の2進数で表すことができる。
2¹² = 4096であるため、全パターンを探索することが可能。
コードが少し汚いけど許してください。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int n, m, x;
  cin >> n >> m >> x;
  v c(n, 0);
  vector<vector<int>> a(n, vector<int>(m, 0));
  rep(i, n) {
    cin >> c[i];
    rep(j, m) {
      cin >> a[i][j];
    }
  }
  int result = intmax;
  for(int i = 1; i <= 4096; i++) {
    v alg(m, 0);
    int cost = 0;
    for(int j = 0; j < n; j++) {
      if(i & (1 << j)) {
        rep(k, m) {
          alg[k] += a[j][k];
        }
        cost += c[j];
      }
    }
    bool ok = true;
    rep(k, m) {
      if(alg[k] < x) {
        ok = false;
      }
    }
    if(ok) {
      result = min(result, cost);
    }
  }
  if (result == intmax) {
    cout << -1 << endl;
  }else{
    cout << result << endl;
  }
}

D-Teleporter

与えられた問題をグラフで考えてみると、全てのノードの出次数が1となっているグラフであることがわかる。
出次数とは、自分から出ていく辺の数です。
全ノードの出次数が1であるため、たかだかN回移動を繰り返すと、必ず訪問済みのノードに到達することがわかります。
一度訪問済みのノードに到達すると、あとはそのループを繰り返すだけになります。
最初のサンプルを例に取ると、

1 -> 3 -> 4 -> 1

というルートで訪問済みの1に戻ることになります。
そして、以降はどれだけ移動を重ねても、その経路はこのループ上をぐるぐる回るだけになります。
この性質を用いると、K回の移動をシミュレーションする必要がなくなります。
具体的には、ループに入るまでに必要な移動数をK'、ループの長さをLとすると
(K - K') % L回、ループの先頭から移動するだけでよくなります。
これは、(K - K') / L回のループ回数は省略することができるためです。
Lは必ずN以下であるため、計算量も十分高速です。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int n;
ll k;
int a[2 * 100000];

pair<int, ll> calc(int start) {
  if(k == 0) return {start, 1};
  vector<bool> flag(n, false);
  flag[start] = true;
  int cnt = 0;
  while(1) {
    start = a[start] - 1;
    cnt++;
    if(k == cnt){
      k -= cnt;
      return {start, cnt};
    };
    if(flag[start]){
      k -= cnt;
      return {start, cnt};
    }else{
      flag[start] =true;
    }
  }
}

int main()
{
  cin >> n >> k;
  rep(i, n) cin >> a[i];
  auto stop = calc(0);
  if(stop.first != 0) {
    stop = calc(stop.first);
  }
  ll rest = k % stop.second;
  int result = stop.first;
  rep(i, rest) {
    result = a[result] - 1;
  }
  cout << result + 1 << endl;
}

E-Colorful Blocks

先週に続いて、今週も自力で解くことができました！
まず最初に、素朴なケースであるK=0の場合を考えてみます。
この場合、最初のブロックにはM色を選ぶことができ、あとのブロックにはそれぞれM-1色を選ぶことができます。
これは、1つ前のブロックと同じ色は選ぶ事ができないためです。
よって、ありえるパターン数はM * (M - 1)^{N - 1}個となります。
次に、このケースを利用してK=1の場合を考えてみましょう。
K=1の場合、すべての組の中で1つだけ色が同じになる組を許します。
今、組はN-1個あり、この中から1つを選ぶ組み合わせの数はN-1 C 1個あります。
そして、そのような組を1つ選ぶとありえるパターン数はM * (M - 1)^{N - 1} / (M - 1)となります。
これは、1つのブロックの色の選択肢がなくなるためです。
よって、K=1の場合、(M * (M - 1)^{N - 1} / (M - 1)) * (N - 1 C 1)となります。
K=2以降の場合についても、同様の考え方で求めていく事ができます。
注意点としてはM = 2の場合にはK = N - 1以外は可能な塗り方が存在しないことと、
modの世界で計算をしていくので逆元を求める必要があることです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 998244353;
const double pi = M_PI;


template <typename number>
pair<number, number> extended_euclid(number a, number b)
{
  number r0, r1, a0, a1, b0, b1;
  r0 = a; r1 = b;
  a0 = 1; a1 = 0;
  b0 = 0; b1 = 1;
  while (r1>0) {
    number q1 = r0 / r1;
    number r2 = r0 % r1;
    number a2 = a0 - q1 * a1;
    number b2 = b0 - q1 * b1;
    r0 = r1 ; r1 = r2;
    a0 = a1 ; a1 = a2;
    b0 = b1 ; b1 = b2;
  }
  number c = r0;
  a = a0; //x
  b = b0; //y
  return  {a, c};
}

template  <typename number>
number inverse_N(number a, number N)
{
  pair<number, number> result = extended_euclid(a, N);
  if(result.first < 0)
  {
    result.first = result.first + N;
  }
  return result.first;
}

ll n, m, k;

ll calc() {
  ll result = m;
  rep(i, n - 1) {
    result = (result * (m - 1)) % mod;
  }
  return result;
}

int main()
{
  cin >> n >> m >> k;
  if(m == 1) {
    if(k == n - 1){
      cout << 1 << endl;
    }else{
      cout << 0 << endl;
    }
    return 0;
  }
  ll base = calc();
  ll minv = inverse_N(m - 1, mod);
  ll numerator = n - 1;
  ll denominator = 1;
  ll cand = numerator;
  ll result = base;
  for(int i = 1; i <= k; i++) {
    ll temp = base * minv;
    temp %= mod;
    temp *= cand;
    temp %= mod;
    result += temp;
    result %= mod;
    //分母の更新
    numerator = (numerator * (n - 1 - i)) % mod;
    //分子の更新
    denominator = (denominator * (i + 1)) % mod;
    //組み合わせの更新
    cand = numerator * inverse_N(denominator, mod);
    cand %= mod;
    //減る候補を更新
    minv = minv * inverse_N(m - 1, mod);
    minv %= mod;
  }
  cout << result << endl;
}