■考えたこと
制約的に何歩で(X,Y)に行けるかを愚直に
シミュレーションする方針で解けると推測。
ACしたコードは下記。
using ll = long long; int main() { int r, x, y; cin >> r >> x >> y; ll l = (ll)x * x + (ll)y * y; ll r2 = (ll)r * r; ll ans = 1; while (r2 * ans * ans < l) ans++; if (ans == 1) { if (r2 * ans * ans > l) ans++; } cout << ans << endl; }
■考えたこと
制約的に全探索と思った。
再帰で実装した。
ACしたコードは下記。
struct Edge { int to; ll cost; Edge(int to, ll cost) : to(to), cost(cost){} }; int main() { int n, m; cin >> n >> m; vector<vector<Edge>> g(n); for (int i = 0; i < m; i++) { int a, b; ll c; cin >> a >> b >> c; --a; --b; g[a].push_back(Edge(b, c)); g[b].push_back(Edge(a, c)); } vector<bool> visited(n); ll ans = 0; auto dfs = [&](auto dfs, int v, ll c) -> void { visited[v] = true; ans = max(ans, c); for (auto nv : g[v]) { if (visited[nv.to]) continue; dfs(dfs, nv.to, c + nv.cost); } visited[v] = false; }; for (int i = 0; i < n; i++) { dfs(dfs, i, 0); } cout << ans << endl; }
■考えたこと
y座標が同じ座標ごとにまとめれば見通しが良くなる。
まとめ後はx座標とR/Lのペアでデータを持ち、昇順でソートしてRLのペアが
存在するか判定すればOK。
ACしたコードは下記。
int main() { int n; cin >> n; vector<int> x(n), y(n); for (int i = 0; i < n; i++) cin >> x[i] >> y[i]; string s; cin >> s; map<int, vector<pair<int, char>>> mp; for (int i = 0; i < n; i++) { mp[y[i]].push_back(make_pair(x[i], s[i])); } for (auto e : mp) { auto ps = e.second; sort(ps.begin(), ps.end()); for (int i = 0; i < ps.size() - 1; i++) { if (ps[i].second == 'R' && ps[i + 1].second == 'L') { cout << "Yes" << endl; return 0; } } } cout << "No" << endl; }
■考えたこと
全探索をすると計算量O(HWN) = O(125 x 10^6)であり間に合うか心配だったが
この方針で実装してACした。
ACしたコードは下記。
int main() { int h, w, n; cin >> h >> w >> n; string t; cin >> t; vector<string> s(h); for (int i = 0; i < h; i++) cin >> s[i]; int ans = 0; for (int hi = 0; hi < h; hi++) { for (int wj = 0; wj < w; wj++) { if (s[hi][wj] != '.') continue; int i = hi, j = wj; bool ok = true; for (int v = 0; v < n; v++) { if (t[v] == 'L') j -= 1; if (t[v] == 'R') j += 1; if (t[v] == 'U') i -= 1; if (t[v] == 'D') i += 1; if (i < 0 || i > h || j < 0 || j > w) ok = false; if (s[i][j] != '.') ok = false; if (!ok) break; } if (ok) ans++; } } cout << ans << endl; }
■考えたこと
dpのような気がしたので入力例1の値で以下の表を書いてみた。
| 9 | 1 |
| 8 | 6 |
| 3 | 2 |
| 7 | 9 |
| 2 | 5 |
| i \ j | 0 | 1 |
|---|---|---|
| 0 | true | true |
| 1 | true | true |
| 2 | true | true |
| 3 | true | false |
| 4 | false | true |
dpの定義は以下。
dp[i][j] = A[i][j]が条件を満たすかどうか。
dp[0][0] = dp[0][1] = true
dp[n - 1][0] または dp[n - 1][1] がtrueならYes。
以下はACしたコード。
int main() { int n, k; cin >> n >> k; vector<vector<int>> a(n, vector<int>(2)); for (int i = 0; i < n; i++) cin >> a[i][0]; for (int i = 0; i < n; i++) cin >> a[i][1]; vector<vector<bool>> dp(n, vector<bool>(2, false)); dp[0][0] = dp[0][1] = true; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < 2; j++) { if (!dp[i][j]) continue; for (int l = 0; l < 2; l++) { if (abs(a[i + 1][l] - a[i][j]) <= k) { dp[i + 1][l] = true; } } } } for (int j = 0; j < 2; j++) { if (dp[n - 1][j]) { cout << "Yes" << endl; return 0; } } cout << "No" << endl; }
■考えたこと
問題文を読んでも解法が思いつかなかった。
とりあえず入力例1で周遊パスを買っていったときの様子を紙に書いてみた。
1日周遊パスは2枚セットで10円で販売されているので各セット購入したとすると
・0セット：7 + 1 + 6 + 3 + 6 = 23円
・1セット：(10 x 1) + (0 + 1 + 0 + 3 + 6) = 20円 ← 料金が高い日順に周遊パスを割り当て
・2セット：(10 x 2) + (0 + 1 + 0 + 0 + 0) = 21円
・3セット：(10 x 3) + (0 + 0 + 0 + 0 + 0) = 30円
となる。
ここまで書き出すと3セット以降は料金が高くなっていくだけなので
試す必要がないことが分かった。
つまり5日間すべてを周遊パスで割り当てするためには3セットで十分。
これは N / D の切り上げ (以降k) で計算できる。
制約的にkセット試せば間に合うと推測。
後はkセット購入した場合の合計料金をどう計算するかだが、下記を書いて
累積和でいけそうと推測。
f : 1 3 6 6 7
s : 0 1 4 10 16 23
以下はACしたコード。
using ll = long long; int main() { int n, d, p; cin >> n >> d >> p; vector f(n); for (int i = 0; i < n; i++) cin >> f[i]; sort(f.begin(), f.end()); vector s(n + 1); for (int i = 0; i < n; i++) { s[i + 1] = s[i] + f[i]; } int sd = (n + d - 1) / d; const ll INF = 1e18; ll ans = INF; for (ll i = 0; i <= sd; i++) { ll sum = 0; if (n - i * d > 0) sum += s[n - i * d]; sum += p * i; ans = min(ans, sum); } cout << ans << endl; }
■考えたこと
蟻本のLake Counting (POJ No.2386) と同じ問題。
とりあえずdfsで連結しているセンサーをなめていき
(訪れたセンサーはtrueにしておく) 再帰終了後、カウントを足すという方針で解いた。
ACしたコードは下記。
const int di[] = { 1, 0, -1, 0, 1, 1, -1, -1 }; const int dj[] = { 0, 1, 0, -1, 1, -1, 1, -1 }; int main() { int h, w; cin >> h >> w; vector<string> s(h); for (int i = 0; i < h; i++) cin >> s[i]; vector<vector<bool>> visited(h, vector<bool>(w)); auto dfs = [&](auto dfs, int i, int j) -> void { visited[i][j] = true; for (int v = 0; v < 8; v++) { int ni = i + di[v]; int nj = j + dj[v]; if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue; if (visited[ni][nj]) continue; if (s[ni][nj] != '#') continue; dfs(dfs, ni, nj); } }; int ans = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (s[i][j] != '#') continue; if (visited[i][j]) continue; dfs(dfs, i, j); ans++; } } cout << ans << endl; }
