yukicoder 1/2 - 競技プログラミングをするんだよ

1は20分、2は諦めて解説読みました。
2の解法が衝撃的でした。

- 1 道のショートカット

問題概要

1,,,Nの番号がついた町があります。
道路がM本あって各道路には移動に必要な時間とお金が設けられています。
道路は一方通行で、番号の小さい町から大きい町へ移動する道路しか存在しません。
C円以下で1の町からNの町に移動する手段のうち最小の移動時間を応えよという問題です。

解説

グラフ最短路なのでダイクストラとかを最初に考えてしまいますがたぶん解けません。
この問題は制約上閉路がありませんが閉路があってもたぶん大丈夫な解法です。
dp(v,c)をc円で町1から町vまで移動できる最小の時間とします。
辺(u,v)があったとき、dp(v,c)=min(dp(v,c),dp(u,c-cost(u,v))+time(u,v))で求められます。
dp(0,0)=0,他をすべてINFにすると、
上の更新を全ての辺に対して行うと1つの町を経由していけるdp(v,c)がすべて求められます。
もう一度全ての辺に対して更新を行うと2つ以内の町を経由していけるdp(v,c)が求められます。
k回更新を行うとkつ以内の町を経由していけるdp(v,c)がすべて求められます。
町の数の最大が50なので、ありうる最長パスは50個の町を経由するパターンなので、50回更新を行えば答えが求まります。
計算量は(町の数)*(辺の数)*(お金)なので50*1500*300=2*10^7ぐらいです。ただfor文の中身が単純なのでワーシャルフロイドのような速さが出ると思います。

ソースコード

#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;
#define LL long long

#define V 50
#define E 1500
#define M 301
LL dp[V][M];
const LL INF = 1e9;
LL from[E], to[E], tim[E], cost[E];
LL v, m, e;

void solve(){
	for (int i = 0; i < V; i++)
		for (int j = 0; j < M; j++)dp[i][j] = INF;
	dp[0][0] = 0;
	for (int i = 0; i < 51; i++){
		for (int j = 0; j < e; j++){
			for (LL k = cost[j]; k <= m; k++)
				dp[to[j]][k] = min(dp[to[j]][k], dp[from[j]][k - cost[j]] + tim[j]);
		}
	}


}
int main(void){
	cin >> v >> m >> e;
	v--;
	for (int i = 0; i < e; i++){ cin >> from[i]; from[i]--; }
	for (int i = 0; i < e; i++){ cin >> to[i]; to[i]--; }
	for (int i = 0; i < e; i++)cin >> cost[i];
	for (int i = 0; i < e; i++)cin >> tim[i];
	solve();
	LL res = INF;
	for (int i = 0; i <= m; i++)
		res = min(res, dp[v][i]);
	cout << ((res==INF)?-1:res) << endl;
	return 0;
}

- 2 素因数ゲーム

問題概要

A君とB君がいます。
ある自然数Nがあって、交互にNの素因数のべき乗で割っていきます。
素因数のべき乗は2以上であればOKです。
A君から割り算を行い、最終的にNを1にしたほうの勝ちです。
お互いが最善手を尽くした場合どちらが勝つでしょうか。

解説

Nimという複数の山から小石をとるゲームがあります。
Nimの最善手を選んだ時の先手後手必勝の求め方は各山の小石の数の排他的論理和を使ったものです。

i番目に小さい素数を $p_i$ とすると、
$N=p_1^{k_1} *p_2^{k_2}*,,,*p_n^{k_n}$ としたとき、小石の山がn個あって各山に小石が $k_1,k_2,,,k_n$ 個ある状態のNimとこのゲームは一致します。
したがって素因数分解をして排他的論理和を取るだけです。
Nimの必勝手の求め方の証明はこちらを見ました。
http://sherbet.transjiggen.com/ccs/ccs_wiki2/index.php?Nim

ソースコード

そもそもこの問題を解くまでNimというゲームを知らなかったので解けるはずもなかった。

#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 main(void){
	list<int> p;
	int N;
	cin >> N;
	for (int i = 2; i*i <= N; i++){
		int sum = 0;
		while (N%i==0)N /= i,sum++;
		if (sum > 0)p.push_back(sum);
		
	}
	if (N > 1)p.push_back(1);
	//cout << N << endl;
	int res = 0;
	for (auto x : p)res^= x;
	if (res)cout << "Alice" << endl;
	else cout << "Bob" << endl;

}