ABCDを解いた.
A. One-dimensional Japanese Crossword
問題概要
個のマスからなる列があって, それぞれ白か黒で塗られている.
連続する黒マスの個数を出力せよ.
解法
一次元のお絵かきロジックである.
ルール通りに, 左から 'B' が連続している個数を数えてそれをそれぞれ出力すれば良い. .
ソース
#include<bits/stdc++.h> using namespace std; int main() { int N; string S; cin >> N; cin >> S; int ret = 0; vector< int > ans; for(char& s : S) { if(s == 'B') { ++ret; } else if(ret > 0) { ans.push_back(ret); ret = 0; } } if(ret > 0) { ans.push_back(ret); } cout << ans.size() << endl; for(int& val : ans) cout << val << " "; }
B. Passwords
問題概要
個のパスワードの候補となる文字列と, 正しいパスワードを示す文字列が与えられる.
パスワードを忘れてしまったので, 個のパスワードを総当りする. パスワードの文字列長が小さい順に試し, 同じ文字列長のパスワードは順不同である.
個のパスワードを試すのに 秒かかる. 回連続して間違えると 秒間は操作できない.
正しいパスワードを入力するまでの最小値と最大値を求めよ.
解法
ちょっとReadingが難しい...
最小値となる場合は, (正しいパスワードの長さ未満の文字列の個数) + 1 個を試すとき. 最大値となる場合は, (正しいパスワードの長さ以下の文字列の個数) 個を試すとき.
正解するまでに試すパスワードの個数を とすると, 操作できなくなる回数は 回.
あとはそれをそのまま出力するだけ.
ソース
#include<bits/stdc++.h> using namespace std; int score(int N, int K) { return((N - 1) / K * 5 + N); } int main() { int N, K; string S[101], T; int length[101] = {}; cin >> N >> K; for(int i = 0; i < N; ++i) { cin >> S[i]; ++length[S[i].size()]; } cin >> T; int sum = accumulate(length, length + T.size(), 0); cout << score(sum + 1, K) << " " << score(sum + length[T.size()], K) << endl; }
C. Journey
問題概要
個の街があってそれぞれ から の番号が振られている. また 本の有向の道路があって, 街 から街 へ時間 かけて通れることを意味する. また道路でループを形成することはない.
時間 に間に合うように街 から街 へ移動する.
このとき最大で何個の街を訪れることができるか求め, そのときの街の番号と共に出力せよ.
解法
トポロジカルソート + 動的計画法 + 経路復元.
ループがないのでこれはDAG. DAG なのでトポロジカルソートすればいい感じの更新順序が得られるので, トポロジカルソートしておく.
街 から に 個の街を通って訪れるときの最短時間 とすれば, これは自明なDPができる. 街 から出ている辺の先と自分 で最小を取っていけば良い. .
経路復元はdpの更新時に前の街を保存しておいて面倒だけど頑張る. どうでもいいけど逆辺にして から への移動するときを考えると微妙に楽?
ソース
適当にやったらMLEした.
#include<bits/stdc++.h> using namespace std; const int INF = 1 << 30; struct edge { int to, cost; }; vector< edge > graph[5003]; int dp[5003][5003], rev[5003][5003]; vector< int > order; bool used[5003]; void dfs(int idx) { if(used[idx]++) return; for(auto& e : graph[idx]) dfs(e.to); order.push_back(idx); } int main() { int N, M, T; cin >> N >> M >> T; while(M--) { int A, B, C; cin >> A >> B >> C; graph[--B].push_back((edge) {--A, C}); } for(int i = 0; i < N; i++) dfs(i); reverse(begin(order), end(order)); fill_n(*dp, 5003 * 5003, INF); dp[N - 1][0] = 0; for(int _ = 0; _ < N; _++) { int i = order[_]; for(int j = 0; j < N; j++) { for(edge& e : graph[i]) { if(dp[e.to][j + 1] > dp[i][j] + e.cost) { dp[e.to][j + 1] = dp[i][j] + e.cost; rev[e.to][j + 1] = i; } } } } int curr = N; while(dp[0][curr] > T) --curr; cout << curr + 1 << endl; vector< int > now; int pos = 0; for(int i = curr; i >= 0; i--) { cout << pos + 1 << " "; pos = rev[pos][i]; } }
D. Maxim and Array
問題概要
長さ の数列 が与えられる.
回まで任意の要素を選んでその要素を 増減させる操作ができる.
このとき を最小化したときの数列 を出力せよ.
解法
の符号を負にすることを考える.
が奇数個のときはもともと負なので偶数個のときを考える. このときなるべく少ない回数で符号を反転させたいので, 絶対値が最小の要素の符号を反転させるように努力するのが最適.
符号を負にできたら, すべての を絶対値として見たときの積の最大化である. の間 なので, が最小の要素に を加えることを繰り返すのが最適である. が最小の要素は優先度付きキューをつかって効率的にもとめることができる.
コーナーケースとして があるものがあるけど, このアルゴリズムなら を あるいは と見立ててあげれば同様に成立する.
計算量は .
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; typedef pair< int64, int > Pi; int main() { int N, K, X; int64 A[200000]; bool sign = true; priority_queue< Pi, vector< Pi >, greater< Pi > > que; scanf("%d %d %d", &N, &K, &X); for(int i = 0; i < N; i++) { scanf("%lld", &A[i]); que.emplace(max(A[i], -A[i]), i); sign ^= A[i] < 0; } while(K--) { auto p = que.top(); que.pop(); if(A[p.second] < 0) sign ^= 1; if(sign) A[p.second] -= X; else A[p.second] += X; if(A[p.second] < 0) sign ^= 1; que.emplace(max(A[p.second], -A[p.second]), p.second); } for(int i = 0; i < N; i++) { printf("%lld ", A[i]); } }