TCO14 Round2A
この記事を書いてる時に1Bの記事が事故死してしまった…。まぁいいか。
- -
250. SixteenBricks
問題：1*1*h[i]の角柱を4×4のグリッドに並べた時の最大表面積を求める問題。
- greedyかなぁと思ったけどsample2が倒せなかった。
- 安全にbitDPとか出来ないかなと思ったけど、思いつかず。
- Challengeで人のコードを見たら、そりゃそうか、という感じだった。
- 以下は、本番後にbitDPしてみたコード。この解法好きです。
class SixteenBricks { private: int bitCount(int t){ int res = 0; for(int i=t;i;i&=i-1) res++; return res; } int additionalScore(int mask, int pos, int h){ int res = 0; int x = pos/4, y = pos%4; if(x > 0 && (mask&(1<<(pos-4)))) res -= h; else res += h; if(x < 3 && (mask&(1<<(pos+4)))) res -= h; else res += h; if(y > 0 && (mask&(1<<(pos-1)))) res -= h; else res += h; if(y < 3 && (mask&(1<<(pos+1)))) res -= h; else res += h; return res; } public: int maximumSurface(vector <int> height){ static int dp[1<<16]; memset(dp, 0, sizeof(dp)); dp[0] = 16; sort(height.rbegin(), height.rend()); for(int i=0;i<(1<<16)-1;i++){ int idx = bitCount(i); for(int j=0;j<16;j++){ if(i&(1<<j)) continue; dp[i|(1<<j)] = max(dp[i|(1<<j)], dp[i]+additionalScore(i, j, height[idx])); } } return dp[(1<<16)-1]; } };
500. NarrowPassage
問題：長さLの細い道で、n匹の狼が目的地に向かう。すれ違うにはx=0かx=Lの地点までいかないといけない。狼の移動距離の合計の最小値は？
- x=0ですれ違うグループ、x=Lですれ違うグループの作り方を全探索すれば…と思った
- それで通る問題が500で出るわけが無い…と思って手元で撃墜ケースを探す
- x=0ですれ違い→x=Lですれ違い のパターンが最適な事もありそう
- というわけで、2回出たり入ったりするのを全探索してみた。
- sample3にやられる
- なん…だと…。
- バグかと思ってコードを見てたけどバグは見つからず。
- 計算量に余裕があったので、3回出たり入ったりしてみた。
- sample3が倒せてしまった。
- 良く分からんけど250が解けてなかったので投げた。
- 通ったのはsample3のおかげと言わざるを得ません。
- 以下は本番で書いたコード。酷いコピペ実装だったし、よく通ったなと思う。
class NarrowPassage { public: int minDist(int L, vector <int> a, vector <int> b) { int n = a.size(); vector< pair<int,int> > vp; vector< pair<int,int> > p1(n), p2(n), p3(n); for(int i=0;i<n;i++) vp.push_back(make_pair(a[i],b[i])); sort(vp.begin(), vp.end()); int res = 1000000007; for(int i=0;i<=n;i++){ for(int k=0;k<n;k++) p1[k] = vp[k]; int tmp1 = 0; for(int k=0;k<i;k++){ tmp1 += p1[k].first; p1[k].first = 0; } sort(p1.begin(), p1.end()); for(int j=0;j<=n;j++){ int tmp2 = tmp1; for(int k=0;k<n;k++) p2[k] = p1[k]; for(int k=0;k<j;k++){ tmp2 += L - p2[n-1-k].first; p2[n-1-k].first = L; } sort(p2.begin(), p2.end()); for(int l=0;l<=n;l++){ for(int k=0;k<n;k++) p3[k] = p2[k]; int tmp3 = tmp2; for(int k=0;k<l;k++){ tmp3 += p3[k].first; p3[k].first = 0; } sort(p3.begin(), p3.end()); bool ok = true; for(int k=0;k+1<n;k++){ if(p3[k].second > p3[k+1].second) ok = false; } if(!ok) continue; for(int k=0;k<n;k++){ tmp3 += abs(p3[k].first - p3[k].second); } res = min(tmp3, res); } } } for(int i=0;i<=n;i++){ for(int k=0;k<n;k++) p1[k] = vp[k]; int tmp1 = 0; for(int k=0;k<i;k++){ tmp1 += L - p1[n-1-k].first; p1[n-1-k].first = L; } sort(p1.begin(), p1.end()); for(int j=0;j<=n;j++){ int tmp2 = tmp1; for(int k=0;k<n;k++) p2[k] = p1[k]; for(int k=0;k<j;k++){ tmp2 += p2[k].first; p2[k].first = 0; } sort(p2.begin(), p2.end()); for(int l=0;l<=n;l++){ for(int k=0;k<n;k++) p3[k] = p2[k]; int tmp3 = tmp2; for(int k=0;k<l;k++){ tmp3 += L - p3[n-1-k].first; p3[n-1-k].first = L; } sort(p3.begin(), p3.end()); bool ok = true; for(int k=0;k+1<n;k++){ if(p3[k].second > p3[k+1].second) ok = false; } if(!ok) continue; for(int k=0;k<n;k++){ tmp3 += abs(p3[k].first - p3[k].second); } res = min(tmp3, res); } } } return res; } };
1000. TreePuzzle
- 見てない。
- -
結果：-- / AC / -- ，+0, 255.25pt, 101位
レーティング：2404 -> 2442
運が良かったとしか言いようのない結果です。250でbitDP思いつけなかったのが反省点。
Google Code Jam 2014 Round1B
先のARCで運を使い果たしたので震えながら参加。
- -
A : The Repeater
- アルファベットの登場順を崩すような操作はできない
- なので与えられた文字列で、アルファベットの登場順が違うのがあったら勝てない
- 勝てるんだったら文字ごとに適当に個数を揃えてやれば良い
- こういうのを美しく書けるようになりたい人生でした
#include <iostream> #include <vector> #include <string> #include <cstdio> #include <algorithm> using namespace std; string conv(const string& s, vector<int>& v){ int cnt = 1; string res; res += s[0]; char c = s[0]; for(int i=1;i<s.size();i++){ if(c == s[i]) cnt++; else { v.push_back(cnt); cnt = 1; c = s[i]; res += c; } } v.push_back(cnt); return res; } int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int N; cin >> N; vector< vector<int> > v(N); bool won = true; string s, t; cin >> s; t = conv(s, v[0]); for(int i=1;i<N;i++){ cin >> s; string u = conv(s, v[i]); if(u != t) won = false; } if(!won){ printf("Case #%d: Fegla Won\n", test); continue; } int res = 0; for(int i=0;i<v[0].size();i++){ int add = 1000000; for(int j=1;j<=100;j++){ int sum = 0; for(int k=0;k<v.size();k++){ sum += abs(v[k][i]-j); } add = min(add, sum); } res += add; } printf("Case #%d: %d\n", test, res); } }
B : New Lottery Game
- あっ、このlargeやばいやつだ。と思ってまずはsmallを通した。
- largeは挑戦者が多いのに全く分からず、悲しい気持ちになってた。
- 先にC提出した後も分からなすぎて、暗殺教室9巻を読んでた程の体たらく
- 終了20分前くらいに、桁DPというワードが脳内に浮上したのでギリギリ通せた。
- 5重ループを書きながら、俺は何をしてるんだ…という気持ちになってた。
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; int solveSmall(int A, int B, int K){ int res = 0; for(int i=0;i<A;i++){ for(int j=0;j<B;j++){ if((i&j) < K) res++; } } return res; } long long solveLarge(int A, int B, int K){ long long dp[2][2][2][2]; memset(dp, 0, sizeof(dp)); dp[0][1][1][1] = 1; for(int i=30;i>=0;i--){ int cur = i%2, next = 1-cur; memset(dp[next], 0, sizeof(dp[next])); for(int smallA=0;smallA<2;smallA++){ for(int smallB=0;smallB<2;smallB++){ for(int smallK=0;smallK<2;smallK++){ if(dp[cur][smallA][smallB][smallK] == 0) continue; for(int a=0;a<2;a++){ if(smallA && !(A&(1<<i)) && a == 1) continue; int nA = smallA ? ((A>>i)&1) == a : 0; for(int b=0;b<2;b++){ if(smallB && !(B&(1<<i)) && b == 1) continue; int nB = smallB ? ((B>>i)&1) == b : 0; if(smallK && !(K&(1<<i)) && a == 1 && b == 1) continue; int nK = smallK ? ((K>>i)&1) == (a&b) : 0; dp[next][nA][nB][nK] += dp[cur][smallA][smallB][smallK]; } } } } } } return dp[1][0][0][0]; } int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int A, B, K; cin >> A >> B >> K; printf("Case #%d: %lld\n", test, solveLarge(A, B, K)); } }
C : The Bored Traveling Salesman
- 悲しい気持ちでBから逃げてきたので、精神を安定させるためにまずsmallを通した。
- largeは…ある順で辿った時に、そこから残りを全部辿れるか判定できれば行けそう。
- validな奴を貪欲に辿っていくというパターン
- 各土地に往路チケットで行けるのは高々1回という仕様が地味に面倒
- 途中まで辿った段階で復路チケットを持ってる土地のリスト(A)と、往復使いきった土地のリスト(B)を持っておき、Aに属する土地から、Bに属する土地を通らずに全ての土地に行けるかを判定した。
- smallの解答と一致してそうに見えたので提出。通った。
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstring> #include <cstdio> #include <stack> #include <queue> using namespace std; typedef vector< vector<int> > Graph; bool isValid(const Graph& g, const vector<int>& order){ stack<int> st; st.push(order[0]); for(int i=1;i<order.size();i++){ while(true){ if(st.empty()) return false; int pos = st.top(); bool ok = false; for(int j=0;j<g[pos].size();j++){ if(g[pos][j] == order[i]) ok = true; } if(ok){ st.push(order[i]); break; } else st.pop(); } } int n = g.size(); vector<int> visit(n, 0); for(int i=0;i<order.size();i++) visit[order[i]] = 1; queue<int> qu; while(!st.empty()){ qu.push(st.top()); st.pop(); } while(!qu.empty()){ int p = qu.front(); qu.pop(); for(int i=0;i<g[p].size();i++){ if(visit[g[p][i]]) continue; visit[g[p][i]] = 1; qu.push(g[p][i]); } } for(int i=0;i<n;i++) if(visit[i]==0) return false; return true; } int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int N, M; cin >> N >> M; Graph g(N); vector<string> vs(N); vector<int> state(N, 0); for(int i=0;i<N;i++) cin >> vs[i]; for(int i=0;i<M;i++){ int a, b; cin >> a >> b; g[a-1].push_back(b-1); g[b-1].push_back(a-1); } string res; int idx = 0; for(int i=0;i<N;i++) if(vs[idx] > vs[i]) idx = i; res = vs[idx]; vector<int> order; order.push_back(idx); vector<int> visit(N, 0); visit[idx] = 2; for(int i=0;i<g[idx].size();i++) visit[g[idx][i]] = 1; for(int i=1;i<N;i++){ idx = -1; order.push_back(0); for(int j=0;j<N;j++){ if(visit[j]!=1) continue; order.back() = j; if(isValid(g, order) && (idx==-1 || vs[idx] > vs[j])) idx = j; } order.back() = idx; res += vs[idx]; visit[idx] = 2; for(int i=0;i<g[idx].size();i++) visit[g[idx][i]] = max(1, visit[g[idx][i]]); } printf("Case #%d: %s\n", test, res.c_str()); } }
- -
Rank 105 : /oo/oo/oo/ Score 100, Penalty 2:17:30
small全部通れば通過くらいかと思ってましたが、通過ラインはそれより上でした。
こわい(´・ω・｀)
ARC022
奇跡が起きて1位。順位表のスクリーンショットは撮った。
- -
A : スーパーICT高校生
- 指定の文字列が部分列として含まれるか調べるだけの簡単なお仕事
- A問題だしと思ってムダにO(n^3)で書いた。反省はしていない。
#include <iostream> #include <string> using namespace std; bool check(string s){ int n = s.size(); for(int i=0;i<n;i++){ if(s[i]!='i'&&s[i]!='I') continue; for(int j=i+1;j<n;j++){ if(s[j]!='c'&&s[j]!='C') continue; for(int k=j+1;k<n;k++){ if(s[k]!='t'&&s[k]!='T') continue; return true; } } } return false; } int main(){ string s; while(cin >> s){ cout << (check(s) ? "YES" : "NO") << endl; } }
B : 細長いお菓子
- はいはい、尺取り尺取り…と思ってたら2WAだした。これはひどい。
- とはいえ、こういうのはバグらせやすいのでサクッと書ける人々はすごいと思う。
#include <iostream> #include <vector> #include <string> #include <cstring> using namespace std; int idx[100001]; int A[100000]; int main(){ int N; while(cin >> N){ for(int i=0;i<N;i++) cin >> A[i]; memset(idx, -1, sizeof(idx)); int cur = 0; int res = 0; for(int i=0;i<N;i++){ if(idx[A[i]] >= cur){ res = max(res, i-cur); cur = idx[A[i]]+1; } idx[A[i]] = i; } res = max(res, N-cur); cout << res << endl; } }
C : ロミオとジュリエット
#include <iostream> #include <vector> #include <string> #include <queue> #include <cstring> using namespace std; typedef vector< vector<int> > Graph; int getFar(const Graph& g, int start){ const int INF = 1000000007; int n = g.size(); vector<int> dist(n, INF); dist[start] = 0; queue<int> qu; qu.push(start); int res = start; while(!qu.empty()){ int p = qu.front(); qu.pop(); res = p; for(int i=0;i<g[p].size();i++){ int next = g[p][i]; if(dist[next] < dist[p]+1) continue; dist[next] = dist[p]+1; qu.push(next); } } return res; } int main(){ int N; while(cin >> N){ Graph g(N); for(int i=0;i<N-1;i++){ int a, b; cin >> a >> b; g[a-1].push_back(b-1); g[b-1].push_back(a-1); } int s = getFar(g, 0); int t = getFar(g, s); cout << s+1 << " " << t+1 << endl; } }
D : スプリンクラー
- まだ全ての円が原点を通るという性質を使ってない。
- 60点と100点の差が円の存在範囲だけなので、60点は30点の延長な気がしてくる。
- 中心が凸包を構成する円だけ調べたら良いのでは、と思うも正当性に自信がない。
- やること無いし書いてみるか、と書いて投げたら60点取れてしまった。
- ここで残り20分くらい。暫定1位だったのでスクリーンショット撮った。
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cmath> #include <complex> using namespace std; const double EPS = 1e-8; typedef complex<double> P; double cross(P a, P b){ return imag(conj(a)*b); } double angle(P a, P b){ return arg(conj(a)*b); } bool compare(const P &a, const P &b){ return make_pair(real(a),imag(a)) < make_pair(real(b),imag(b)); } vector<P> convexHull(vector<P> vp){ if(vp.size() < 3) return vp; sort(vp.begin(), vp.end(), compare); vector< pair<double,int> > vi; for(int i=1;i<vp.size();i++) vi.push_back(make_pair(angle(P(1,0),vp[i]-vp[0]), i)); sort(vi.begin(), vi.end()); vector<P> res(2); res[0] = vp[0]; res[1] = vp[vi[0].second]; for(int i=1;i<vi.size();i++){ P next = vp[vi[i].second]; int sz = res.size(); while(sz>=2&&cross(res[sz-1]-res[sz-2],next-res[sz-1])<EPS){ res.pop_back(); sz--; } res.push_back(next); } return res; } int main(){ int N; while(cin >> N){ vector< pair<int,int> > v[6000]; vector<P> vp; for(int i=0;i<N;i++){ int x, y; cin >> x >> y; vp.push_back(P(x,y)); } vp = convexHull(vp); for(int i=0;i<vp.size();i++){ int x = vp[i].real(); int y = vp[i].imag(); int sr = x*x+y*y; int r = sqrt(sr)+1e-8; for(int j=-r;j<=r;j++){ int range = sqrt(sr-j*j)+1e-8; int yIdx = y+j+3000; v[yIdx].push_back(make_pair(x-range,x+range)); } } int res = 0; for(int i=0;i<6000;i++){ if(v[i].empty()) continue; sort(v[i].begin(), v[i].end()); int begin = v[i][0].first; int end = v[i][0].second; for(int j=1;j<v[i].size();j++){ if(end < v[i][j].first){ res += end-begin+1; begin = v[i][j].first; end = v[i][j].second; } else { end = max(end, v[i][j].second); } } res += end-begin+1; } cout << res << endl; } }
- -
ついにAtCoderで1800というレーティングを頂きました。黄色くらい？
この後のGCJで使う分の運が残ってるのか、とても不安です。
ARC019 C.最後の森
問題リンク
- 分岐点全探索で良かったらしい。
- 村、城、ほこらの各地点からBFSする
- 経路は 村→分岐点→ほこら→分岐点→城 として表せる
- 各点Pについて、村→Pのコスト + 2*(ほこら→Pのコスト) + 城→Pのコスト を調べる
- 倒すモンスターの数をk以下にした時のコストを持っておけばO(k^2)で分かる
- 全体でO(n^2 k^2)
- 本番で通らなかったのは、普通にバグってたのと分岐点に敵がいた場合の処理漏れ。
#include <iostream> #include <vector> #include <string> #include <queue> #include <cstring> using namespace std; int step[3][101][50][50]; class Node { public: int k, x, y; Node(int k, int x, int y) : k(k), x(x), y(y) {} }; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, -1, 0, 1}; int solve(const vector<string>& vs, int K){ int n = vs.size(), m = vs[0].size(); memset(step, -1, sizeof(step)); for(int start=0;start<3;start++){ queue<Node> qu; int sx, sy; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(vs[i][j] == "SCG"[start]) sx = i, sy = j; step[start][0][sx][sy] = 0; qu.push(Node(0, sx, sy)); while(!qu.empty()){ Node nd = qu.front(); qu.pop(); for(int i=0;i<4;i++){ int nx = nd.x+dx[i]; int ny = nd.y+dy[i]; if(nx < 0 || n <= nx || ny < 0 || m <= ny) continue; int nk = nd.k + (vs[nx][ny]=='E'); if(vs[nx][ny] == 'T') continue; if(nk > K) continue; if(step[start][nk][nx][ny] != -1) continue; step[start][nk][nx][ny] = step[start][nd.k][nd.x][nd.y]+1; qu.push(Node(nk, nx, ny)); } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int best = -1; for(int k=0;k<=K;k++){ if(best == -1 || (step[start][k][i][j] != -1 && best > step[start][k][i][j])){ best = step[start][k][i][j]; } step[start][k][i][j] = best; } } } } int res = -1; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int upperB = K+(vs[i][j] == 'E'); int upperC = K+2*(vs[i][j] == 'E'); for(int kA=0;kA<=K;kA++){ if(step[0][kA][i][j] == -1) continue; for(int kB=0;kB<=K;kB++){ if(kA+kB > upperB) break; if(step[1][kB][i][j] == -1) continue; int kC = min(K, upperC-(kA+kB)); if(step[2][kC][i][j] == -1) continue; int sum = step[0][kA][i][j] + 2*step[1][kB][i][j] + step[2][kC][i][j]; if(res == -1 || res > sum) res = sum; } } } } return res; } int main(){ int N, M, K; while(cin >> N >> M >> K){ vector<string> vs(N); for(int i=0;i<N;i++) cin >> vs[i]; cout << solve(vs, K) << endl; } }
ARC019
1年半ぶりに参加。
- -
A : お買い物クライシス
- 指定の文字を指定の数字に変えるだけの簡単なお仕事
- A問題だしと思ってテストせずに投げた。通って良かった。
#include <iostream> #include <string> using namespace std; int main(){ string s; while(cin >> s){ for(int i=0;i<s.size();i++){ if(s[i] == 'O') s[i] = '0'; if(s[i] == 'D') s[i] = '0'; if(s[i] == 'I') s[i] = '1'; if(s[i] == 'Z') s[i] = '2'; if(s[i] == 'S') s[i] = '5'; if(s[i] == 'B') s[i] = '8'; } cout << s << endl; } }
B : こだわりの名前
- 無意識に回文の種類数を数えてたぜ…(サンプルテストして気付いた)。
- 何でサンプル通らないんだろうと思ったけど、問題文は良く読めという事ですね。
#include <iostream> #include <vector> #include <string> using namespace std; int main(){ string s; while(cin >> s){ int n = s.size(); int error = 0; for(int i=0;i<n-1-i;i++){ if(s[i] != s[n-1-i]) error++; } if(error == 0){ cout << 25*(n%2 == 0 ? n : n-1) << endl; } else if(error == 1){ cout << 25*n-2 << endl; } else { cout << 25*n << endl; } } }
C : 最後の森
- ワカンネってなってD問題に逃避した。
- 中継地点全探索すれば良くね?と終了間際に思ったものの、3ケースだけ合わず撃沈。
D : ほんとうのたたかい
- 伝説の剣の名前を見てグラフのやばい問題に違いないと思って開いた。
- 違った。
- 電王戦の記者会見が盛り上がってたので、チラ見しながら考える。
- 素数個単位で適当にずらせば良くねという結論になり、並べてみた。
- 1728個配置できた。
- 投げた→WA
- なんでや！と思って問題文よく読んだら出力行数も必要だったので加えて投げた→WA
- なんでや！と思って問題文よく読んだら'O'を'o'にしてたので直して投げた→AC
- 'o'と'O'の違いが分かる大人になりたかった。
#include <iostream> using namespace std; char s[150][151]; int main(){ for(int i=0;i<150;i++){ for(int j=0;j<150;j++) s[i][j] = '.'; s[i][151] = '\0'; } for(int i=0;i<13;i++){ for(int j=0;j<13;j++){ if(13*i+j >= 150) break; s[i][13*i+j] = 'O'; } } for(int i=0;i<13;i++){ for(int j=0;j<13;j++){ if(13*j+i >= 150) break; s[13+i][13*j+i] = 'O'; } } for(int i=1;i<=13;i++){ for(int j=0;j<13;j++){ if(13*i+13+j >= 150) break; int cur = j, bit = 1<<j; for(int k=0;k<13;k++){ if(13*k+cur >= 150) break; s[13*i+13+j][13*k+cur] = 'O'; cur = (cur+i)%13; while(k<11 && (bit&(1<<cur))){ cur = (cur+1)%13; } bit |= (1<<cur); } } } cout << 150 << endl; for(int i=0;i<150;i++){ cout << s[i] << endl; } }
- -
今日のまとめ：日本語といえど問題文はちゃんと読みましょう
模擬地区予選2013
誰も見てないと思って担当した問題について好き勝手書くコーナー。
ソースコード載せてる以外は解法に触れてないのでご注意？
- -
E : Putter
- Testerでした(writerはir5さん)。
- サンプルが見た目より強いのでこれ通れば大体ACじゃねと思ってましたが、そうでもなかった。せめてもう1個くらいあっても良かった気もしますが、複雑なのを入れたところでデバッグできない説も。
- 提出された解答を何個か眺めた限りnext_permutationを使った実装が多かったですが、私の解答はDFS。ジャッジデータ中で答えが一番大きいものでも68なので、結構枝が刈れる(刈らなくても通りますが)。
- ライブラリゲーでなく、実装をちゃんと考える必要がありながらも重実装すぎない良い幾何の問題だったのではと思っています。
#include <iostream> #include <vector> #include <complex> using namespace std; const double EPS = 1e-8; typedef complex<double> P; struct L { P p, q; L() : p(P(0,0)), q(P(0,0)) {} L(P p, P q) : p(p), q(q) {} }; P start; vector<P> g; vector<P> dir; vector<L> seg; double dot(P a, P b) { return real(conj(a)*b); } double cross(P a, P b) { return imag(conj(a)*b); } P footPerp(const L& l, const P& p) { return l.p + (l.q-l.p)*(dot(l.q-l.p, p-l.p) / norm(l.q-l.p)); } P lineShadow(const L& l, const P& p){ return 2.0*footPerp(l, p)-p; } P getDir(const vector<int>& order, P target, int depth){ for(int i=depth-1;i>=0;i--){ target = lineShadow(seg[order[i]], target); } P res = target - start; res /= abs(res); return res; } int dfs(vector<int>& order, vector<int>& used, P dirL, P dirR, int depth){ int n = g.size(); if(depth == n) return 1; int res = 0; for(int i=0;i<n;i++){ if(used[i]) continue; order[depth] = i; P dL = getDir(order, depth%2 ? seg[i].q : seg[i].p, depth); P dR = getDir(order, depth%2 ? seg[i].p : seg[i].q, depth); if(cross(dL, dirL) > 0) dL = dirL; if(cross(dR, dirR) < 0) dR = dirR; if(cross(dL, dR) > 0){ used[i] = 1; res += dfs(order, used, dL, dR, depth+1); used[i] = 0; } } return res; } int main(){ int n; while(cin >> n && n){ cin >> start.real() >> start.imag(); g.resize(n); dir.resize(n); seg.resize(n); for(int i=0;i<n;i++) cin >> g[i].real() >> g[i].imag(); for(int i=0;i<n;i++){ seg[i] = L(g[i], g[(i+1)%n]); dir[i] = g[(i+1)%n] - g[i]; dir[i] /= abs(dir[i]); } int res = 0; vector<int> order(n, -1), used(n, 0); for(int i=0;i<n;++i){ order[0] = i; used[i] = 1; res += dfs(order, used, g[i]+EPS*dir[i]-start, g[(i+1)%n]-EPS*dir[i]-start, 1); used[i] = 0; } cout << res << endl; } }
G : Floating Islands
- writerでした。なんかMSTの変わった問題作れないかな−と、模擬国内Dと同時期に考えてた問題。模擬国内のちょっと後に出題した形にまとまり、今回採用となりました。
- 模擬国内Dではめんどい仕様を上手く問題文にできなかった事を反省したので、仕様はシンプルにまとめました。キレイにまとまったので個人的に気に入ってます。
- 提案時は、もう少し計算量落ちるような…と思いながらO(n^3)で出したのですが、某所スタッフにより即刻O(n^2)に落とされ今に至ります。
- O(n^3)解までは理詰めでいけて実装も楽ですが、O(n^2)解をキッチリ実装しきるのは意外と大変です。サンプルではO(n^2)解のデバッグが難しいので、大きめのケースを作ってO(n^3)解と答えを比較するのも手。
- 解説スライドに載せたコーナーケースは良く釣れてました。
- 今回のサンプル(誰得コーナー)
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; const long long INF = 1000000000000000000LL; int main(){ int N; while(cin >> N && N){ vector< pair<int,int> > multi; vector<int> one; if(N == 2){ int a, b, c; cin >> a >> c >> b >> c; cout << abs(a-b) << endl; continue; } for(int i=0;i<N;i++){ int p, d; cin >> p >> d; if(d == 1) one.push_back(p); else multi.push_back(make_pair(p, d)); } sort(one.begin(), one.end()); sort(multi.begin(), multi.end()); if(multi.size() > 1){ multi[0].second--; multi.back().second--; for(int i=1;i+1<multi.size();i++) multi[i].second -= 2; } vector<int> lower(one.size()), upper(one.size()); for(int i=0;i<one.size();i++){ int idx = 0; while(idx < multi.size() && one[i] > multi[idx].first){ idx++; } lower[i] = upper[i] = idx; if(idx == multi.size()) lower[i]--; int sum = 0; while(lower[i] > 0){ if(one[i] < multi[lower[i]].first){ lower[i]--; continue; } sum += multi[lower[i]].second; if(sum >= one.size()) break; lower[i]--; } sum = 0; while(upper[i] < multi.size()){ sum += multi[upper[i]].second; upper[i]++; if(sum >= one.size()) break; } } vector<long long> dp(one.size()+1, INF); dp[0] = 0; for(int i=0;i<multi.size();i++){ int start = one.size()+1, end = 0; for(int j=0;j<one.size();j++){ if(lower[j] <= i && i < upper[j]){ start = min(j, start); end = max(j, end); } } for(int j=0;j<multi[i].second;j++){ for(int k=end;k>=start;k--){ dp[k+1] = min(dp[k+1], dp[k]+abs(multi[i].first-one[k])); } } } long long res = dp[one.size()]; cout << (res == INF ? -1 : res + multi.back().first - multi[0].first) << endl; } }
2013国内予選 D. 素数洞穴
解法
- 洞穴のマップを頑張って生成する
- 全ての洞穴について到達時の最適解を確定させ、最も良かったものを答えれば良い
#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; int dx[] = {0, -1, 0, 1}; int dy[] = {1, 0, -1, 0}; bool isPrime(int p){ if(p==1) return false; for(int i=2;i*i<=p;i++) if(p%i==0) return false; return true; } int main(){ static int id[1000][1001]; static int pt[1000][1001]; vector< pair<int,int> > pos(1); memset(pt, -1, sizeof(pt)); memset(id, -1, sizeof(id)); id[500][500] = 1; pt[500][500] = 0; pos.push_back(make_pair(500, 500)); id[500][501] = 2; pt[500][501] = 1; pos.push_back(make_pair(500, 501)); int dir = 0; int curX = 500, curY = 501; for(int i=3;i<=1000000;++i){ int ndir = (dir+1)%4; if(pt[curX+dx[ndir]][curY+dy[ndir]]!=-1) ndir = dir; curX += dx[ndir]; curY += dy[ndir]; id[curX][curY] = i; pt[curX][curY] = isPrime(i); pos.push_back(make_pair(curX, curY)); dir = ndir; } int m, n; while(cin >> m >> n && n){ pair<int, int> res = make_pair(isPrime(n), isPrime(n) ? n : 0); vector< vector< pair<int,int> > > dp(1000, vector< pair<int,int> >(1001, make_pair(-1, -1))); dp[pos[n].first][pos[n].second] = res; for(int i=pos[n].first;i+1<1000;i++){ for(int j=0;j<=1000;j++){ if(dp[i][j].first == -1) continue; for(int k=-1;k<=1;k++){ if(j+k<0||1000<j+k) continue; if(id[i+1][j+k] < 0 || m < id[i+1][j+k]) continue; pair<int,int> next = dp[i][j]; if(pt[i+1][j+k]) next.first++, next.second = id[i+1][j+k]; dp[i+1][j+k] = max(next, dp[i+1][j+k]); res = max(res, dp[i+1][j+k]); } } } cout << res.first << " " << res.second << endl; } }
