ハル研プロコン2016に参加しました
ハル研プロコンに参加しました。
www.hallab.co.jp
個人的にはとても楽しかったのですが, 上位の人によるとあまり工夫のしどころがなかったようです。
とりあえず自分のやったことを書いていきたいと思います。
貪欲パート
この後「ちょっと待てばレーザーでたくさん消せるならちょっと待つ」というのを入れましたが, これはうまくいきませんでした。
これについて考察すると, 例えば残り 3 個の小惑星があり, 1 つは非常に遠くにあって残りの 2 つはすぐ近くにあるとします。今打つと遠くにある一つのみを消すことになるのですが, ちょっと待ってから打つと近くにある小惑星が 2 つ消せるとしましょう。
そうすると, 元の方法では「遠くを消してからちょっと移動して 2 つ消える」だったのに対し, もう一つの方法では「2 つ同時にレーザー打ってから遠くにある小惑星に近づいてまたレーザーを打つ」となるので, 明らかに損をします。
- 近づく小惑星に関して, 端っこに近いやつほど近づきやすくする, で 68199
- レーザーも端っこ消しやすくすれば良くなるのでは, を勘違いして真ん中にあるほど消しやすくしたところ改善, で 67686
これについて考察すると, 今回の自分のアルゴリズムではなにかの小惑星に向かう動きしか考慮していないので, 宇宙船自体はずっと端っこにいたほうが有利っぽいことを考えるとレーザーは真ん中をたくさん消すほうが良さげだったということですかね。
探索パート
- 行先であり得そうなものを 2 通り拾ってくるようにする, で 62469
- ここでマグカップを確信しました。
- レーザーについてもあり得そうなものを 2 通り拾ってくる, で 61632
- 枝刈りを入れることでたくさん探索して 60117
- 枝刈りは, (今のターン) + (まだかかりそうなターン数) > (今までの最短ターン) だったら消す感じです。
- 時間で粘るようにする, で 59761
後は気合の高速化で探索範囲を広げました。ここまではめっちゃ楽しかったんですがこっからはあんまり楽しくなかったです。
最終的には 59136 ターンで finish しました。最後に確認したときは 4 位僅差で 3 位だったと思いますがどうなることやら。
上位陣の話を聞いたところ,
だったそうです。確かにこれだと高速化ゲーで楽しくなさそうですが, ビームサーチは「ターンでゲームを進めると評価関数つくりにくいなぁ」と思ってた自分にとっては「小惑星の壊れた数」でサーチを進めるのは頭の良さを感じました。なるほど。
できれば 3 位に入っててほしいです…
Codeforces Round #365 (Div. 2) C. Chris and Road
問題
n 頂点の凸多角形が x 軸方向の負の方向に単位時間 v で移動する。この凸多角形の内部に入らないように, y 軸を y = w まで移動したい。
y 軸の移動速度が最大で u の時, 最短で何秒で y = w まで移動できるか。
解法
凸多角形の左側を歩くときと右側を歩くときで場合分けします。右側を歩くのは必ず成功するので, これでちゃんと答えが求められます。
左側を歩く場合, x 軸が最小になる点から y 軸が最大になる点(時計の 9 時方向から 12 時方向ってイメージ)で凸多角形に衝突しなければ良いです。
右側を歩く場合, y 軸が最小になる点から x 軸が最大になる点(時計の 6 時方向から 3 時方向)で凸多角形の内部に入らないようにすれば良いです。
const int MAXN = 100100; pii P[MAXN]; int N, W, V, U; typedef double Real; int prv(int i) { return (i+N-1)%N; } int nxt(int i) { return (i+1)%N; } int main() { cin >> N >> W >> V >> U; for (int i = 0; i < N; i++) cin >> P[i].first >> P[i].second; int imin = min_element(P, P+N) - P; int imax = max_element(P, P+N) - P; Real ans = 1e18; // 多角形の左側を通る場合 { int i = imin; bool ng = false; for (int j = 0; j < N; j++) { Real t = (Real)P[i].second / U; Real x = P[i].first - V*t; if (x < 0) { ng = true; break; } int ni = prv(i); if (P[ni].second <= P[i].second) break; i = ni; } if (!ng) ans = min(ans, (Real)W/U); } // 多角形の右側を通る場合 { while (1) { int ni = prv(imax); if (P[ni].second >= P[imax].second) break; imax = ni; } Real tmp = 0; int y = 0; int i = imax; for (int j = 0; j < N; j++) { // 普通に歩いてかかる時間 Real need = (Real)(P[i].second - y) / U; if ((Real)P[i].first - V*(tmp+need) <= 0) tmp += need; else tmp = (Real)P[i].first / V; y = P[i].second; int ni = nxt(i); if (P[ni].first <= P[i].first) break; i = ni; } tmp += (Real)(W-y)/U; ans = min(ans, tmp); } printf("%.10lf\n", ans); return 0; }
Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum
解法
偶数じゃなくて奇数だったら簡単です。というのも, xor は 2 回同じ数をかけられれば自動的に 0 になるので [l, r] の区間の xor を累積和で適当にやれば良いだけだからです。
ですが, これは偶数の場合を聞いているので, 答えるべきものとしては [l, r] の累積xor から, [l, r] に存在する数の xor の和を取ったもの, になります。
累積和は簡単なので, 区間 [l, r] におけるユニークな数の xor 和を考えます。
クエリを R の順番に並べます。で, ある数がすでに表れていた場合には前回現れたところはすべて無効化するような感じにします。具体的には
last[num] = (num が最後に出てくる index) というようにすると, i 番目に num が出てきた場合, A[last[num]] ^= num とやることによって解決します。こういう風にすれば bit なりセグメント木なりで区間 xor の問題に落とせます。
// 0-based Binary Indexed Tree template<typename T> struct BIT { int max; vector<T> bit; BIT(int max) : max(max) {bit.resize(max+1);} // [0, i) T sum(int i) { T s = 0; while (i > 0) { (s ^= bit[i]); i ^= i&-i; } return s; } // 0-basedな座標iに値xを追加する void add(int i, T x) { ++i; while (i <= max) { (bit[i] ^= x); i += i&-i; } } // [a, b) T sum(int a, int b) { return sum(b)^sum(a); } }; const int MAXN = 1001000; int A[MAXN], S[MAXN], L[MAXN], R[MAXN]; int ans[MAXN]; vector<int> G[MAXN]; int main() { int N, M; scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", A+i); for (int i = 1; i <= N; i++) S[i] = S[i-1]^A[i-1]; cin >> M; for (int i = 0; i < M; i++) { scanf("%d %d", L+i, R+i); L[i]--; ans[i] = S[R[i]]^S[L[i]]; G[R[i]].push_back(i); } BIT<int> bit(MAXN); map<int, int> last; for (int i = 0; i < N; i++) { bit.add(i, A[i]); if (last.find(A[i]) != last.end()) { bit.add(last[A[i]], A[i]); } for (int j : G[i+1]) { ans[j] ^= bit.sum(L[j], i+1); } last[A[i]] = i; } for (int i = 0; i < M; i++) printf("%d\n", ans[i]); return 0; }
Codeforces Round #372 (Div. 1) B. Complete The Graph
いやなんか時間とってゆっくり競プロやりたいんですけど…
問題
コスト付きの無向グラフが与えられる。いくつかの辺のコストは好きに選べるので, s から t への最短経路の大きさを L にしたい。このようなことが可能であれば, そのうちの 1 つを答えよ。
解法
まず自明に解がない場合を省きます。というのは, いじれるすべての辺のコストを INF にしても最短経路が L 未満の場合と, いじれるすべての辺のコストを 1 にしても最短経路が L より大きい場合です。
逆に, これ以外の場合は, 解が存在することが示せます。これは
- いじれるすべての辺のコストを 1 にすると最短経路は L 未満, 全て INF にすると L より大きい
- いじれる辺のいずれかのコストを 1 増やすと最短経路は 1 増えるかそのまま
から言えます。
で, どう具体的にアルゴリズムに落とすかというと,
- いじれる辺のすべてのコストを 1 にセット
- 以下を繰り返す
- dijkstra して t までの距離を求める。L なら終了
- そうでない場合, s から t までの最短経路にいじれる辺があるはず。その辺のコストを L-d[t]+1 にする。
というようにやれば, いじる辺は M 本しかないので O(M^2 log N) になります(これでギリギリ通った)。さらに, 最初にすべてのコストを 1 にしたときの最短経路上の辺のみを使うようにすると O(NMlog N) になって高速になります。
struct edge { int v; ll w; int id; edge() {} edge(int v, ll w, int id) : v(v), w(w), id(id) {}; }; vector<edge> G[1010]; vector<ll> dijkstra(int n, int s, int t) { vector<ll> d(n, LLONG_MAX/10); d[s] = 0; priority_queue<pair<ll, int> > que; que.push(make_pair(0ll, s)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second; ll dist = -p.first; if (dist > d[u]) continue; if (u == t) return d; for (edge e : G[u]) { if (d[e.v] > d[u]+e.w) { d[e.v] = d[u] + e.w; que.push(make_pair(-d[e.v], e.v)); } } } return d; } void no() { cout << "NO" << endl; exit(0); } const int MAXM = 10101; int U[MAXM], V[MAXM], W[MAXM]; bool use[MAXM]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M, L, s, t; cin >> N >> M >> L >> s >> t; const ll INF = 1e9; for (int i = 0; i < M; i++) cin >> U[i] >> V[i] >> W[i]; for (int i = 0; i < M; i++) if (W[i]) { G[U[i]].emplace_back(V[i], W[i], i); G[V[i]].emplace_back(U[i], W[i], i); } auto d = dijkstra(N, s, t); if (d[t] < L) no(); if (d[t] == L) { cout << "YES" << endl; for (int i = 0; i < M; i++) { ll w = (W[i]==0) ? INF : W[i]; cout << U[i] << " " << V[i] << " " << w << endl; } return 0; } for (int i = 0; i < M; i++) if (!W[i]) { G[U[i]].emplace_back(V[i], 1, i); G[V[i]].emplace_back(U[i], 1, i); } d = dijkstra(N, s, t); if (d[t] > L) no(); { int now = t; while (now != s) { for (edge e : G[now]) { if (d[e.v] + e.w == d[now]) { use[e.id] = true; now = e.v; break; } } } } while (1) { for (int i = 0; i < N; i++) G[i].clear(); for (int i = 0; i < M; i++) { ll w = INF; if (W[i] == 0 && use[i]) w = 1; if (W[i]) w = W[i]; G[U[i]].emplace_back(V[i], w, i); G[V[i]].emplace_back(U[i], w, i); } auto d = dijkstra(N, s, t); if (d[t] == L) break; int now = t; while (now != s) { int id = -1; for (edge e : G[now]) { if (d[e.v]+e.w == d[now]) { id = e.id; now = e.v; break; } } if (W[id] == 0) { W[id] = L-d[t]+1; break; } } } cout << "YES" << endl; for (int i = 0; i < M; i++) { ll w = INF; if (W[i] == 0 && use[i]) w = 1; if (W[i]) w = W[i]; cout << U[i] << " " << V[i] << " " << w << endl; } return 0; }
Codeforces Round #367 (Div. 2) E. Working routine
問題
N*M のグリッドが与えられる。各クエリで 「(a, b), (c, d) を左上の頂点とする高さ h, 幅 w の領域を交換する」ということをする(ただし, 交換する長方形は辺やセルを共有しない)。
全てのクエリを処理した後の最終的なグリッドの状態を求めよ。
解法
リストの考え方を応用すると解けます。
各ノードに「左隣, 右隣, 上隣, 下隣」のノードを覚えてもらうと, 領域内のほとんどのセルは隣接するセルが変化せず, 領域の周りのセルだけ隣接関係が変わっていることに注意すると, 各クエリは O(N+M) で処理できます。下の図を見ると多少イメージがわくと思います。
隣接関係の更新の仕方(というか順番)は工夫しないと簡単にバグるので注意です。
const int MAX = 1010; struct Node { Node() {init();} Node(int r, int c) : r(r), c(c) {init();} void init() { right = NULL; left = NULL; top = NULL; bottom = NULL; } int r; int c; Node* right; Node* left; Node* top; Node* bottom; }; Node* nodes[MAX][MAX]; int board[MAX][MAX]; int N, M, Q; // node1 <-> node2, node3 <-> node4 void changeNode1(Node* node1, Node* node2, Node* node3, Node* node4) { node1->right = node4; node3->right = node2; node2->left = node3; node4->left = node1; } // node1, node3 // node2, node4 void changeNode2(Node* node1, Node* node2, Node* node3, Node* node4) { node1->bottom = node4; node3->bottom = node2; node2->top = node3; node4->top = node1; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> Q; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> board[i][j]; for (int i = 0; i <= N+2; i++) for (int j = 0; j <= M+2; j++) nodes[i][j] = new Node(i, j); for (int i = 0; i <= N+1; i++) { for (int j = 0; j <= M+1; j++) { if (i) nodes[i][j]->top = nodes[i-1][j]; if (j) nodes[i][j]->left = nodes[i][j-1]; nodes[i][j]->right = nodes[i][j+1]; nodes[i][j]->bottom = nodes[i+1][j]; } } while (Q--) { int a, b, c, d, h, w; cin >> a >> b >> c >> d >> h >> w; Node* root1 = nodes[a][0]; Node* root2 = nodes[c][0]; for (int i = 0; i < b; i++) root1 = root1->right; for (int i = 0; i < d; i++) root2 = root2->right; // 上辺, 右辺 { Node* now1 = root1; Node* now2 = root2; for (int i = 0; i < w; i++) { changeNode2(now1->top, now1, now2->top, now2); now1 = now1->right; now2 = now2->right; } for (int i = 0; i < h; i++) { changeNode1(now1->left, now1, now2->left, now2); now1 = now1->bottom; now2 = now2->bottom; } } // 左辺, 下辺 { Node* now1 = root1; Node* now2 = root2; for (int i = 0; i < h; i++) { changeNode1(now1->left, now1, now2->left, now2); now1 = now1->bottom; now2 = now2->bottom; } for (int i = 0; i < w; i++) { changeNode2(now1->top, now1, now2->top, now2); now1 = now1->right; now2 = now2->right; } } } for (int i = 1; i <= N; i++) { Node* root = nodes[i][0]; for (int j = 0; j < M; j++) { root = root->right; int r = root->r, c = root->c; r--; c--; cout << board[r][c] ; if (j < M-1) cout << " "; } cout << endl; } return 0; }
Codeforces Round #368 (Div. 2) D. Persistent Bookcase
これ普通に頭良いと思うんだけどみんな解いてるんだよなぁ…
問題
最初すべてのセルが塗られていないグリッドが与えられる。以下の Q 個クエリを処理し, グリッドで黒色のセルの数を出力せよ。
- i 行 j 列目のセルが白なら黒くする。
- i 行 j 列目のセルが黒なら白くする。
- i 行目の白黒を反転させる。
- クエリの q 個目の状態に戻す。
解法
あらかじめどういうクエリが来るかはわかっているので, 「クエリの q 個目の状態に戻す」というのが来たときどこに戻れば良いかを覚えておけば, 基本的にはクエリの木構造ができています。木構造に合わせて, 素直にクエリを処理していけば O(NQ) 程度でできます。
const int MAXQ = 100100; int N, M, Q; int T[MAXQ], I[MAXQ], J[MAXQ]; int ans[MAXQ]; int reff[MAXQ]; vector<int> G[MAXQ]; bool board[1010][1010]; int S; void dfs(int v) { ans[v] = S; for (int ch : G[v]) { if (T[ch] == 1) { bool prv = board[I[ch]][J[ch]]; if (!board[I[ch]][J[ch]]) { S++; } board[I[ch]][J[ch]] = true; dfs(ch); board[I[ch]][J[ch]] = prv; if (!prv) S--; } else if (T[ch] == 2) { bool prv = board[I[ch]][J[ch]]; if (board[I[ch]][J[ch]]) { S--; } board[I[ch]][J[ch]] = false; dfs(ch); board[I[ch]][J[ch]] = prv; if (prv) S++; } else if (T[ch] == 3) { for (int i = 0; i < M; i++) { if (board[I[ch]][i]) { S--; board[I[ch]][i] = false; } else { S++; board[I[ch]][i] = true; } } dfs(ch); for (int i = 0; i < M; i++) { if (board[I[ch]][i]) { S--; board[I[ch]][i] = false; } else { S++; board[I[ch]][i] = true; } } } else { assert(0); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> Q; for (int i = 1; i <= Q; i++) { cin >> T[i] >> I[i]; if (T[i] <= 2) cin >> J[i]; if (T[i] <= 3) I[i]--; J[i]--; } int now = 0; for (int i = 1; i <= Q; i++) { if (T[i] <= 3) { G[now].emplace_back(i); now = i; reff[i] = i; } else { now = reff[I[i]]; reff[i] = now; } } dfs(0); for (int i = 1; i <= Q; i++) cout << ans[reff[i]] << endl; return 0; }
AtCoder Regular Contest 061 F - 3人でカードゲーム / Card Game for Three
解法
まず普通に解法を考えます。一度それぞれのカードを決めたらすでにゲームの勝敗は決まっていることを考えるとなんか dp ではないような気がします。で, 問題の性質をよく考えると A さんが勝つには A さんに N 回ターンが回ってくれば良いことに気付きます。また, B, C が勝たないためには, B, C さんにそれぞれ M+1 回, K+1 回, ターンが回ってきてはいけないことに気付きます。つまり, 解法としては,
- 'b' が M+1 回, 'c' が K+1 回出る前に 'a' が N 回出るような N+M+K 枚のカードの並べ方は何通りあるか？
という問題に帰着します。
まず部分点のほうを考えましょう(下のコードでコメントアウトされているのがそれです)。
'b', 'c' の出る回数をそれぞれ m, k とします。この場合は, 'b' が m 回, 'c' が k 回, 'a' が N-1 回出たのちに 'a' が 1 回出る, で後はどうなっていても良い, という感じになるので,
comb[N-1+m+k][N-1] * comb[m+k][m] * 3^(M+K-m-k)
通りあります。これを m, k 全ての場合について数えれば良いです。
次に満点解法のほうを考えます。上の式をよく見ると, 「m+k」というのがいろんなところに出ていて, comb[m+k][m] の m, k に対する和さえ求められれば後は m+k に関する式になっているので m+k について全探索するだけで行けることに気付きます。
ということで comb[m+k][m] の m に関する和を求める方法を考えます。M=2, K=4 の場合について和を求める場所を考えると下の図のようになています。
i 行目から i+1 行目の和を考える際には, 漸化式 comb[n+1][r] = comb[n][r] + comb[n][r-1] を考えると, i+1 行目に移るときほとんど和が 2 倍になっていることが分かります。端っこのところだけ微妙にずれることがありますが, そこは適当にうまくやります。
ll mod_pow(ll x, ll p, ll MOD) {
ll a = 1;
while (p) {
if (p%2) a = a*x%MOD;
x = x*x%MOD;
p/=2;
}
return a;
}
// mod_inverse
ll mod_inverse(ll a, ll m) {
return mod_pow(a, m-2, m);
}
const int MOD = 1e9+7;
const int MAX = 1000000;
ll fact[MAX], rfact[MAX];
ll p3[MAX];
ll nCr(int n, int r) {
return fact[n]*rfact[r]%MOD*rfact[n-r]%MOD;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
fact[0] = rfact[0] = 1;
for (int i = 1; i < MAX; i++) {
fact[i] = i*fact[i-1]%MOD;
rfact[i] = mod_inverse(fact[i], MOD);
}
p3[0] = 1;
for (int i = 1; i < MAX; i++) {
p3[i] = p3[i-1]*3%MOD;
}
int N, M, K;
cin >> N >> M >> K;
ll ans = 0;
// for (int m = 0; m <= M; m++) {
// for (int k = 0; k <= K; k++) {
// ll tmp = fact[N-1+m+k];
// (tmp *= rfact[N-1])%=MOD;
// (tmp *= rfact[m])%=MOD;
// (tmp *= rfact[k])%=MOD;
// (tmp *= p3[M+K-m-k])%=MOD;
// (ans += tmp) %= MOD;
// }
// }
ll sum = 1;
int low = 0, high = 0;
for (int i = 0; i <= M+K; i++) {
ans += nCr(N-1+i, N-1)*sum%MOD*p3[M+K-i]%MOD;
int nh = min(i+1, M);
int nl = max(0, i+1-K);
sum = 2*sum;
if (low < nl) sum -= nCr(i, low);
if (high == nh) sum -= nCr(i, high);
sum = (sum%MOD+MOD)%MOD;
high = nh;
low = nl;
}
ans %= MOD;
cout << ans << endl;
return 0;
}
