ABC097 C K-th Substring

2020 競プロ AtCoder 300 ABC097 prefix 文字列

ABC097 C K-th Substring

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc097/tasks/arc097_a

考察

  • N=|s|とおくとO\left(N^2 \right)に見えてO\left(N^3 \right)だった．．．．
    （文字列比較にO\left(N \right)）かかるやん・・・(´・ω・｀)
  • 得られた知見：答えの文字列の長さが高々Kであること

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>


using namespace std;


/******************************************************************************************/



int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

	string s;
	int k;
	cin >> s >> k;

	int n = s.size();
	set<string> st;
	for (int i = 1; i <= k; i++)
	{
		//i文字の部分文字列
		for (int j = 0; j < n; j++)
		{
			if (j + i > n)continue;
			st.insert(s.substr(j, i));
		}
	}
	int cnt = 1;
	for (auto itr : st) {
		if (cnt == k) {
			cout << itr << endl;
			return 0;
		}
		cnt++;
	}
	return 0;
}

ABC151 E Max-Min Sums

2020 競プロ AtCoder 500 数学 式変形 各値ごとに数え上げる ABC151 あまりに注意 前処理 数え上げ

ABC151 E Max-Min Sums

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc151/tasks/abc151_e

考察

  • 式変形すると， \sum f\left(X \right) = \sum \left(maxX\right) - \sum \left(minX \right)となるので各A_{i}が最大値，最小値となる集合Sの個数を求めればよいことが分かる
  • 考察は比較的素早くできたのにあまりの部分で5WA，，，，，悲しい

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long int ll;
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;


/******************************************************************************************/


struct Combination {

	vector<ll> fact, rfact;

	Combination(ll sz) : fact(sz + 1), rfact(sz + 1) {

		fact[0] = 1;
		for (ll i = 1; i < fact.size(); i++) {
			fact[i] = fact[i - 1]%MOD * i % MOD;
		}
		//逆元
		rfact[sz] = inv(fact[sz]);
		for (ll i = sz - 1; i >= 0; i--) {
			rfact[i] = rfact[i + 1] %MOD * (i + 1) % MOD;
		}
	}

	ll inv(ll x) {
		return pow(x, MOD - 2);
	}
	ll pow(ll x, ll n) {
		ll ret = 1;
		while (n > 0) {
			if (n & 1) (ret *= x) %= MOD;
			(x *= x) %= MOD;
			n >>= 1;
		}
		return (ret);
	}
	ll P(ll n, ll r) {
		if (r < 0 || n < r) return (0);
		return (fact[n] * rfact[n - r] % MOD);
	}

	ll C(ll p, ll q) {
		if (q < 0 || p < q) return (0LL);
		return (fact[p]%MOD * rfact[q] % MOD * rfact[p - q] % MOD);
	}

	ll H(ll n, ll r) {
		if (n < 0 || r < 0) return (0);
		return (r == 0 ? 1 : C(n + r - 1, r));
	}
};



int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);


	ll n, k;
	cin >> n >> k;


	Combination comb(n + 10);

	vector<ll> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	ll ans = 0;

	ll maxi = 0;

	ll mini = 0;

	for (int i = 0; i < n; i++)
	{
		mini += (a[i] % MOD) * (comb.C(n - i - 1, k - 1) % MOD);
		mini = (mini + MOD) % MOD;
	}

	reverse(a.begin(), a.end());
	for (int i = 0; i < n; i++)
	{
		maxi += (a[i] % MOD) * (comb.C(n - i - 1, k - 1) % MOD);
		maxi = (maxi + MOD) % MOD;
	}

	cout << (maxi - mini + MOD) % MOD << endl;

	return 0;
}

第6回 ドワンゴからの挑戦状 予選 B Fusing Slimes

2020 競プロ AtCoder 数学 式変形 600 数え上げ 実験 区間ごとに見る

第6回 ドワンゴからの挑戦状 予選 B Fusing Slimes

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b

考察

  • 各区間が何回使われるのかを数え上げれば良さそうなのは分かった．
  • あとは実験してくと，見えてくるものがある．
  • 各区間ごとに\displaystyle \left(x_{i+1}-x_{i}\right)\sum_{j=1}^{i}\cfrac{1}{j}を数え上げる
  • ん～解けたかった．．．．

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

typedef long long int ll;

const ll MOD = 1e9 + 7;


/******************************************************************************************/
struct Combination {

	vector<ll> fact, rfact;

	Combination(ll sz) : fact(sz + 1), rfact(sz + 1) {

		fact[0] = 1;
		for (ll i = 1; i < fact.size(); i++) {
			fact[i] = fact[i - 1] * i % MOD;
		}
		//逆元
		rfact[sz] = inv(fact[sz]);
		for (ll i = sz - 1; i >= 0; i--) {
			rfact[i] = rfact[i + 1] * (i + 1) % MOD;
		}
	}

	ll inv(ll x) {
		return pow(x, MOD - 2);
	}
	ll pow(ll x, ll n) {
		ll ret = 1;
		while (n > 0) {
			if (n & 1) (ret *= x) %= MOD;
			(x *= x) %= MOD;
			n >>= 1;
		}
		return (ret);
	}
	ll P(ll n, ll r) {
		if (r < 0 || n < r) return (0);
		return (fact[n] * rfact[n - r] % MOD);
	}

