code festival 2014 上海
id math で出ていました． 5位で表彰された，やったぜ．
コンテストページ : http://code-festival-2014-china.contest.atcoder.jp/
A問題
難しい訳ではないんだけど，Aにしては実装が重い
http://code-festival-2014-china.contest.atcoder.jp/submissions/305593
#define _USE_MATH_DEFINES #define _CRT_SECURE_NO_DEPRECATE #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <climits> #include <cfloat> #include <ctime> #include <cassert> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <numeric> #include <list> #include <iomanip> #include <fstream> #include <iterator> #include <bitset> using namespace std; typedef long long ll; typedef pair<int, int> Pii; typedef pair<ll, ll> Pll; #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)(c).size()) #define ten(x) ((int)1e##x) template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } int main(){ int n; cin >> n; int _n = n; int x = 1; while (_n--) x *= 10; vector<string> vs; FOR(i, x) { string s; int y = i; FOR(j, n) { int cur = y % 10; int upper = y / 10 % 2; if (upper) cur = 9 - cur; s.push_back('0' + cur); y /= 10; } reverse(s.begin(), s.end()); vs.push_back(s); } printf("%d\n", sz(vs) - 1); for (auto& a : vs) { printf("%s\n", a.c_str()); } }
テンプレート部分は以降省略します
B問題
二分探索して|x|+|y|を求めて，後は辻褄を合わせる問題．
http://code-festival-2014-china.contest.atcoder.jp/submissions/305674
int q; ll abs_sum(ll n) { ll l = -1, r = ten(9); while (r - l != 1) { ll md = (l + r) / 2; ll val = md * (md + 1) * 2 + 1; if (n <= val) r = md; else l = md; } return r; } int main(){ cin >> q; FOR(i, q) { ll n; cin >> n; ll abs_xy = abs_sum(n); n -= 1 + abs_xy * (abs_xy - 1) * 2; n--; ll x = (n + 1) / 2 - abs_xy; ll y = abs_xy - abs(x); if (n % 2 == 1) y = -y; cout << x << " " << y << endl; } }
C問題
正多角形の頂点が全て格子点上にあるようなものの中で，最も頂点数の多い多角形を出力する問題． ぱっと見，正方形しかなさそうだったので"格子点 多角形"で検索して，wikipediaを見て確信する．
正方形となるような辺は，x,y軸に平行が，45度傾いている物と思い込んでいて2WAした．
http://code-festival-2014-china.contest.atcoder.jp/submissions/306262
typedef pair<Pll, int> P; int main(){ int n; cin >> n; vector<P> vp; FOR(i, n) { Pll p; cin >> p.first >> p.second; vp.emplace_back(p,i+1); } map<Pll,int> st; FOR(i, n) st[vp[i].first] = vp[i].second; vector<int> anses; FOR(i, sz(vp)) { for (int j = i + 1; j < sz(vp); j++) { Pll& p = vp[i].first; Pll& q = vp[j].first; ll xdiff = p.first - q.first; ll ydiff = p.second - q.second; Pll r(p.first - ydiff, p.second + xdiff); Pll s(q.first - ydiff, q.second + xdiff); if (st.count(r) && st.count(s)) { anses.push_back(st[p]); anses.push_back(st[q]); anses.push_back(st[r]); anses.push_back(st[s]); } if (sz(anses)) break; } if (sz(anses)) break; } cout << sz(anses) << endl; sort(anses.begin(), anses.end()); for (auto i : anses) cout << i << endl; }
D問題
どう見てもフローにしか見えなかった，後で聞くとbfsすると解けたらしいが思いつかなかった．
フローを2本流して，経路復元をする方法で解ける．解いている人はフローが多そう？
http://code-festival-2014-china.contest.atcoder.jp/submissions/306143
struct Edge { int cap; // capacity int to; int rev; // reverse edge id Edge() {} Edge(int c, int t, int r) : cap(c), to(t), rev(r) { } }; struct CostEdge : public Edge { int cost; CostEdge() : Edge() {} CostEdge(int c, int t, int cs, int r) : Edge(c, t, r), cost(cs) { } }; template<class E> // Edge type class Graph { public: typedef std::vector<std::vector<E> > G; private: G g; public: Graph(int n) : g(G(n)) {} void addEdge(int from, int to, int cap, int cost) { g[from].push_back(E(cap, to, cost, g[to].size())); g[to].push_back(E(0, from, -cost, g[from].size() - 1)); //rev edge } G &getRowGraph() { return g; } }; // O(VE+FElogV) template<class E> int minCostFlow(Graph<E> &graph, int s, int t, int f, bool negative = false) { typedef pair<int, int> P; typename Graph<E>::G &g = graph.getRowGraph(); int n = g.size(); int res = 0; vector<int> h(n, 0); vector<int> prevv(n); vector<int> preve(n); const int inf = 10000000; //check //負の辺に対応？ if (negative) { vector<int> dist(n, inf); dist[s] = 0; bool update = true; while (update) { update = false; for (int v = 0; v < n; v++) { if (dist[v] == inf) continue; for (int i = 0; i < (int)g[v].size(); i++) { E &e = g[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; prevv[e.to] = v; preve[e.to] = i; update = true; } } } } for (int i = 0; i < n; i++) h[i] = dist[i]; } while (f > 0) { //ダイクストラで最短経路(cost = 辺の費用) priority_queue<P, vector<P>, greater<P> > que; vector<int> dist(n, inf); dist[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (dist[v] < p.first) continue; for (int i = 0; i < (int)g[v].size(); i++) { E &e = g[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; que.push(P(dist[e.to], e.to)); } } } if (dist[t] == inf) { return -1; //最短経路なし } for (int v = 0; v < n; v++) h[v] += dist[v]; //s-t間に目一杯流す int d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, g[prevv[v]][preve[v]].cap); } f -= d;//流した分を引く res += d * h[t]; //流した分からコストの計算をする //逆辺の計算 for (int v = t; v != s; v = prevv[v]) { E &e = g[prevv[v]][preve[v]]; e.cap -= d; g[v][e.rev].cap += d; } } return res; } #define ID(a,b) (a*w+b) char board[50][51]; int main(){ int h, w; cin >> h >> w; FOR(i, h) cin >> board[i]; const int n = 2 + 2 * h*w; int a, b, s; FOR(i, h) FOR(j, w) { if (board[i][j] == 'A') a = ID(i, j); if (board[i][j] == 'B') b = ID(i, j); if (board[i][j] == 'S') s = ID(i, j); } Graph<CostEdge> g(n); FOR(i, h) FOR(j, w) { if (board[i][j] == '#') continue; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; int id = ID(i, j); FOR(k, 4) { int ni = i + dx[k]; int nj = j + dy[k]; if (0 <= ni && ni < h && 0 <= nj && nj < w && board[ni][nj] != '#') { int nid = ID(ni, nj); g.addEdge(id * 2 + 1, nid * 2, 1,1); } } } FOR(i, h) FOR(j, w) { if (board[i][j] == '#') continue; int id = ID(i, j); int cap = (id == s) ? 2 : 1; g.addEdge(id * 2, id * 2 + 1 , cap, 0); } const int src = n - 2, dst = n - 1; g.addEdge(src, s * 2, 2, 0); auto g2 = g; g2.addEdge(a * 2 + 1, dst, 1 , 0); int s2a = minCostFlow(g2, src, dst, 1); auto g3 = g; g3.addEdge(b * 2 + 1, dst, 1 , 0); int s2b = minCostFlow(g3, src, dst, 1); g.addEdge(a * 2 + 1, dst, 1, 0); g.addEdge(b * 2 + 1, dst, 1, 0); int s2ab = minCostFlow(g, src, dst, 2); if (s2ab != s2a + s2b) { puts("NA"); } else { { int cur = 2 * a; auto rG = g.getRowGraph(); while (cur != 2 * s) { for (auto e : rG[cur]) { if (e.cost == -1 && e.cap == 1) { int from = e.to; cur = from - 1; int i = cur / 2 / w; int j = cur / 2 % w; board[i][j] = 'a'; //fprintf(stderr,"%d %d\n",i,j); break; } } } } { int cur = 2 * b; auto rG = g.getRowGraph(); while (cur != 2 * s) { for (auto e : rG[cur]) { if (e.cost == -1 && e.cap == 1) { int from = e.to; cur = from - 1; int i = cur / 2 / w; int j = cur / 2 % w; //fprintf(stderr, "%d %d\n", i, j); board[i][j] = 'b'; break; } } } } board[s / w][s%w] = 'S'; FOR(i, h) puts(board[i]); } }
E問題
条件付き期待値の式を立てて，ゲームの結果をメモ化再帰する． 1回で3~4回ゲームが出来るので，状態数をn3持って計算したいけれど，その場合計算量が n3 43 = 81 n3 くらいになって間に合わない様子，その上実装が面倒くさい． そこで1ゲーム毎に状態を持つようにする．すると状態数がn3 * 4 ，計算量がn3 * 4 * 3 = 12 *n3 になり，高速でかつ実装も楽に．
実装する時にはTLEを重要視せず実装量を重視して書いたが，定数倍に気をつけないとだめだったらしい．
http://code-festival-2014-china.contest.atcoder.jp/submissions/306554
double p[3]; double tbl[101][101][101][4]; double dfs(int p1, int p2, int p3,int game) { if (tbl[p1][p2][p3][game] >= 0) { return tbl[p1][p2][p3][game]; } double ret = 1e300; bool first_stage = (game == 0); // 初回 if (p1 > 0) { int ngame = game + 1; if (ngame >= 3) ngame = 0; //extraはないので double suc = dfs(p1 - 1, p2, p3, ngame); double ans; if (first_stage) { if (p[0] == 1.0) ans = 1 + suc; else ans = (1 + suc * p[0]) / p[0]; } else { double fil = dfs(p1, p2, p3, 0); ans = suc * p[0] + fil * (1 - p[0]); } ret = min(ret, ans); } if (p2 > 0) { int ngame = game + 1; if (ngame >= 4) ngame = 0; //extraあり！ double suc = dfs(p1, p2 - 1, p3, ngame); double ans; if (first_stage) { if (p[1] == 1.0) ans = 1 + suc; else ans = (1 + suc * p[1]) / p[1]; } else { double fil = dfs(p1, p2, p3, 0); ans = suc * p[1] + fil * (1 - p[1]); } ret = min(ret, ans); } if (p3 > 0) { int ngame = game + 1; if (ngame >= 4) ngame = 0; //extraあり！ double suc = dfs(p1, p2, p3 - 1, ngame); double ans; if (first_stage) { if (p[2] == 1.0) ans = 1 + suc; else ans = (1 + suc * p[2]) / p[2]; } else { double fil = dfs(p1, p2, p3, 0); ans = suc * p[2] + fil * (1 - p[2]); } ret = min(ret, ans); } return tbl[p1][p2][p3][game] = ret; } int main() { int n[3]; FOR(i, 3) cin >> n[i]; FOR(i, 3) cin >> p[i]; FOR(i,3) p[i] /= 100; FOR(p0, 101) { FOR(p1, 101) { FOR(p2, 101) { FOR(i, 4) { tbl[p0][p1][p2][i] = -1; } } } } FOR(i,4) tbl[0][0][0][i] = 0; double ans = dfs(n[0], n[1], n[2], 0); printf("%.15lf\n", ans); }
F問題
実は累積の積を持っておけば焼き肉が"生焼け","丁度","焼き過ぎ"になる確率を計算出来る．
時間sに網に置かれて，時間t-1の時点でもまだ網に残っている確率を求めたい． これが求められれば，上記の3つの確率が求められる．
時刻 s < a <= t-1 で，この肉が取られる確率は， 1 / {時刻aにおける肉の数} である． よって，t-1 でも肉が残っている確率は， 1 - 1 / {時刻aにおける肉の数} を s < a <= t-1 で掛けあわせたものになる．
ところで，素直に累積するとオーバーフローが怖かったので，segment treeを使って必要な部分だけを計算した．
class seg_tree { public: vector<double> dat; int n; void init(double *d, int size) { n = 1; while (n < size) n <<= 1; dat.resize(2 * n - 1); fill(dat.begin(), dat.end(), 0); for (int i = 0; i < size; i++) dat[n - 1 + i] = d[i]; for (int i = n - 2; i >= 0; i--) propagate(i); } void propagate(int i) { dat[i] = dat[i * 2 + 1] * dat[i * 2 + 2]; } //k番目(0-indexed)をvalに更新 void update(int k, int val) { k += n - 1; dat[k] = val; while (k > 0) { k = (k - 1) / 2; propagate(k); } } //[a,b)において求めたい値を得る double query(int a, int b) { return query(a, b, 0, 0, n); } //[a,b)において求めたい値を得る // k = 現在見ている接点の番号 // [l,r)はkに対応した範囲 double query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return 1.0; //範囲外 if (a <= l && r <= b) return dat[k]; //[l,r) ⊂ [a,b) //[l,r)の一部が[a,b)に含まれる int md = (l + r) / 2; //[l,md),[md,r) int nl = k * 2 + 1, nr = nl + 1; //子の接点 double lval = query(a, b, nl, l, md); double rval = query(a, b, nr, md, r); return lval * rval; //calc } }; int n; int s[ten(5)], t[ten(5)]; int main() { cin >> n; FOR(i, n) cin >> s[i] >> t[i]; vector<int> comp; FOR(i, n) comp.push_back(s[i]), comp.push_back(t[i]); sort(comp.begin(), comp.end()); FOR(i, n) { s[i] = lower_bound(comp.begin(), comp.end(), s[i]) - comp.begin(); t[i] = lower_bound(comp.begin(), comp.end(), t[i]) - comp.begin(); } vector<Pii> ev; FOR(i, n) ev.push_back(Pii(s[i], 1)); FOR(i, n) ev.push_back(Pii(t[i], -1)); sort(ev.begin(), ev.end()); int meet = 0; vector<int> order; vector<double> db; for (auto e : ev) { if (e.second == 1) { order.push_back(e.first); db.push_back(1.0); // rem } else { //took db.push_back(1.0 - 1.0 / meet); // rem } meet += e.second; } seg_tree sg; sg.init(&db[0], sz(db)); FOR(i, n) { double q = sg.query(s[i], t[i]); double prev = 1.0 - q; double rem = q * db[t[i]]; printf("%.10lf %.10lf\n",prev, rem); } }
スイーツ
@__math 上海で負けた方がスイーツしたくないですか
— ドイツ語は消えろ (@yosupot) 2014, 12月 9@yosupot ええでｗ
— まーす (@__math) 2014, 12月 9@__math やったぜw
— ドイツ語は消えろ (@yosupot) 2014, 12月 9そういえばまーすに負けました。スイーツです。
— ドイツ語は消えろ (@yosupot) 2014, 12月 21よすぽでスイーツ pic.twitter.com/twcmL9C1vi
— まーす (@__math) 2014, 12月 21