C………
1947 -> 1904.
A. Find Amir
問題概要
個の学校があって から の番号がつけられている.
始点と終点は自由で, すべての学校を訪れたい.
学校 と学校 との間を移動するためにはチケットが必要で, そのコストは である. 一度買ったチケットはチケットは何回でも使える.
解法
と , と , と … との間はコスト で移動できる.
だいたい 個のグループをすべてまとめるのにかかるコストを知りたくなる.
と , と というふうに結ぶとコスト なのでこれが最適.
答えは となる.
ソース
こういう問題, 謎反例がありそうで怖い.
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; if(N % 2 == 0) { cout << N / 2 - 1 << endl; } else { cout << N / 2 << endl; } }
B. Minimum number of steps
問題概要
と からなる文字列が与えられる.
文字列中に の部分文字列が存在する間, それを に置き換える.
置き換える回数の最小値を求めよ.
解法
文字列を先頭から見ていって, 文字を追加していく感じで考える.
ある文字列に を加えると, が今までに現れた の文字数とすると, 操作回数は 回増加する.
その和を求めれば解.
ソース
なんか, 寝てたら他の人々が無限にACしていて最遅になってしまってつらかった.
#include <bits/stdc++.h> using namespace std; typedef long long int64; const int mod = 1e9 + 7; int main() { int64 fact[1000001]; fact[0] = 1; for(int i = 1; i <= 1000000; i++) { fact[i] = fact[i - 1] * 2; fact[i] %= mod; } string S; cin >> S; int64 ret = 0; int A_sz = 0; for(int j = 0; j < S.size(); j++) { if(S[j] == 'b') { ret += fact[A_sz]; ret %= mod; ret += mod - 1; ret %= mod; } else { ++A_sz; } } cout << ret << endl; }
C. Ice cream coloring
問題概要
頂点の木 が与えられる.
また 種類のアイスクリームが売られている.
頂点 では 種類のアイスクリームが購入できる.
同じ種類のアイスクリームについては, 木 内で部分連結である.
新たな 頂点のグラフ を考える. の頂点で, 種類 と のアイスクリームが売られている頂点が存在する時, 頂点 と頂点 に辺が張る.
の彩色数の最小値と, その塗り方を求めよ.
解法
適当な頂点を根とした根付き木を考える.
連結という条件を上手く使う.
根から下っていったときに, ある頂点ではじめて現れるアイスクリームは, その部分木以外では現れることはない.
またある頂点について, 親で現れていたアイスクリームが, ある頂点で現れなくなった時, その部分木内では現れない.
これだけわかれば, あとは自明(コンテスト中は自明ではなかった).
行きがけ順に, 自分の頂点が販売できるアイスクリームのうちまだ色が決まっていない種類について, 貪欲に最小の色を割り当てれば良い.
ある頂点でどの色を使っていないかは, 鳩ノ巣(鳩ノ巣ではないね)っぽくやると全体で の合計くらいに収まる.
ソース
ソースコード, 思っていたよりずっとシンプルだよね….
#include <bits/stdc++.h> using namespace std; int N, M; vector< int > beet[300001]; vector< int > g[300001]; int color[300001]; int used[300001]; void dfs(int idx, int par = -1) { vector< bool > used(beet[idx].size() + 1, 0); for(auto &c : beet[idx]) { if(~color[c]) used[min((int) beet[idx].size(), color[c])] = idx; } int tail = 0; for(auto &c : beet[idx]) { while(used[tail]) ++tail; if(!~color[c]) color[c] = tail++; } for(auto &to : g[idx]) { if(to != par) dfs(to, idx); } } int main() { scanf("%d %d", &N, &M); for(int i = 0; i < N; i++) { int S; scanf("%d", &S); while(S--) { int t; scanf("%d", &t); beet[i].push_back(t); } } for(int i = 1; i < N; i++) { int a, b; scanf("%d %d", &a, &b); --a, --b; g[a].push_back(b); g[b].push_back(a); } memset(used, -1, sizeof(used)); memset(color, -1, sizeof(color)); dfs(0); int res = 1; for(int i = 1; i <= M; i++) res = max(res, color[i] + 1); cout << res << endl; for(int i = 1; i <= M; i++) cout << max(1, color[i] + 1) << " "; cout << endl; }