Codeforces Round #192 (Div. 1)
Unusual Round と謳っていたので怖かったですが, 参加してみると楽しかったです.
Result : oox.. 240th 1753 -> 1804
C が解けそうでC から考えているとB の得点がモリモリ減ってしまったので, 今はまだ低い得点の問題から素早く解いたほうがよさそうです.
A. Purification
問題概要 : $n \times n $ のグリッドがあり, 全てのマスは最初呪われている.
あるマスが強く呪われていなければ(=マスの値が'.'ならば), そのマスが含まれる行・列を浄化できる.
あるマスを一度浄化したらそのマスはずっと浄化された状態が保たれる.
このとき, すべてのマスを浄化するのに必要な最小手順と, 浄化するマスを答えよ. (複数ある場合はどれか1 つ, できない場合は-1)
解法 : すべてのマスを浄化しないといけないから, 1 行または1 列すべてを浄化することでこれは満たされる. $i$ 行と$j$ 列がすべて強く呪われている時は, マス($i$, $j$) をどうやっても浄化できないので, -1 を出力する.
コード :
#include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <set> #include <map> using namespace std; typedef long long lint; char mp[256][256]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%s", &mp[i]); bool row = 0, col = 0; for (int i = 0; i < n; i++){ bool rF = 1, cF = 1; for (int j = 0; j < n; j++){ if (mp[i][j] == '.') cF = 0; if (mp[j][i] == '.') rF = 0; } if (rF) row = true; if (cF) col = true; } if (row && col) return (!printf("-1\n")); if (!col){ for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (mp[i][j] == '.'){ printf("%d %d\n", i + 1, j + 1); break; } } } } else { for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (mp[j][i] == '.'){ printf("%d %d\n", j + 1, i + 1); break; } } } } return (0); }
問題概要 : $r \times c $ のグリッドに自分と自分以外の人がいる.
ゴールが与えられるので, ゴールに行くまでに自分以外の人にあう人数を最小化せよ.
ただし, 自分以外の人は自分の行動をみて, 自分と会えるように最適に行動する.
解法 : 自分以外の人の最適な戦略は, 途中で会うことを気にせずにゴールで自分を待ちぶせすることである.
そこで, 自分のゴールからの距離$d$ よりゴールからの距離が小さい人は全員会うことになる.
コード :
#include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <set> #include <map> using namespace std; typedef long long lint; char mp[1024][1024]; int w, h; int sy, sx, gy, gx; int c[1024][1024]; int dy[] = {1, 0, -1, 0}, dx[] = {0, 1, 0, -1}; void bfs() { for (int i = 0; i < 1024; i++) for (int j = 0; j < 1024; j++) c[i][j] = 1000000000; queue<pair<int, pair<int, int> > > q; for (q.push(make_pair(0, make_pair(sy, sx))); q.size(); ){ pair<int, pair<int, int> > x = q.front(); q.pop(); if (c[x.second.first][x.second.second] <= x.first) continue; c[x.second.first][x.second.second] = x.first; for (int i = 0; i < 4; i++){ int ny = x.second.first + dy[i], nx = x.second.second + dx[i]; if (0 <= nx && nx < w && 0 <= ny && ny < h && mp[ny][nx] != 'T') q.push(make_pair(x.first + 1, make_pair(ny, nx))); } } } int main() { scanf("%d %d", &h, &w); for (int i = 0; i < h; i++){ scanf("%s", &mp[i]); for (int j = 0; j < w; j++){ if (mp[i][j] == 'E'){ sx = j; sy = i; } else if (mp[i][j] == 'S'){ gx = j; gy = i; } } } bfs(); int ans = 0; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) ans += (mp[i][j] - '0') * ('0' <= mp[i][j] && mp[i][j] <= '9' && c[i][j] <= c[gy][gx]); printf("%d\n", ans); return (0); }
問題概要 : $n$ 頂点$m $ 辺のグラフが与えられ, このグラフは次の制約を満たす.
- 各頂点の次数は$2$ 以下である
- 二重辺, 自己ループは存在しない
この条件を満たし, 最初に与えたグラフと辺を共有しないグラフがあればそれを出力せよ. なければ-1 を出力せよ.
解法 : まず, この条件を満たす簡単なグラフの例として, 輪っか(大きさ$m $ のサイクル)がある. そこで, $n$ 個の頂点を適当に並べた$n$ 個の辺からなる輪っかを考えると, そのうち$m $ 個以上の辺が元のグラフで使われていない確率は, 十分大きい$n$に対して $\left( 1-\dfrac{m}{_n\text{C}_2} \right ) \left( 1-\dfrac{m}{_n\text{C}_2 - 1} \right ) \left( 1-\dfrac{m}{_n\text{C}_2 - 2} \right ) \cdots \left( 1-\dfrac{m}{_n\text{C}_2 - m + 1} \right ) \approx \left( 1-\dfrac{m}{_n\text{C}_2} \right )^m $ となる.
ここで, $m > _n \text{C} _2$ となるような$m $ や, 小さい$n, m $ の組み合わせに対してグラフを作り直せないことが分かる. $n \leqq 9$ の場合はすべての輪っかの並び順を試せるので, $O(n! \times n)$ 程度の時間で厳密に調べても良いだろう.
また, もっとも最悪のケースとして考えられる$m=n$ のとき,
$ \left( 1-\dfrac{m}{_n\text{C}_2} \right )^m = \left( 1-\dfrac{n}{_n\text{C}_2} \right )^n = \left( 1-\dfrac{2}{n - 1} \right )^n = \dfrac{1}{e^2} (n \to \infty)$
ということが一般に知られているので, 十分大きい$n$ に対しても適当な輪っかを4 ~ 5 回つくる間に答えが求まり, 計算量は$O(n \log n)$ 程度となる.
コード :
#include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <vector> #include <ctime> using namespace std; typedef long long lint; set<pair<int, int> > used; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++){ int a, b; scanf("%d %d", &a, &b); used.insert(make_pair(a, b)); used.insert(make_pair(b, a)); } vector<int> v; for (int i = 1; i <= n; i++) v.push_back(i); clock_t s = clock(); while (double(clock() - s) / CLOCKS_PER_SEC <= 2.8){ random_shuffle(v.begin(), v.end()); vector<pair<int, int> > ans; for (int i = 0; i < n; i++){ if (used.find(make_pair(v[i], v[(i + 1) % n])) == used.end()) ans.push_back(make_pair(v[i], v[(i + 1) % n])); if (ans.size() == m){ for (int j = 0; j < m; j++) printf("%d %d\n", ans[j].first, ans[j].second); return (0); } } } printf("-1\n"); return (0); }
