読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 6/7/8

yukicoder

なんか素数扱う問題がやけに多い気がします。

- 6 使い物にならないハッシュ

  • 問題概要

ある素数pの各桁の和をp'とします。p'が二桁以上ある場合はもう一度各桁の和をとりそれをp'とします。
p'が一桁になったとき,それをp'のハッシュ値とします。
K,Nを素数としたとき、[K,N]の区間内の素数をハッシュテーブルに格納します。
ハッシュテーブルのコリジョンが起きないN-Kが最大となる区間のNを答えよという問題です。

  • 解説

しゃくとり法の典型問題です。
まずエラトステネスのふるいを用いてNまでの素数を全て列挙しておきます。
エラトステネスのふるいの計算量はO(N \log \log N)、ほぼO(N)です。
素数を列挙できたら各素数ハッシュ値を全て求めます。
素数の数が計算量に必要な場合はガウス素数定理とかを用いてだいたい予測できるのでそれを用いましょう。ネット環境があればggったほうが早いかもですが。
あとはしゃくとり法を用いて|r-l|が最大になる区間を求めましょう。
l,rは単調増加なので素数の数をP_N \approx \frac{N}{\log N}とするとO(P)です。
結局全体の計算量はエラトステネスのふるいにかかるコストのみですね。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
int Hash(string s){
	int n = (int)s.size(),t=0;
	if (n == 1)return(stoi(s));
	for (int i = 0; i < n; i++)
	{
		t += s[i] - '0';
	}
	return Hash(to_string(t));
}

bool prime[1000000];
vector<int> prime_list;
vector<int> hash_list;
int table[10] = { 0 };
int len = 1, st = 0;
int main(void){
	int K, N;
	cin >> K >> N;
	for (int i = 0; i <= N; i++)
	{
		prime[i] = true;
	}
	prime[0] = prime[1] = false;
	for (int i = 0; i <= N; i++)
	{
		if (prime[i]){
			for (int j = (i << 1); j <= N; j += i)
			{
				prime[j] = false;
			}
			if (i >= K){
				prime_list.push_back(i);
				hash_list.push_back(Hash(to_string(i)));
			}
		}
	}
	st = prime_list[0];
	table[hash_list[0]]++;
	int l = 0, r = 1;
	while (r < ((int)prime_list.size())){
		while (table[hash_list[r]]>0)
			table[hash_list[l++]]--;

		if (len <= (r - l + 1))len = (r - l + 1), st = prime_list[l];
		table[hash_list[r++]]++;
	}
	cout << st << endl;
	return 0;
}

- 7 プライムナンバーゲーム

  • 問題概要

二人でゲームをしています。
ある数Nが与えられます。
NからN以下の素数を引いて相手にその数を新たなNとして渡します。
相手に渡された数字が0か1なら勝ちです。
最初の数字Nが与えられたとき先手必勝か後手必勝か答えよという問題です。

  • 解説

ARCで殺され掛けたのでゲーム系統の問題見ると真っ先にGrundy数に落とせないか考えるようになりました。
0,1は無視していいです。
相手に与えられた数字が2or3のとき負けです。
つまり2or3に遷移できれば勝ちです。
数字がnのときのグランディー数をg(n)とすると、g(2)=g(3)=0とします。
g(n)= g(n-p)で現れない最小の正整数(pはp < Nを満たす素数)とすると
計算量はO(\frac{N^2}{\log N})でN以下の全ての正整数に対するグランディー数が求められます。
実際はグランディー数の計算にsetとかを使って数字の集合を求める必要があるのでO(N)かかっちゃってO(N^2)ですね。
あとはg(N)が0かどうか判別するだけです。

別解として、小さい値から普通にDPしてminmaxアルゴリズム回しても大丈夫です。
ていうかこっちが想定解だったみたいです。こっちだとsetいらないのでO(\frac{N^2}{\log N})

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;

bool prime[10001];
vector<int> prime_list;
int gr[10001];

int main(void){
	int N;
	cin >> N;
	for (int i = 0; i <= N; i++)
	{
		prime[i] = true;
	}
	prime[0] = prime[1] = false;
	for (int i = 0; i <= N; i++)
	{
		if (prime[i]){
			for (int j = (i << 1); j <= N; j += i)
			{
				prime[j] = false;
			}
			prime_list.push_back(i);
		}
	}

	gr[0]=gr[1]=gr[2] =gr[3]= 0;
	

	for (int i = 4; i <=N; i++)
	{
		set<int> g;
		for (auto &x : prime_list){
			if (i - x < 2)break;
			g.insert(gr[i - x]);
		}
		int now=0;
		for (auto &x : g){
			if (x!=now)break;
			now++;
		}
		gr[i] = now;
		//cout << i << " " << gr[i] << endl;
	}
	if (gr[N])cout << "Win" << endl;
	else cout << "Lose" << endl;
	return 0;
}

- 8 N言っちゃダメゲーム

  • 問題概要

21言っちゃダメゲームを知らないのですが世代間格差というものなのでしょうか。
0から始まり、交互にK以下の正整数を加算して、加算結果がN以上になったら負けというゲームです。

  • 解説

加算結果がN-1にできれば勝ちです。
その前の相手の加算結果が[N-(K+1),N-2)]ならば絶対にN-1にできます。
N-1-n(K+1)からは絶対にN-1-m(K+1)以外にしか遷移できなくて(n,mは整数)
N-1-k(K+1)からは絶対にN-1-s(K+1)に遷移できます。
つまり初期状態がN-1-n(K+1)なら絶対に負けて、それ以外なら絶対勝てます。
初期状態は0なのでN-1-n(K+1)=0を変形するとN=n(K+1)+1のとき敗北です。
N%(K+1)==1のとき負けですね。

#include<iostream>
using namespace std;


int main(){
	int P,N,K;
	cin >> P;
	while (P--){
		cin >> N >> K;
		if (N % (K + 1) == 1)cout << "Lose" << endl;
		else cout << "Win" << endl;

	}
	return 0;
}