AtCoder Beginner Contest 073
そろそろBiginnerをBigginerと入力してしまうのやめたいね
([追記]9/10 2:59 Biginnerですらなくて、Beginnerなので修正しました)
A - September 9
問題
2桁の整数が与えられるので、にが含まれるか答えてください。
解法
問題文を読むと、お腹が痛いのでトイレに行った方がいいことがわかる。
こういうのは string でやった方が楽だと知っているので(2桁で固定だからね)
コード
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; if (s[0] == '9' || s[1] == '9') cout << "Yes" << endl; else cout << "No" << endl; }
問題文の下にある提出フォームで書いてコンパイルもせずに出した 通ったのでよかったね(49sec)
B - Theater
問題
100,000個の席がある。人の団体客がやってきて、番目の人々は番目から番目までの連続した席に座った。
合計で何人座ったか。
解法
そろそろお腹が痛いことに気がつける。
問題文をよく読むと、同じ席に座ることはないことがわかるので(それはそう ああそれはそう それはそう)、それぞれの団体客は何人なのかは みたいな感じで簡単にもとまる。(閉区間の気持ちになりましょう)
コード
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int ans = 0; for (int i = 0; i < n; ++i) { int l, r; cin >> l >> r; ans += (r - l + 1); } cout << ans << endl; }
これも自分を信じて提出フォーム直書きをするといいです(よくはないです)
C - Write and Erase
問題
数列が与えられるので、奇数回出現した数がいくつあるかを求めなさい。
解法
進研ゼミでみた!となれるかがポイント
数列に出てくる数字は明らかに巨大なので、これを配列の添え字に使うみたいな解法は明らかに悪手です
方針はいくつかあって、
- その辺に落ちている平衡二分探索木に投げる
- sortして前から順番に同じ数字がいくつあるか見ていく
みたいなのがあると思います。
ぼくは平衡二分探索木に投げつけました
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; map<int, int> m; for (int i = 0; i < n; ++i) { int a; cin >> a; m[a]++; } int ans = 0; for (auto i : m) { ans += i.second % 2; } cout << ans << endl; }
フォームで書いたら17行目に"ans += m.second % 2"とか書いていてコンパイルエラーを出しました(小声)
D - joisino's travel
問題
辺頂点の連結なグラフが与えられます。
番目の頂点全てを通る経路で最短のものを求めてください。
解法
ワーシャルさんとフロイドさんとセールスマンが見える気がする。
この方針だと明らかに400じゃないヤバになるけどとりあえず早く終えたい一心で実装した。
始点は全探索して決め打ち、これで
そこからbitDP(巡回セールスマン問題)で全てを通る最短経路を見つけるといいことがわかる。このパートは合計で
あとはの各頂点間の最短経路がほしいので、あらかじめWarshall-Floyd法( )か始点を全探索してからのDijkstra( *1 )をしておいておわり。全部で 。多分。
今回のRの制約はと小さいので、†next_permutation†で順番を全探索しても全く問題ない(ことに後になって気がついた。)
コード
最初の方針 Warshall-Floyd法 + bitDP
#include <bits/stdc++.h> using namespace std; vector<vector<int>> d(202, vector<int>(202, 1001001001)); vector<int> r; int dp[10][1010]; int dfs(int v, int bit) { int &res = dp[v][bit]; if (~res) return res; res = 1001001001; for (int i = 0; i < r.size(); ++i) { if ((bit >> i) & 1) continue; res = min(res, dfs(i, bit + (1 << i)) + d[r[v]][r[i]]); } if (res == 1001001001) res = 0; return res; } int solve() { int ans = 1001001001; for (int i = 0; i < r.size(); ++i) { memset(dp, -1, sizeof(dp)); ans = min(ans, dfs(i, (1 << i))); } return ans; } int main() { int n, m, e; cin >> n >> m >> e; for (int i = 0; i < e; ++i) { int a; cin >> a; r.push_back(a - 1); } for (int i = 0; i < m; ++i) { int u, v, c; cin >> u >> v >> c; u--; v--; d[u][v] = c; d[v][u] = c; } for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); cout << solve() << endl; }
さすがにこの重さをフォームで書くのは無謀です
Warshall-Floyd法 + next_permuation
#include <bits/stdc++.h> using namespace std; inline int in() { int x; cin >> x; return x; } const int inf = 1001001001; int main() { int n, m, R; cin >> n >> m >> R; vector<int> r(R); for (auto &i : r) i = in() - 1; vector<vector<int>> d(n, vector<int>(n, inf)); for (int i = 0; i < m; ++i) { int u = in() - 1, v = in() - 1, c = in(); d[u][v] = d[v][u] = c; } for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } int ans = inf; sort(r.begin(), r.end()); do { int sum = 0; for (int i = 1; i < R; ++i) { sum += d[r[i - 1]][r[i]]; } ans = min(ans, sum); } while (next_permutation(r.begin(), r.end())); cout << ans << endl; }
*1:?