	ll C(ll p, ll q) {
		if (q < 0 || p < q) return (0);
		return (fact[p] * rfact[q] % MOD * rfact[p - q] % MOD);
	}

	ll H(ll n, ll r) {
		if (n < 0 || r < 0) return (0);
		return (r == 0 ? 1 : C(n + r - 1, r));
	}
};


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);


	
	int n;
	cin >> n;
	Combination comb(n + 10);
	vector<ll> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	ll p = 1LL;
	for (ll i = 1; i < n; i++)
	{
		p *= i;
		p %= MOD;
	}

	ll ans = 0;

	ll tm = 0;
	for (int i = 0; i < n - 1 ; i++)
	{
		ll diff = a[i + 1] - a[i];	
		tm += comb.inv(i + 1LL);
		tm %= MOD;
		ans += diff * tm;
		ans %= MOD;

	}
	cout << (ans*p)%MOD<< endl;
	
	return 0;
}

ABC150 D Semi Common Multiple

2020 競プロ AtCoder ABC150 400 gcd lcm 数学 式変形

ABC150 D Semi Common Multiple

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc150/tasks/abc150_d

考察

  • 式変形すると，X=\cfrac{a_{i}}{2}\left(2p+1\right)となる
  • X=\left(a_{i}の半分\right)*\left(奇数\right)になるのでXは\cfrac{a_{i}}{2}の倍数であり，\cfrac{a_{i}}{2}で割った商が奇数となるものになる
  • なので，\cfrac{a_{i}}{2}の最小公倍数を求めて，それを\cfrac{a_{i}}{2}で割った商が1つでも偶数になるならダメ，それ以外は\cfrac{最小公倍数+1}{2}個ある

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

typedef long long int ll;

/******************************************************************************************/



//ユークリッド互除法
template<typename T>
T gcd(T x, T y) {

	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}

/*最小公倍数*/
template<typename T>
T lcm(T x, T y) {
	T tmp = gcd(x, y);

	return x /tmp * y;
}


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);


	ll n, m;
	cin >> n >> m;
	ll ans = 0;
	vector<ll> a(n);

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		a[i] /= 2;
	}
	ll hoge = a[0];

	for (int i = 0; i < n; i++)
	{
		hoge = lcm(hoge, a[i]);
		if (hoge > m) {
			cout << 0 << endl;
			return 0;
		}
	}

	bool flag = true;
	for (int i = 0; i < n; i++)
	{

		if ((hoge / a[i]) % 2 == 0) {
			flag = false;
		}
	}

	if (flag) {
		cout << (m / hoge + 1) / 2 << endl;
	}
	else
	{
		cout << 0 << endl;
	}


	return 0;
}

2020/01/05の進捗

  • 卒論を進めた
  • pandas周りのリファレンスを読んでみた（知らないの多すぎ．．．）


この書き方初めて知ったよ．．．．

valid_fraction = 0.1
valid_size = int(len(data) * valid_fraction)

train = data[:-2 * valid_size]
valid = data[-2 * valid_size:-valid_size]
test = data[-valid_size:]

2020年の抱負

2019 競プロ AtCoder ABC092 350 dp

2020年の目標

はじめに

「あけましておめたぷにきあくん笑」（訳：あけましておめでとうございます）．
本年もよろしくお願いいたします．


今年の目標

おわりに

  • うしたぷにきあ君笑ってなに笑

AOJ ALDS1_7_C 木の巡回

2020 競プロ AOJ ADLS 木 再帰関数 木の巡回

AOJ ALDS1_7_C 木の巡回

問題概要

リンク参照

問題リンク

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_C

考察

  • ただただ実装するだけではあるけど今まで書いたことがなかったので勉強になった．
  • 出力と再帰で潜るタイミングを変えれば良い

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
#include<complex>
#include<list>
#include<cstdio>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)


using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;




const int INF = 1e9 + 7;


/******************************************************************************************/


vector<int> G[30];
int in[30];

void preParse(int now) {

	if (now == -1) {
		return;
	}
	
	cout << " " << now;
	
	preParse(G[now][0]);
	preParse(G[now][1]);
}


void inParse(int now) {

	if (now == -1) {
		return;
	}

	inParse(G[now][0]);

	cout << " " << now;

	inParse(G[now][1]);
}


void postParse(int now) {

	if (now == -1) {
		return;
	}

	postParse(G[now][0]);
	postParse(G[now][1]);
	cout << " " << now;
}



int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		G[a].push_back(b);
		G[a].push_back(c);

		if (b != -1) {
			in[b]++;
		}
		if (c != -1) {
			in[c]++;
		}
	}


	//root探し
	int root = 0;
	for (int i = 0; i < n; i++)
	{
		if (in[i] == 0) {
			root = i;
			break;
		}
	}

	cout << "Preorder" << endl;
	preParse(root);
	cout << endl;

	cout << "Inorder" << endl;
	inParse(root);
	cout << endl;

	cout << "Postorder" << endl;
	postParse(root);
	cout << endl;
	
	return 0;
}