Between Two Sets
問題概要
長さ の数列 と, 長さ の数列 がある. の全要素の倍数であって の全要素の約数である値 の個数を出力せよ.
解法
の全要素の約数である必要があるので値 の候補は である. このような をすべて試せば良い.
ソース
#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
問題概要
文字列 に対しちょうど 回の以下の操作をして文字列 にしたい.
- 文字列の末尾にある 文字を加える
- 文字列の末尾の文字 削除する, 文字列が空のときは空のままである
解法
を にするための最短回数の操作を考える.
先頭から一致していない部分を削除して, になるように文字を加えるのが最適である.
最短回数で消したとき, 最短回数 のときも にできる. 余分に 文字足して 文字消す操作を繰り返せば良い.
最短回数 はできないが, 文字列を全部消して, 空の状態でもう 回消すと周期がずれて良い感じになるので, そちらで可能かどうか判定する.
ソース
#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
問題概要
にいる.
ステップで, ユークリッド距離が か の距離の地点に移動できる.
に移動するための最小ステップ数を求めよ.
海保
場合分け.
まず のとき . ちょっと斜め上に行って, 回下がれば良い.
次に のとき .
さらに のとき .
それ以外は 距離 のステップを 回使って三角形を作ればよいので .
ソース
#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 でゲームをする. 最初 個の石の山がある. First が常に先攻である.
- 集合 を 個の異なる整数 と定義する.
- プレイヤーは交互で行う. 各ターンでは, プレイヤーは 中の要素 を選択し, つの山を, すべて同じ個数の 個の山に分割する. そのような がないとき, そのプレイヤーは負けである.
- 各プレイヤーは最適に行動する.
が与えられるので, First が勝つ時 First
, それ以外のとき Second
と出力せよ.
解法
まず, のとき, 永遠にゲームは終わらないので Second
.
それ以外を考えるが, 見た感じこれは Grundy 数.
Grundy 数 が のとき Second
, それ以外のとき First
を出力すればよさそう.
よくわからなかったので調べてみると, 複数の山からなる Grundy 数で各山が独立であるとき,
らしいのでこれをこの問題に適用する.
求めたいものが とする. この状態では となる要素 を選択できる. このようなものがないとき負けなので である.
要素 を選択すると 個の山が 個に分裂するので, 上式を適用して となる. 結局 は, は当然同じ値で XOR なので の偶奇で求める事ができる. のとき で, のとき である.
あとは適当にメモ化すれば通る. で のため状態数はかなり限られて間に合う.
ソース
#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; }