ABCDを解いた.
A. Alyona and Numbers
問題概要
整数 が与えられる.
を満たす
と,
を満たす
で,
となるような ペア
を作りたい.
の候補数を求めよ.
解法
簡単なのは分かるけど, ちょっと面倒.
は,
としても同じである.
よって, 5 で割った余りが同じものは, まとめてしまって良い.
5で割った余りのそれぞれの個数が分かれば良いので, 適当に切り上げたりしならがら計算する.
ソース
#include <bits/stdc++.h> using namespace std; typedef long long int64; int main() { int64 N, M; cin >> N >> M; int64 ret = 0; for(int64 i = 0; i <= 4; i++) { int64 count1 = (N + 4 - i) / 5; int64 count2 = (M + (i + 1) % 5) / 5; ret += count1 * count2; } cout << ret << endl; }
B. Alyona and Mex
問題概要
長さ の数列
が与えられる.
この数列のある要素 を選んで, 要素の中身を
に置換する操作を好きなだけ行うことが出来る.
数列に現れない正整数の最小値 を定義する. (例えば,
なら
.)
このとき の最大値を求めよ.
解法
のように順番に作っていくことを考える.
同じ数値を作るなら小さい数を使った方が良いので, ソートしたほうがよさそう[1]. ソートする.
このとき以下の貪欲が成立.
1 番目の要素から順に見ていく. 今 番目の要素を見ているとする.
数値 まで作れているとき,
を使って
を作れるかどうかは単純な大小関係. 作れたら作ってしまって良い([1] より).
ソース
#include <bits/stdc++.h> using namespace std; int main() { int N, A[100000]; scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d", &A[i]); sort(A, A + N); int ret = 0; for(int i = 0; i < N; i++) { if(ret < A[i]) ++ret; } printf("%d\n", ret + 1); }
C. Alyona and the Tree
問題概要
頂点 1 を根とする根付き木が与えられる.
すべての辺, 頂点には, それぞれある値を持つ. ここで, 頂点 が持つ値を
とする.
適切に, この木から悲しい頂点がなくなるように葉を消すことを繰り返した時の, 消す葉の数の最小値を求めよ.
このとき悲しい頂点を以下のように定義する.
が悲しい頂点
で,
を満たす頂点
が存在する.
頂点
への経路中の辺に書かれた数の総和.
解法
まず, 部分木が云々という文字列があるのでDPっぽくできそう. 実際できる.
頂点
の祖先ノードから
とするとよくて, の親ノードの
を
, その間の辺のコストを
とすると,
とすれば更新できる(経路はそこの辺で切るか, 親へ行くかのどちらかなので).
最後に, 根から下っていったときに, それぞれ悲しいノードが出たところで切れば良い.
ソース
#include <bits/stdc++.h> using namespace std; typedef long long int64; int64 N, A[100000]; pair< int64, int64 > par[100000]; vector< int64 > graph[100000]; int64 updp[100000]; bool memo[100000]; int64 rec(int idx) { if(idx == -1) return(0); if(memo[idx]++) return(updp[idx]); return(updp[idx] = max(0LL, rec(par[idx].first) + par[idx].second)); } int dfs(int idx) { if(updp[idx] > A[idx]) return(0); int ret = 1; for(int to : graph[idx]) ret += dfs(to); return(ret); } int main() { scanf("%d", &N); for(int i = 0; i < N; i++) { scanf("%d", A + i); } par[0] = {-1, 0}; for(int i = 1; i < N; i++) { int p, c; scanf("%d %d", &p, &c); --p; par[i] = {p, c}; graph[p].push_back(i); } for(int i = 0; i < N; i++) rec(i); printf("%d\n", N - dfs(0)); }
D. Alyona and Strings
問題概要
アルファベット小文字のみで構成された文字列 がある.
から部分文字列を互いに素となるように
個順番に取り出し並べる. この文字列を
とする.
となるように取り出すとき,
の値を最大化せよ.
解法
DPをすれば良い. 以下のように dpテーブルを定義する.
の
文字目かつ
の
文字目以降の文字列で,
個部分文字列を 取り出すときの最長の長さ
この dpテーブルを更新する
まず, その文字は取り出さないことを考えると, 次の文字に進める. これは明らかに以下.
この文字から始まる部分文字列を取り出すことを考えると, 最大の長さの文字列を取り出す方が良い. これが何文字かは, その位置の .
を求めたくなるが, これは事前に DP で求めておけば良い.
この部分文字列を何個に分けるかすべての通りを試す.
計算量は, となって間に合う,
ソース
#include <bits/stdc++.h> using namespace std; int N, M, K; string S, T; int LCP[1006][1006]; int dp[1006][1006][10]; int rec(int S_begin, int T_begin, int dec) { if(dec == -1) return(0); if(S_begin >= S.size() || T_begin >= T.size()) return(-11451419); if(~dp[S_begin][T_begin][dec]) return(dp[S_begin][T_begin][dec]); int ret = max(rec(S_begin + 1, T_begin, dec), rec(S_begin, T_begin + 1, dec)); for(int i = 1; i <= LCP[S_begin][T_begin] && dec - i >= -1; i++) { ret = max(ret, rec(S_begin + LCP[S_begin][T_begin], T_begin + LCP[S_begin][T_begin], dec - i) + LCP[S_begin][T_begin]); } return(dp[S_begin][T_begin][dec] = ret); } int main() { memset(dp, -1, sizeof(dp)); cin >> N >> M >> K; cin >> S >> T; for(int i = S.size() - 1; i >= 0; i--) { for(int j = T.size() - 1; j >= 0; j--) { LCP[i][j] = S[i] == T[j] ? LCP[i + 1][j + 1] + 1 : 0; } } cout << rec(0, 0, K - 1) << endl; }
