OyamaC'20 解説

Last updated Mar 19, 2020

Editorial

小山高専で, mitsuさん原案のコンテスト OyamaCが行われました. testerを担当したので, 解説を書いておきます.

# fizzbuzz

fizzbuzzは書けますか？N % 15から書くとスムーズです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
  i64 N;
  cin >> N;
  if(N % 15 == 0) cout << "fizzbuzz" << endl;
  else if(N % 3 == 0) cout << "fizz" << endl;
  else if(N % 5 == 0) cout << "buzz" << endl;
  else cout << N << endl;
}

# tiktak

秒の単位換算です. 3600, 60で割ったあまりを計算していけばいいです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
  i64 N;
  cin >> N;
  cout << N / 3600 << endl;
  N %= 3600;
  cout << N / 60 << endl;
  cout << N % 60 << endl;
}

# sumsumsum

みつみつみつみたいですね(は？) これは, $x, y$を$D$をオーバーしない範囲で考えてあげれば, $z$が決まります. 実は, 原案は$1 \le A, B, C, D \le 10^6$でした. あなたは解けますか？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  i64 N = 3;
  vector<i64> A(N);
  rep(i,0,N) {
    cin >> A[i];
  }
  i64 D;
  cin >> D;

  vector<vector<i64>> dp(N + 1, vector<i64>(D + 1, 0));
  dp[0][0] = 1;
  rep(i,0,N) {
    rep(j,0,D + 1) {
      if(j >= A[i]) {
        dp[i + 1][j] = dp[i][j] + dp[i + 1][j - A[i]];
      }
      else {
        dp[i + 1][j] = dp[i][j];
      }
    }
  }
  cout << dp[N][D] << endl;
}

# uniform liner sushi

これは蟻本にも書かれている, 区間スゲジューリング問題ですね. 後ろをなるべく小さくするように取る貪欲で解くことができます.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  i64 N;
  cin >> N;
  std::vector<pair<i64, i64>> vec;
  rep(i,0,N) {
    i64 s, t;
    cin >> s >> t;
    vec.push_back({ s + t, s });
  }

  sort(all(vec));


  vector<i64> ne(1, 0);
  i64 ans = 0;
  rep(i,0,N) {
    if(ne[0] <= vec[i].second) {
      ne[0] = vec[i].first;
      ans++;
    }
  }
  cout << ans << endl;
}

# rot and rot

これが最後の砦だと思ってたんですけど, 皆さんどうでしたか？
僕は行列を用いて移動を表現しました.

$$ \left( \begin{array}{c} S & 1 \end{array} \right) $$

に,

$$ \left( \begin{array}{c} A + 1 & 1 \\\ B & 0 \end{array} \right) $$

を掛けると, 1ステップです. なので, $N$ステップは,

$$ \left( \begin{array}{c} S & 1 \end{array} \right) \left( \begin{array}{c} A + 1 & 0 \\\ B & 1 \end{array} \right) ^ N = \left( \begin{array}{c} S & 1 \end{array} \right) \left( \begin{array}{c} (A + 1) ^ N & 0 \\\ ((A + 1)^N - 1) / ((A + 1) - 1) * B & 1 \end{array} \right) ^ N $$

です. $A = 0$に注意が必要です. 行列累乗でも間に合うと思います.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

const i64 MOD = 1e9 + 7;

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

template<i64 M>
constexpr i64 euinv(i64 val) {
    i64 a = M, b = val;
    i64 x = 0, u = 1;
    while (b) {
        i64 t = a / b;
        swap(a -= t * b, b);
        swap(x -= t * u, u);
    }
    return x < 0 ? x + M : x;
}

