ei1333の日記

ぺこい

Week of Code 25

www.hackerrank.com

Between Two Sets

問題概要

長さ  {n(1 \le n \le 10)} の数列  {A = \{a_i\} (1 \le a_i \le 100)} と, 長さ  {m(1 \le m \le 10)} の数列  {B = \{b_i\} (1 \le b_i \le 100)} がある.  {A} の全要素の倍数であって  {B} の全要素の約数である値  {x} の個数を出力せよ.

解法

 {B} の全要素の約数である必要があるので値  {x}候補 {1 \le x \le 100} である. このような  {x} をすべて試せば良い.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, M, A[10], B[10];

  cin >> N >> M;
  for(int i = 0; i < N; i++) cin >> A[i];
  for(int i = 0; i < M; i++) cin >> B[i];

  int ret = 0;
  for(int x = 1; x <= 100; x++) {
    bool flag = true;
    for(int i = 0; i < N; i++) flag &= x % A[i] == 0;
    for(int i = 0; i < M; i++) flag &= B[i] % x == 0;
    ret += flag;
  }

  cout << ret << endl;
}

Append and Delete

問題概要

文字列  {s(1 \le |s| \le 100)} に対しちょうど  {k(1 \le k \le 100)} 回の以下の操作をして文字列  {t(1 \le |t| \le 100)} にしたい.

  • 文字列の末尾にある  {1} 文字を加える
  • 文字列の末尾の文字  {1} 削除する, 文字列が空のときは空のままである

解法

 {s} {t} にするための最短回数の操作を考える.

先頭から一致していない部分を削除して,  {t} になるように文字を加えるのが最適である. 最短回数で消したとき, 最短回数  {+ 2k} のときも  {t} にできる. 余分に  {1} 文字足して  {1} 文字消す操作を繰り返せば良い.
最短回数  {+ 2k + 1} はできないが, 文字列を全部消して, 空の状態でもう  {1} 回消すと周期がずれて良い感じになるので, そちらで可能かどうか判定する.

ソース

#include <bits/stdc++.h>

using namespace std;


int main()
{
  string S, T;
  int K;

  cin >> S;
  cin >> T;
  cin >> K;

  int smallest = 0, biggest = S.size() + T.size();
  while(!S.empty() && T.find(S) != 0) S.pop_back(), ++smallest;
  smallest += T.size() - S.size();

  if(biggest <= K || (smallest <= K && smallest % 2 == K % 2)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Baby Step, Giant Step

問題概要

 {(0, 0)} にいる.

 {1} ステップで, ユークリッド距離が  {a} {b(1 \le a \lt b \le 10^9)} の距離の地点に移動できる.

 {(d, 0)} に移動するための最小ステップ数を求めよ.

海保

場合分け.

まず  {b \le d} のとき  {\lceil d / b \rceil}. ちょっと斜め上に行って,  {1} 回下がれば良い.
次に  {a = d} のとき  {1}.
さらに  {d = 0} のとき  {0}.
それ以外は 距離  {b} のステップを  {2} 回使って三角形を作ればよいので  {2}.

ソース

#include <bits/stdc++.h>

using namespace std;


int main()
{
  int Q;
  cin >> Q;
  for(int i = 0; i < Q; i++) {
    int A, B, D;
    cin >> A >> B >> D;
    if(B <= D) cout << (D + B - 1) / B << endl;
    else if(A == D) cout << 1 << endl;
    else if(D == 0) cout << 0 << endl;
    else cout << 2 << endl;
  }
}

Stone Division

問題概要

以下のようなゲームを考える.

  • First と Second でゲームをする. 最初  {n(1 \le n \le 10^{18})} 個の石の山がある. First が常に先攻である.
  • 集合  {S} {m(1 \le m \le 10)} 個の異なる整数  {\{s_1, s_2, ..., s_{m-1}\} (1 \le s_i \le 10^{18})} と定義する.
  • プレイヤーは交互で行う. 各ターンでは, プレイヤーは  {S} 中の要素  {s_i} を選択し,  {1} つの山を, すべて同じ個数の  {s_i} 個の山に分割する. そのような  {s_i} がないとき, そのプレイヤーは負けである.
  • 各プレイヤーは最適に行動する.

 {n, m, S} が与えられるので, First が勝つ時 First, それ以外のとき Second と出力せよ.

解法

まず,  {\exists i\ \mbox{s.t.}\ s_i = 1} のとき, 永遠にゲームは終わらないので Second.

それ以外を考えるが, 見た感じこれは Grundy 数. Grundy {g(n)} {0} のとき Second, それ以外のとき First を出力すればよさそう.

よくわからなかったので調べてみると, 複数の山からなる Grundy 数で各山が独立であるとき,
 {g(a, b, c) = g(a) \oplus g(b) \oplus g(c)}
らしいのでこれをこの問題に適用する.

求めたいものが  {g(x)} とする. この状態では  {x \equiv 0 \pmod {s_i}} となる要素  {i} を選択できる. このようなものがないとき負けなので  {g(x) = 0} である.

要素  {i} を選択すると  {s_i} 個の山が  {x / s_i} 個に分裂するので, 上式を適用して  {g(x) = \underbrace{ g(s_i) \oplus g(s_i) \oplus ... \oplus g(s_i)}_{x / s_i}} となる. 結局  {g(x)} は,  {g(s_i)} は当然同じ値で XOR なので  {x / s_i} の偶奇で求める事ができる.  {x / s_i \equiv 0 \pmod {2}} のとき  {0} で,  {x / s_i \equiv 1 \pmod {2}} のとき  {g(s_i)} である.

あとは適当にメモ化すれば通る.  {i \ne j} {x / s_i / s_j = x / s_j / s_i} のため状態数はかなり限られて間に合う.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int64 n, m, s[10];
map< int64, int64 > dp;

int64 f(int64 n)
{
  if(dp.count(n)) return (dp[n]);
  set< int64 > x;
  for(int i = 0; i < m; i++) {
    if(n >= s[i] && n % s[i] == 0) {
      int64 g = f(n / s[i]);
      if(s[i] & 1) x.insert(g);
      else x.insert(0);
    }
  }
  int ret = 0;
  while(x.count(ret)) ++ret;
  return (dp[n] = ret);
}

int main()
{
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    cin >> s[i];
  }
  if(count(s, s + m, 1) >= 1 || f(n) == 0) cout << "Second" << endl;
  else cout << "First" << endl;
}