CODE FESTIVAL 2016 に参加しました
タイトル通りです。思ったことをつらつら書いていきます。
1 日目
家から追い出されたのでちょっと早めに家を出ると案の定早く着きすぎた。
来ちゃった♥ pic.twitter.com/r5pIBd4dUS
— マヨ子@大天使クサハエル (@mayoko_) 2016年11月26日
暇だったのでちょっと周りをブラブラしましたが面白いものは電通しかありませんでした。
会場に着いて暇だったので雪の宿を yazaten さんと btk さんにあげたりクソなぞなぞコンテストを作ったりしていました。12/11 に行う予定です。よろしくお願いします。
https://t.co/czhBapNrSv
— マヨ子@大天使クサハエル (@mayoko_) 2016年11月26日
12/11 21:00 から 1 時間の予定です
メインメニューのコンテスト。1600 点でパーカーがもらえるらしいというのと配点からまずは ABCDe を解くことを目標にしました。
- A 問題: はい。
- B 問題: 最初 N 点「以上」だと思って超簡単な貪欲じゃんと思ったら WA して「は？」と言ったけど適当に二分探索して通した。
- C 問題: 「多分連結っていうので良くね？」と思って提出したら AC して良かった。AtCoder の配点はよくわかりませんがいつもの 400 に比べると簡単だった。
- D 問題: これはちょっと迷った。しばらく考えた後,
- M で割ったあまりで考える
- M で割ったあまりについて, 奇数個余っているようなものについて注意する
- M で割ったあまりが i <-> M-i となるようなものをペアにしてごにょる
- みたいな方針でできることに気づいて, 適当にやったらサンプルあったので提出したら AC した。これはバグらせるかと思ったのでラッキーだった(ここで詰まって終了した人もいたらしいけど, 辛そう)。
- E 問題: 適当に dfs 枝刈りしたら部分点はとれた。満点をしばらく考えていたけどわからなかったので 次の問題を見る。
- H 問題: 次の部分点なのでちょっと見たが難しそうだったのであまり真面目に取り組まなかった。
- F 問題: 一瞬である程度の方針が立ったので簡単な気もする。最初に思いついた方針は少し間違えてたけどまぁ修正できる範囲で, 普通に AC。これはうれしかった。
後は E の満点, H の部分点を考えててた(特に E ばっかり考えてた)けどわからず終了。去年は面白い問題に取り組む前に終了してた感じだったけど今年はそこそこ楽しめたので良かったです。無事パーカーももらえたしハッピー。
後はごはん食べたりペアコーディング見たりエキシビジョンマッチみたりしました。
- AC 画像について, ガーリッシュナンバーに変更したのは良くないという意見を受けました。
- エキシビジョンはちょっと考えたけどわからず…海外勢が 0 完太陽だったのは面白いですね。
最後リレーでよろしくお願いしますするときに英語離せないの辛いなーってなりました。tozangezan さん普通に話せててすごいなぁと思いました。
2 日目
トーナメントは B 問題が簡単そうだったので 400/600 を狙ってたんですがバグって終了。0 完太陽でした。
A 問題の最小全域木作ってあらかじめ i から j への最大コストとか覚えておくののテクニックとかアルゴリズム的正当性がすごい頭良いなぁと思いました。
トーナメントは割と難しい問題だった気がするので 45 分 2 セットでも良かったような気がします。あんまり消化しきれてない感じが。
あと Round2 の A も 1 行でかけると聞いて考えてたんですがこれも面白かったですね。後で chokudai さんに賢い考え方を教えてもらいました。ところでいまだにいろはちゃんと chokudai さんの違いが分かってない。誰がやってるんだ。
その後のトークは kyuuri さんの LT とりんごさんのクイズが面白かったです。snuke さんがクソなぞなぞに言及してたのはなんとなくうれしかったです。
最後にリレーがありました。本選でまぁまぁいい順位だったせいで I 問題を割り当てられました。が, 普通に難しくてわからなかったので海外勢に教えてもらいました。すごい。ここでも英語できないの辛かったですね…
ところで I 問題は書くべきことを記憶するのが非常に面倒なロシアゲーだったのでメモを持っていくのを許可してほしい感じがありました。頭の中で解法を思い起こしながらコード書いてたら「ﾏﾀﾞｰ?」みたいなこと言われてすまぬ…となりました。
後から考えると
- クソなぞなぞ談義したかった
- ハル研プロコンの話もうちょっとしたかった
- コンテンツ別のやつもうちょっと楽しみたかった
とかいろいろやればよかったと思うことありますが楽しかったです。運営の方々本当にありがとうございました。
ハル研プロコン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; }