template<i64 M>
struct modint {
  i64 a;
  constexpr modint(const i64 x = 0) noexcept: a((x % M + M) % M) {}
  constexpr i64 value() const noexcept { return a; }
  constexpr modint inv() const noexcept { return modint(euinv<M>(a)); }
  constexpr modint pow(i64 r) const noexcept {
    modint ans(1);
    modint aa = *this;
    while(r) {
      if(r & 1) {
        ans *= aa;
      }
      aa *= aa;
      r >>= 1;
    }
    return ans;
  }
  constexpr modint& operator+=(const modint r) noexcept {
    a += r.a;
    if(a >= M) a -= M;
    return *this;
  }
  constexpr modint& operator=(const i64 r) {
    a = (r % M + M) % M;
    return *this;
  }
  constexpr modint& operator-=(const modint r) noexcept {
    a -= r.a;
    if(a < 0) a += M;
    return *this;
  }
  constexpr modint& operator*=(const modint r) noexcept {
    a = a * r.a % M;
    return *this;
  }
  constexpr modint& operator/=(modint r) noexcept {
    i64 ex = M - 2;
    while(ex) {
      if(ex & 1) {
        *this *= r;
      }
      r *= r;
      ex >>= 1;
    }
    return *this;
  }

  constexpr modint operator+(const modint r) const {
    return modint(*this) += r;
  }
  constexpr modint operator-(const modint r) const {
    return modint(*this) -= r;
  }
  constexpr modint operator*(const modint r) const {
    return modint(*this) *= r;
  }
  constexpr modint operator/(const modint r) const {
    return modint(*this) /= r;
  }

  constexpr bool operator!=(const modint r) const {
    return this->value() != r.value();
  }

};

template<const i64 M>
std::ostream& operator<<(std::ostream& os, const modint<M>& m) {
  os << m.value();
  return os;
}

using fp = modint<MOD>;

int main() {
  i64 S, A, B, N;
  cin >> S >> A >> B >> N;
  A++;

  if(A == 1) {
    cout << fp(S) + fp(B) * fp(N) << endl;
  }else {
    /*
     * p = 10^9 + 7, F_pでの演算を考える
     * 
     * [S  1] * [ A + 1  0  ]^N
     *          [   B    1  ]
     *
     * = [S  1] * [ (A + 1)^N                              0 ]
     *            [ ((A + 1)^N - 1) / ((A + 1) - 1) * B    1 ]
     */
    cout << fp(S) * fp(A).pow(N) + (fp(A).pow(N) - fp(1)) / (fp(A) - fp(1)) * fp(B) << endl;
  }

}

# uniform liner sushi 2

2なのでふたつです. 基本区間スケジュールでやりますが, なるべく寿司が食べ終わるのが遅い方を優先的に食べさせるようにするといいです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
int main() {
  i64 N;
  cin >> N;
  std::vector<pair<i64, i64>> vec;
  rep(i,0,N) {
    i64 s, t;
    cin >> s >> t;
    vec.push_back({ s + t, s });
  }

  sort(all(vec));


  vector<i64> ne(2, 0);
  i64 ans = 0;
  rep(i,0,N) {
    if(ne[1] <= vec[i].second) {
      ne[1] = vec[i].first;
      ans++;
    }
    else if(ne[0] <= vec[i].second) {
      ne[0] = vec[i].first;
      std::swap(ne[0], ne[1]);
      ans++;
    }
  }
  cout << ans << endl;
}

# storage

ちょうど満杯, なので容量の情報は正確に持っておく必要があります. これを添え字にもつDPを考えるとよいです. また, $K$個以内については, 最小で何個を考えてやって, 最後にそれが$K$個以下かを判定すればよいです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

int main() {
  i64 A, N;
  cin >> A >> N;
  i64 K;
  cin >> K;
  vector<i64> W(N);
  rep(i,0,N) {
    cin >> W[i];
  }

  vector<vector<i64>> dp(N + 1, vector<i64>(A + 1, 1e18));
  dp[0][0] = 0;
  rep(i,0,N) {
    rep(j, 0, A + 1) {
      if(j >= W[i]) {
        dp[i + 1][j] = std::min(dp[i][j], dp[i][j - W[i]] + 1);
      }
      else {
        dp[i + 1][j] = dp[i][j];
      }
    }
  }
  if(dp[N][A] <= K) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}