IBM Quantum Challenge 2020 参加記
はじめに
2020/11/8 から3週間開催された IBM Quantum Challenge に参加しました.せっかくなので記事に残しておきます.今後参加する人も増えそうなので,参考になればと思います.
各問題についてのコメント
第1週 問題a
基本的な量子ゲートの説明から入り,加算器を実装するのが問題 a の課題です.去年も同じような導入でした.
この問題に関しては資料を読めばつまる所もないと思うのでノーコメント.
第1週 問題b
グローバー探索のちょうどよいイテレーション回数を求める問題です.去年はもうちょっとブラックボックス感があったきがする(よく覚えてない)のですが,今回のような設定にしたほうが教育的で良いと思いました.
グローバー探索は資料にもあるとおり,候補の空間を欲しい答えが張る部分空間とそれと直交する部分空間の2次元で表現した上で,探索対象のベクトルに関する各種操作を自分で図示すると理解が進むと思います.
第2週 問題a
グローバー探索で 3x3 のライツアウト問題を解け,という問題です.
オラクルとしては,解の候補(どのボタンを押すかの 9 個の量子ビット)の各ビットをみて,そこを押したら反転する入力のセル(ビット)を対象に cx ゲートを適用するだけです.
解となる要素は入力データ部分が全部 0 になってるわけですから,X ゲートで反転して全部の and を取ればよいわけですね.
探索空間は 2^9 なので大体 17 回やればほとんどアタリだけ引くことができるようになります.
最適化も含めて考えれば去年の本番の問題よりちょっと簡単目ぐらいの難易度に感じました.
第2週 問題b
qRAM を用いて複数の入力データを重ね合わせることで,4つのライツアウト盤面から高々3回のボタンを押してクリアできるものを見つける,という問題.
入力が複数個になっていること,単にそれぞれのライツアウトを解くだけでなく高々3回で解けるものだけを見つける必要があることなど,考えることが増えて少しむずかしいです.
オラクルの中で問題 2a のグローバー探索をするというのが去年には無い方法だったので,かなり勉強になりました.僕はこれにしばらく気が付かず,半日ほど時間を溶かしました.
内側のグローバー探索の直後では探索空間が大体4個*1になるため,diffusion 回路をアドレス部分に関してやれば十分ということです.そのため(外側の)グローバー探索のイテレーション回数は1で済みます.
外側のオラクルは 9 個の 1bit データを全部足すカウンタを使います.可逆にしないといけないという点では古典と異なりますが,ほとんど HW の回路を組むのと一緒です.
和を記録しておくのに愚直にやれば4ビット必要ですが,これ全部を補助ビットから賄うともったいないので,下位1ビットは和を取りたいビットの1つ目を直接入れておくようにすると補助ビットを1つ節約できます.補助ビットが余っていればいるだけ uncomputation がサボれるため,量子ビット数がギリギリな設定ではこういう工夫が効いてきます.
https://github.com/Suikaba/ibm-quantum-challenge-2020/blob/master/ex2b.py
いやしかし難しいなあ.*2
第3週(最終問題)
いよいよ本番です.この週は予定がありまくりで時間を無理やり捻出しました*3.
問題は競プロ勢にはおなじみの以下のような問題.
あなたはレーザーを持っていて,3発まで打てる.このレーザーは行 or 列の一直線上にある惑星を同時に破壊できる.
16個のグリッドのうち,クリアできないグリッドをグローバーのアルゴリズムによって特定せよ.ただし,
これが2部グラフの最大マッチングに対応するのはもはや常識ですが,今回はこれを量子回路で解く必要があります.
去年の感じだとルールをかなり忖度しないと本テストで簡単に reject されてしまうので,こういうのを想定してるんだろうなーという方向で最適化する解答を先に載せます.
自分の解法(ルール準拠)
この解法ではいかなる古典的な知識も用いず,また問題の解の存在条件の言い換えなども行いません.
量子ビットの用途は以下のとおり.
- アドレス(4bit)
- 惑星データ (6bit)
- レーザーデータ (8bit)
- オラクル用補助ビット (1bit)
- 補助ビット (9bit)
惑星データは入力を見て座標に対応する2つのレーザーに対応するビットの or をとったものになります.
次はアルゴリズムの流れについて.自分はグローバー探索を3段組にしました.
1. 一番内側のグローバー探索ではちょうど3発レーザーを打っているものを探索(入力データに依存しない)
2. 2段目のグローバー探索では上の条件に加え,盤面をクリアできるものを探索(入力データに依存)
3. 一番外側では上で見つけた解答の部分だけ符号反転.具体的にはちょうど3発打っているものだけ反転すればいい感じになる.
Slack チャンネルを見ている限り,3段目の部分で詰まっている人が多いのかなという印象を受けました.
僕の理解が正しければ,グローバー探索はアタリを引くアルゴリズムですが,逆にハズレよりアタリのほうが遥かに多い場合にはハズレを引くアルゴリズムということもできます.今回はハズレが1個でアタリが15個あるので,アタリ部分だけ狙い撃ちして反転できれば目的を達成できます.
また,1段目と2段めを分けたのは惑星データのストアの回数を若干少なくするためです.
このストア部分は入力データ 16 x 6 回のループを回す必要があり,そこそこ cx ゲートを使うのでできるだけ少ないほうが嬉しいです.でもよく考えたらあんまり変わってないかもしれません.悲しいね.
一番良いのは問題 2b のようにストアする部分がイテレーションの外側に出ていることなのですが,今回はそれができなかったのでこのような形になりました.
僕の実装では最適化を頑張っても 244k 程度のコストになりました*4.個人的には opt_is_count3 あたりの実装が気に入っています.その他も ancilla ビットを使い切ってできるだけ uncomputation が発生しないように努めているつもりです.
うーんしかし惑星データのストア部分を外に出せないと 100k 切るのは夢物語ですね.でもみんな 100k 当たり前のように切ってるんだよなあ.なにがいけないのかなあ.
別解その1(多分ルール非準拠,未提出)
unsolvable な盤面を直接求めに行く方針です.*5
結論を言えば,8-queen's problem ならぬ 4-queen's problem のようなものに言い換えられます.
すなわち解き方としては
- 0~3 の長さ4の順列を生成する.i 番目の数 p[i] が (i, p[i]) のセルに対応する.
- 盤面のうち順列に対応する位置すべてに惑星があるかチェックする.これは順列との or をとってカウントが4かどうかで判定可能
という流れで解けます.この解き方の問題点は outermost の探索空間が 2^2 * 24 通りあるために1回のイテレーションでは十分な確率で解を得るのが難しいことです.せめて3回ぐらいまわせればそれっぽくなるんですけどね.
実装したところ,回路の最適化なしでも1回イテレーションするだけなら 40k 程度のコストになりました.
別解その2(ルール非準拠)
別解1をより進めます.盤面には高々 6 個の惑星しか無いので,4つの行のうち少なくとも2つの行には惑星が1つしかありません.
したがって,前処理で盤面の行・列をいい感じに swap すれば,盤面で考えるべきは以下の x の部分だけになります.
xooo
oxoo
ooxx
ooxx
左上2箇所は決め打ちできるので,右下2パターンについてだけ探索すればよく,探索空間が小さくなるためイテレーション1回でも相当高確率で解が得られます.
また回路規模も(特に最適化なしで)16k ぐらいになります.
これ結構気に入っていたのですが,禁止されちゃって悲しかった.
ちなみにコンテスト中の1位の記録が 10k を切っていたのですが,こういうズルなしでやってるんだとしたら本当にすごいです.全く思いつかないよ.
その他のこと
まとめ
全然だめだったけど今年も楽しかった~.運営の皆様お疲れさまです.
競プロ勢とも相性いいと思うので,参加したことのない人は来年は出てみてはいかがでしょう.初心者でも楽しめるはず.
ただルールが結構ガバガバだったり,システムが不安定*7だったりするので,そういうのが嫌な人は見送ったほうが良いかもしれません.システムはそのうち洗練されていくものですし,今後も続いていけば良いなあと思います.来年も楽しみにしています.
ICPC2020 国内予選 参加記
はじめに
2020/11/7 に行われた ICPC 国内予選に suibaka, nakano, otera1999 の3人で参加しました.
結果は 29位 と力及ばず,ここ3年で最も低い順位をとってしまいました.
この結果,僕と nakano は今回で引退となります.せっかくなので記録を残しておきます.
コンテスト中の流れ
僕が B, D, E をやって,otera くんが A, C, F をやっていました.nakano は考察担当で実装はしません.
以下僕が解いた分の問題の流れをば(A, C, F は読んですらいないので全く知らない).
- B 問題
- これ直前に Twitter かなんかで同じ問題なかったっけ?と思いながら適当に書くと WA になり,めっちゃたまげた
- 無限に悩んで,挙げ句考察担当に(B問題なのに)合ってるか確認する始末…
- 結果だけいうと,提出するファイルを間違えていただけだった.提出担当やめろ
- D 問題
- n が小さかったんで bitDP でできたりしない?
- 一個ずつ決めていく方針だと後ろの未確定の分で困るね.うんうん
- nakano が答え決め打ちしてそれ以外の文字が前と後ろどちらにあるかだけ決めればいいんでは?という.すげー
- サクッと実装して,終わり.(終わってから思ったんですけどこの問題結構好きです.
- E 問題
- 独立集合の数え上げ.むずそー
- nakano と考えていると,斜め方向で状態を考えれば,隣接する2つは選べないので状態数が fib(n/2) ぐらいになって嬉しいねとなる
- 斜め方向なのでちょっと実装方針に悩む
- 詰めて書いたところ,なんかバグる -> ループを m / 2 回回していたが,左上から右下まで見るので m 回回さないとだめだった.
- サンプルが合うので,ぶん回す -> なんと間に合わないままコンテスト終了
- 計算量は大体 m * n * fib(n/2) だが,dp テーブルを unordered_map (or map) で管理しているので定数倍 (or log) の分重い
- 4分割してそれぞれで解くのでこれに 4 倍がつき,さらにテストケース数分あるので冷静になると,確かに間に合わないかもなという気もする
AOJ 1629 正三角形の柵 (Equilateral Triangular Fence)
解法
底辺の y 座標を決めうったとする.これを \(y_l\) とおく.
\(y \geq y_l\) をみたすある点 \((x, y)\) が正三角形の内部にあるための条件は,底辺の左端と右端の x 座標(それぞれ \(l_x, r_x\) とおく)が
\[
x - y/\sqrt{3} + y_l/\sqrt{3} \leq lx \land rx \leq x + y/\sqrt{3} - y_l/\sqrt{3}
\]
を満たすときである.これは1次元上の条件である.
したがって,前処理として \(x - y/\sqrt{3}, x + y/\sqrt{3}\) のそれぞれで点をソートした列をもっておき,左端を決めて右端を伸ばしていくしゃくとりを行えば解くことができる.
\(y_l/\sqrt{3}\) の分は全体に同じだけかかるオフセットなので,前処理のソートによる順番に影響しない.区間さえ求めたら,オフセット分を長さから引いてやれば良い.
特に何も考えず実装すると,計算量は \(O(nk + n\log n)\) となる.
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr double eps = 1e-9; constexpr double inf = 1e9; const double sq3 = sqrt(3); int main() { cout << fixed << setprecision(10); int n; while(cin >> n, n) { int k; cin >> k; vector<int> x(n), y(n); vector<pair<double, int>> lx(n), rx(n); for(int i = 0; i < n; ++i) { cin >> x[i] >> y[i]; lx[i] = make_pair(x[i] - y[i] / sq3, i); rx[i] = make_pair(x[i] + y[i] / sq3, i); } sort(lx.begin(), lx.end()); sort(rx.begin(), rx.end()); double res = inf; vector<int> used(n); for(int ly = 1; ly <= 10000; ++ly) { if((int)lx.size() < n - k) break; fill(used.begin(), used.begin() + lx.size(), 0); int l = 0, r = 0, cnt = 0; while(l < (int)lx.size()) { while(cnt < n - k && r < (int)rx.size()) { cnt += ++used[rx[r++].second] == 1; } if(cnt == n - k) { res = min(res, rx[r - 1].first - lx[l].first - 2 * ly / sq3); } const double cur_x = lx[l].first; while(l < (int)lx.size() && abs(cur_x - lx[l].first) < eps) { cnt -= --used[lx[l++].second] == 0; } } auto rm_pred = [&] (auto const& p) { return y[p.second] == ly; }; lx.erase(remove_if(lx.begin(), lx.end(), rm_pred), lx.end()); rx.erase(remove_if(rx.begin(), rx.end(), rm_pred), rx.end()); } cout << 3 * res << endl; } }
AOJ 1623 等積変形 (Equivalent Deformation)
解法
点を合わせる順番と対応を全部試して探索するだけで解ける.
点を合わせるときは,直接合わせられる場合は直接合わせればよいし,そうでない場合は残りの2点のどちらかを適切に移動させてから合わせればよい.このとき2点のどちらを選ぶかは両方試す.
ソースコード
#include <bits/stdc++.h> using namespace std; using ld = long double; using point = complex<ld>; constexpr ld eps = 1e-8; struct line { point a, b; }; bool eq(ld a, ld b) { return std::abs(a - b) < eps; } ld cross(point a, point b) { return imag(conj(a) * b); } bool isis_ll(point v1, point v2) { return !eq(cross(v1, v2), 0); } point is_ll(line s, line t) { point sv = s.b - s.a, tv = t.b - t.a; return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv); } int main() { vector<int> x1(3), y1(3); while(cin >> x1[0] >> y1[0]) { for(int i = 1; i < 3; ++i) cin >> x1[i] >> y1[i]; vector<int> x2(3), y2(3); for(int i = 0; i < 3; ++i) cin >> x2[i] >> y2[i]; function<int(int, vector<int>, vector<point>, int)> dfs = [&] (int i, vector<int> match, vector<point> ps, int step) { if(step >= 5 || i == 3) return step; auto vec = point(x2[match[i]], y2[match[i]]) - ps[i]; auto p2 = ps[(i + 1) % 3], p3 = ps[(i + 2) % 3]; auto vec2 = p2 - p3; if(!isis_ll(vec, vec2)) { ps[i] = point(x2[match[i]], y2[match[i]]); return dfs(i + 1, match, ps, step + 1); } else { int res = 5; { auto tmp_ps = ps; line l1{p2, p2 + ps[i] - p3}; line l2{p3, p3 + vec}; auto pp = is_ll(l1, l2); tmp_ps[(i + 1) % 3] = pp; tmp_ps[i] = point(x2[match[i]], y2[match[i]]); res = min(res, dfs(i + 1, match, tmp_ps, step + 2)); } { auto tmp_ps = ps; line l1{p3, p3 + ps[i] - p2}; line l2{p2, p2 + vec}; auto pp = is_ll(l1, l2); tmp_ps[(i + 2) % 3] = pp; tmp_ps[i] = point(x2[match[i]], y2[match[i]]); res = min(res, dfs(i + 1, match, tmp_ps, step + 2)); } return res; } }; vector<int> ord(3); iota(ord.begin(), ord.end(), 0); int ans = 5; do { vector<int> match(3); iota(match.begin(), match.end(), 0); do { vector<point> ps(3); for(int i = 0; i < 3; ++i) ps[i] = point(x1[ord[i]], y1[ord[i]]); ans = min(ans, dfs(0, match, ps, 0)); } while(next_permutation(match.begin(), match.end())); } while(next_permutation(ord.begin(), ord.end())); if(ans == 5) cout << "Many" << endl; else cout << ans << endl; } }
感想
こういうの,本番だと難しく見えるんですよね….
AOJ 2559 Minimum Spanning Tree
解法
マージテクだけで解ける.
最初に MST を構成しておく.MST に含まれない辺は自明.
以下MSTに含まれる辺についてコストを求める.
MST 上を DFS で探索し,各部分木から外に生えていく辺を全部求めていく.
外に出ていく辺としては以下の2通りある.
- 行き先は別の部分木の頂点(先祖ー子孫の関係にない)
- 行き先が祖先
どちらの場合も同じやり方で処理できる.
DFS の戻り値として,その部分木から外に出ていくすべての辺を返すことにする.
DFS の過程で今頂点 v にいるとすると,
- 辺集合の格納先を res とする.
- 各部分木に対して辺集合を求め,マージテクで res と併合する.このとき,intersect する場合は削除するようにし,そうでない場合は挿入するようにする.
- v から出ている(MST上にない)すべての辺 e に対して,e が res にあれば削除,なければ挿入する.
- res を返す
ステップ2が「行き先が別の部分木の頂点の辺」を打ち消す操作,ステップ3が「行き先が祖先の辺」を打ち消す操作に対応する.
res を set で管理すれば,マージテクしながら削除にも対応できる.このとき,辺の順序は (cost, idx) で持っておけば良い.
計算量は O(n + m(logm)^2) である.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; class union_find { public: union_find(int n) : par(n, -1) {} int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); } bool unite(int x, int y) { x = root(x), y = root(y); if(x == y) return false; if(par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } private: vector<int> par; }; struct edge { int from, to, cost, idx; bool operator<(const edge& e) const { return make_pair(cost, idx) < make_pair(e.cost, e.idx); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<vector<edge>> g(n); vector<edge> es; for(int i = 0; i < m; ++i) { int a, b, w; cin >> a >> b >> w; a--, b--; g[a].push_back(edge{a, b, w, i}); g[b].push_back(edge{b, a, w, i}); es.push_back(edge{a, b, w, i}); } sort(es.begin(), es.end()); vector<vector<edge>> mst(n); vector<bool> in_mst(m); vector<ll> ans(m, -1); ll mst_cost = 0; { union_find uf(n); for(auto const& e : es) { if(uf.unite(e.from, e.to)) { in_mst[e.idx] = true; mst_cost += e.cost; mst[e.from].push_back(edge{e.from, e.to, e.cost, e.idx}); mst[e.to].push_back(edge{e.to, e.from, e.cost, e.idx}); } } for(int i = 0; i < m; ++i) { if(!in_mst[i]) { ans[i] = mst_cost; } } } function<set<edge>(int, int)> solve = [&] (int v, int p) { set<edge> res; vector<set<edge>> buf_es; for(auto const& e : mst[v]) { if(e.to == p) continue; auto tmp_es = solve(e.to, v); tmp_es.erase(e); if(!tmp_es.empty()) { ans[e.idx] = mst_cost - e.cost + tmp_es.begin()->cost; } if(res.size() < tmp_es.size()) swap(res, tmp_es); for(auto const& e : tmp_es) { if(res.count(e)) res.erase(e); else res.insert(e); } } for(auto const& e : g[v]) { if(in_mst[e.idx]) continue; if(res.count(e) == 1) res.erase(e); else res.insert(e); } return res; }; solve(0, -1); for(auto const x : ans) { cout << x << "\n"; } }
感想
重心分解の例題で見かけたので復習がてら解いたのですが,重心分解いらないじゃんとなってしまい悲しい.
AOJ 2907 Prefix Suffix Search
解法
\(w_i\) をそれぞれ逆にした文字列集合を \(\{rw_i\}\) とする.
最初にそれぞれをもともとのインデックスが分かるようにソートしておく.
以降は \(w_i, rw_i\) はソート済みであるとする.
各 \(i\) に対して,\(w_i\) のもともとのインデックスに対応する文字列が \(rw_j\) であるとする.
すると,\((0, j_0), (1, j_1), \ldots, (n, j_n)\) という2次元上の点列が得られる.
各クエリ \(p, s\) に対して,\(p\) (あるいは \(s\))の条件を満たす文字列集合は,\(w_i\) (あるいは \(rw_i\))における1つの連続区間とみなすことができる.
\(p, s\) に対応する区間をそれぞれ \([l_1, r_1], [l_2, r_2]\) とする.
すると,先の2次元上の点列と合わせて,以下の値を求められれば良い.
\[\# \{ j_i ~| ~l_1 \leq i \leq r_1, l_2 \leq j_i \leq r_2\}\]
これは WaveletMatrix やマージソートをセグメント木っぽく行うデータ構造などで高速に処理することができる.ICPC など写経が必要なら計算量は不利だが後者を選ぶとよいだろう.
また,\(p\) や \(s\) に対する区間を求めるのは単純に二分探索すれば計算量的にも問題ない.
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename T> class merge_tree { public: merge_tree(std::vector<T> const& v) : n(size(v.size())), dat(n * 2) { for(int i = 0; i < (int)v.size(); ++i) { dat[i + n].push_back(v[i]); } for(int i = n - 1; i >= 0; --i) { std::merge(dat[i * 2].begin(), dat[i * 2].end(), dat[i * 2 + 1].begin(), dat[i * 2 + 1].end(), std::back_inserter(dat[i])); } } // in [l, r), the number of values larger than lb int count(int l, int r, T lb) { l += n, r += n; int res = 0; while(l < r) { if(l & 1) res += count(l++, lb); if(r & 1) res += count(--r, lb); l >>= 1, r >>= 1; } return res; } private: int size(int x) { int res = 1; while(res < x) res <<= 1; return res; } int count(int node_id, T lb) { return std::lower_bound(dat[node_id].begin(), dat[node_id].end(), lb) - dat[node_id].begin(); } private: const int n; std::vector<std::vector<T>> dat; }; int main() { using ps = pair<string, int>; int n, q; cin >> n >> q; vector<ps> ws(n), rev_ws(n); for(int i = 0; i < n; ++i) { cin >> ws[i].first; rev_ws[i] = ws[i]; ws[i].second = rev_ws[i].second = i; reverse(rev_ws[i].first.begin(), rev_ws[i].first.end()); } sort(ws.begin(), ws.end()); sort(rev_ws.begin(), rev_ws.end()); vector<int> ids(n); { // build ids vector<int> rev_ids(n); for(int i = 0; i < n; ++i) { rev_ids[rev_ws[i].second] = i; } for(int i = 0; i < n; ++i) { ids[i] = rev_ids[ws[i].second]; } } merge_tree<int> mt(ids); auto calc_range = [] (vector<ps> const& bag, string const& s) -> pair<int, int> { int lb = -1, ub = bag.size(); while(ub - lb > 1) { const int mid = (lb + ub) / 2; (bag[mid].first.compare(0, s.size(), s) < 0 ? lb : ub) = mid; } const int res_l = ub; lb = -1, ub = bag.size(); while(ub - lb > 1) { const int mid = (lb + ub) / 2; (bag[mid].first.compare(0, s.size(), s) <= 0 ? lb : ub) = mid; } return {res_l, ub}; }; while(q--) { string prefix, suffix; cin >> prefix >> suffix; reverse(suffix.begin(), suffix.end()); const auto [l1, r1] = calc_range(ws, prefix); const auto [l2, r2] = calc_range(rev_ws, suffix); cout << mt.count(l1, r1, r2) - mt.count(l1, r1, l2) << endl; } }
感想
久々に AOJ を使ったら C++17 が使えるようになっていてよかった.
LuaTeX で源ノ角フォントを使う
フォントのダウンロード
https://github.com/adobe-fonts/source-han-sans/tree/release
https://github.com/adobe-fonts/source-han-serif/tree/release
から日本語のやつを落としてくる.
ファイルの配置
texmf-local/fonts/opentype/adobe/SourceHanSans
texmf-local/fonts/opentype/adobe/SourceHanSerif
にそれぞれの .otf ファイル群を配置.
それから
$ mktexlsr $ luaotfload-tool --update
でおわり.確認は
luaotfload-tool --find="Source Han Sans Regular"
tex ファイル
tex ファイルの先頭に
\usepackage{luatexja} \usepackage[sourcehan]{luatexja-preset}
とすればよい.オプションは必要に応じてつける.
自分は no-math と deluxe をつけて使っている.
ところで
基本的にこれでうまくいくんだが,lualatex がやたらメモリを食う(具体的には 2GB ぐらい) ので困る.メモリは足りるけどそんなに使うか?
眺めていると,2回目以降はキャッシュされてマシになるっぽい.まあいいか.