略。
この問題は、150 * 60の$\mathbb{F}_2$ matrixであって、「行ベクトルを110個選んだときに、どう選んでもrankが60になる」ような行列を構築すれば解ける。
ところで、
https://arxiv.org/pdf/1404.3250.pdf
を見ると、ランダムに110 * 60選んだ行列がフルランクになる確率は$(1 - 1/{2^{51}})^{60}$以上らしい。
よって、テストケース数を30とすると失敗する確率は
$1/{2^{51}} * 60 * 30 * 1000$で抑えられ、これはEPS
脳内AC
JOI Open 2013 Synchronizationの人間的な解法を紹介します。
略
ある辺を追加すると、左右で互いに情報を交換します。この交換する個数を高速に求めたいです。
左が情報をa個、右がb個持っていて、そのうち共通のものがc個あったとします。 すると辺を追加した後、左右はつながり、合計でa+b-c個の情報を持ちます。
ところで、このcは、"その追加しようとしている辺がその前に繋がっていた時点での、左右の情報の個数"です。
以上より、辺ごとに最後につながっていた時点での左右の情報の個数を持つことにします。すると以下のようなクエリを処理できれば良くなります。
これはもう今の時代どうとでもなりますが(ex euler-tour-tree)、それは今回は使いません。
まず、木の形が固定であることを利用し、最初に根付き木にすると、
の3つができれば良くなります。連結成分のうち最も根に近い頂点の値が、その連結成分の値を表すこととします。
これはもう今の時代どうとでもなりますが、そのなかで実装の軽いeuler-tour 2Dを使用します。
これを利用すると、ノードにsetとかそこらへんを載せたsegtreeで解けることがわかります。
手元で1.9sで、まあ2xだと考えると、TLが4sぐらいならば間に合うと思うのですが、本番だとどのぐらいのTLだったのでしょうか。 まあsetをやめて、例えば先読みしてsegtreeとかにすればもっと速くなると思います。
よく考えると、RMQだけで実装できました。思考停止二分探索でlogが2個、segtree特有の二分探索高速化でlogが1個です。
今までのworld finalの問題6問セット*2時間だった。
1: 知らない 2: 球形の穴が沢山空いた直方体が与えられるので、k等分 3: 知らない 4: 重実装幾何 どぼじて 5: 平面状に点がたくさん与えられて最大クリーク 6: 420と見せかけて状態が少ないハフマン木構築
持ち込みたいもの(白紙、ライブラリ、筆記用具)は初日の登録セッションで渡しておかないといけない。期間中に練習をしたいなら、持ち込み用と練習用で分けて持っておく必要がある。白紙だけでなく方眼紙も持ち込めた。
むこうから支給されたのは、水500ml * 6本、昼ごはん3食、後ろに消しゴムの付いた鉛筆3本、ボールペン黒3本、ノートと大量の方眼紙が3セット
筆記用具はかなり貧弱なので、持ち込んだほうがいいと思う。 紙は使い切ることはまず無い量だったので、まあ紙質とか気にするなら
3人座れる長机、パソコンの位置は一番左
システムの情報はサイトに書いてある、重要な情報はスタックサイズ無限、C++14が使える、あたり？
キーボードは耐えられないほどではないがそこそこ打ちにくかった、本番だと2分ぐらいしかパソコンに触ってないから記憶が怪しいかも
コンテスト前の虚無タイムは相当長い
印刷のタイムラグは多分チームごとに相当差がある、印刷場に近い席なら相当速い(と思う)(今回だと名前順が遅いほど速い)。個人的にはクエリを送ってから印刷までのタイムラグは少なくて、それを運んでくる時間が律速(ゆっくり歩いて運んでくる)
印刷の方法はコマンドラインからprintfile A.cppみたいに叩く方式だった。不思議。
ジャッジ結果は結果以外何も見れなかった(一番厳しい方式)。得られる情報はジャッジ結果が帰ってくるまでのタイムラグぐらい。本来のkattisだと何番目のケースで落ちたかとか見れるが、今回はそれはないので注意。
思い当たるのはこのぐらいなので、他に知りたいことが合ったら教えてください
AGC 014 Fを解きました。
解いた後に解説動画を見たら全然違いました。ゴリ押しです。
まず、数列を-1倍してよくある各点までのLISを求めるやつをします。 たとえば[3, 5, 1, 2, 4]ならば、[1, 1, 2, 2, 2]です。これは"初めてその値が高い項になるのは何回目か？"を表します。
サンプル3:[2, 10, 5, 7, 3, 6, 4, 9, 8, 1]に対してやると、[1, 1, 2, 2, 3, 3, 4, 2, 3, 5]となります。
ここで、LISといえばRank分けですね、というわけで分けると、[2, 10], [5, 7, 9], [3, 6, 8], [4], [1]となりますね。
ここで、実はこれをこのまま結合した[2, 10, 5, 7, 9, 3, 6, 8, 4, 1]を数列の初期値としても答えが変わらないことが示せます。略します。
で、これを二次元平面にプロットしてみましょう。x座標はLISの値、y座標は数列の値です。
すると下図のようになります。
すると、"一番左の列の点たちを適切な位置に動かす"を繰り返すような操作になることに気づきます。 具体的には各点について、「自分より上の点について、自分より左の列から移動してきたような点」が存在しない列、のうち最も左側に動きます。
操作をすると下図のようになります。
ここで、上の点にしか移動が依存しないことを考えると、上から点を追加していく方針を考えたくなります。
要するに、各列について、その列に来た点のうちもっとも左側から来たものとの距離、を持って、その配列を管理しながらいい感じに処理をします。
各点についてどのような処理をするかというと、「配列の値 <= 移動距離」となるなかで最も近いものに移動し続けることになります。
もちろん愚直では間に合いませんが、ここで、配列の値が広義単調減少であることを利用します。
大体配列の値ずつぐらい移動することを考えると、今のいる場所の配列の値で平方分割することを考えたくなります。
具体的には「今いる場所の1マス先の配列の値」がsqrt以上かどうかで場合分けをすると、大きい間は愚直にバイナリサーチ、小さいとまとめて一気に動く、という操作を行えば良くなります。
計算量はO(NsqrtNlogN)と見せかけてO(NsqrtN)です。
久しぶりの参加記
うっかり遅刻した(いつもの)(ごめん)(反省がない)(受付時間で差を付けろ)(鈍足)
なんかsigmaとsugimにArrangement Tickets(JOIオープン)の僕の解法は嘘解法だとかいう言いがかりをつけられる。
問題を読んでる間に前の席のantaさんが実装を始めて怖かった
A問題はメモ化再帰やるだけっぽいのでとりあえず全探索書いたら一生答えが返ってこなかった。 でもまあメモ化したらサンプルがあったので提出。WA
よく考えたら遷移にループがありますねぇ！(気づき) 幸先が悪すぎる。 無理やり修正して投げたらAC。既にantaさんが2問解いてるんだけどバグかな？
FA狙うゾってCを読んだらsegtreeで解けると勘違い。書き終わったがサンプルが合わない(それはそう) よく考えると平方分割だったので書き直し。
C問題のWAが取れなすぎるので一回置いといてDEを読む。Dは解法自明実装激重だったが、この時点でペナルティも時間消費も激しすぎたのでDを捨ててABCEの4完を目指すことを決定。
C問題のデバッグと並行してE問題を考えると解けた。
が、Eもめちゃくちゃバグる。
Cを提出→結果待ちでEをデバッグして提出→結果待ちでCをデバッグして提出→…みたいになって冷えていた。
ACを見ることで精神衛生を保とうと放置してたBをパパっと解いたらWAして更に嫌な気持ちになった。
多分ジャッジルームで「こいつ冷えてるな～」とか言われてるんだろうなあと思いながらデバッグ。Bはすぐにバグが取れる。
CE両方ほぼ同時にバグを取りきるが両方TLEする(は？)
両方O(NsqrtNlogN)なのでオーダーが間違えてるのか？とは思ったがどうしようもないので両方定数倍改善することに。
E問題はsetを事前に用意していた超高速setに変更。無事AC。1654/2000ms
C問題はmodをif + 引き算にチマチマ書き換えたら無事AC。5443/6000ms
定数倍改善してる間にEのFAも取られるしもうめちゃくちゃですね。
恐ろしいWAが溜まっているがDを20分で解くのは厳しすぎるなあと思ってこれ以上誰もE通すな～～～って思いながらボーッとする。
さすがに頑張るかという気持ちになってDを実装したが、案の定間に合わず。
前半があまりにひどすぎたが、後半は最善の行動だった。
ところで商品なに来るか知らないんですが、何が来るんでしょう
あけましておめでとうございます！
— 最高の夏 (@maroon_kuri) January 1, 2017
↓はお正月問題のリンクです。
新年早々重い問題を解きたい方はぜひやってみてください。https://t.co/GH0VwifmvK
ヒント1 : FMTは使わない(MODが変な意味はない)
ヒント2 : 式の形は、個数に対応するハッシュではなく意味がある
@maroon_kuri そういえば、
— yosupo (@yosupot) 2017年1月3日
長さ200,000ぐらいの数列MとCが与えられるのでG(M)を求めよ、ただしF=|A|*M^|A|*sum(A_i)ではなく、F=C_|A| * sum(A_i)、クエリはなし
という問題が思考過程で生成されました(逆出題)
@maroon_kuri 要するにクエリがなくなった代わりにFがより複雑になったバージョンです
— yosupo (@yosupot) 2017年1月3日
解法があってるかは未検証です。
ヒント1 : 係数がどうしようもなくなったので、長さごとにその長さの数列たちの和を独立に計算します
ヒント2 : 「長さ200,000の数列(各要素は109とか)を全部かけてください、ただしModではなく多倍長でそのまま」 を普通に順番に掛けるより早く計算するにはどうする？
この記事はrogy advent calenderの3日目の記事です。
日本時間では4日になっているような気がしますが、地球上にはまだ3日の部分が残っているのでセーフです。
(本当は丁寧に書くつもりだったのですが、時間がないので、プロコンをしている人向けの記事になりました。悲しいね)
Fenwick Treeというデータ構造があります、これを高速化しようと頑張りました
調べればたくさん説明は出てくると思います。
数列について、
という操作が、どちらもO(logN)で出来るデータ構造です。
例えば普通に配列でやると、O(1) / O(N)、累積和を用いると O(N) / O(1) になります。
template<class T> struct Fenwick { int N; vector<T> seg; Fenwick(int N) : N(N) { seg.resize(N+1); fill_n(begin(seg), N+1, 0); } /// i番目の要素にxを追加する void add(int i, T x) { i++; while (i <= N) { seg[i] += x; i += i & -i; } } /// [0, i)のsum T sum(int i) { T s{0}; while (i > 0) { s += seg[i]; i -= i & -i; } return s; } /// [a, b)のsum T sum(int a, int b) { return sum(b) - sum(a); } };
まず、これがFenwick Treeのコードです。使いやすいように0-indexedになっています。
上記のコードを見てもわかるように、Fenwick Treeは非常に美しいデータ構造です。 そして定数倍も非常に速いです。これをさらに高速化することなど出来るのでしょうか？
まず、Nが大きく(100,000とか)なった時に、どこがボトルネックになるかを考えます。
メモリアクセスな気がします。log2(N) / 2 回バラバラなところにアクセスするので、これをどうにか減らせないでしょうか？
まず、Fenwick Treeではなく、普通の累積和を求めるSegment Treeで考えます。
考えると、2分木ではなく多分木にすればメモリアクセスの回数が減りそうな気がします。
例えば4分木にすれば、アクセスする場所は半分になります。代わりに、それぞれのノードにサイズ4のFenwick Treeを持たせる必要があります。
このFenwick Treeを愚直に配列/累積和で実装すると、そこが重くなります。 そして元々のFenwick Treeの綺麗な構造が消えるので、要するに遅くなります。
ポインタを使い、愚直に多分木を書いてみたのですが、もうハチャメチャ遅いです。
変なことをしようとすると、綺麗な構造が壊れてなんか逆に遅くなる、ということがわかりました。
予想していた通り、Fenwick Treeの高速化は難しいです。
なので、SIMD命令を使います。CPUはIntel 6700で、Intel AVX2を使用しています。
SIMD命令は、連続した要素に対して、一括で命令を行うことができます。
最近のはすごくて、ポインタの配列について、一括でその指す場所の値をgetできます(gather命令)
これにより、sum関数の高速化を図ります。
更に、8分木にして、ノードごとの累積和の計算を高速化します。
これにより、get関数の高速化を図ります。
/** * Fenwick Tree(0-indexed, int only) * X is height of tree */ template<int X> struct FenwickSimd { int *seg_base; int *(seg[X]); m256 segC; FenwickSimd() {} FenwickSimd(int N) { // N < 8**X assert(N < 1<<(3*X)); int S = 0; int segCbuf[8] = {}; for (int i = 0; i < X; i++) { N = (N+7)/8; segCbuf[i] = S; S += 8*(N+1); } seg_base = (int *)aligned_alloc(32, sizeof(int)*S); for (int i = 0; i < X; i++) { seg[i] = seg_base+segCbuf[i]; } segC = _mm256_load_si256((m256 *)segCbuf); } /// a[i] += x void add(int p, int x) { for (int i = 0; i < X; i++) { int dp = p&7, up = p&~7; const m256 pd = _mm256_set1_epi32(dp); const m256 base = _mm256_set_epi32(7,6,5,4,3,2,1,0); m256 xx = _mm256_set1_epi32(x); xx = _mm256_and_si256(xx, _mm256_cmpgt_epi32(base, pd)); m256 tar = _mm256_load_si256((m256 *)(seg[i]+up)); tar = _mm256_add_epi32(tar, xx); _mm256_store_si256((m256 *)(seg[i]+up), tar); p >>= 3; } } // sum [0, i) int sum(int p) { int s{0}; const m256 off = _mm256_set_epi32(21,18,15,12,9,6,3,0); m256 adr = _mm256_set1_epi32(p); adr = _mm256_srlv_epi32(adr, off); adr = _mm256_add_epi32(adr, segC); m256 buf = _mm256_setzero_si256(); const m256 mask = _mm256_set_epi32( 7<X?-1:0,6<X?-1:0,5<X?-1:0,4<X?-1:0, 3<X?-1:0,2<X?-1:0,1<X?-1:0,0<X?-1:0); buf = _mm256_mask_i32gather_epi32(buf, seg_base, adr, mask, 4); buf = _mm256_hadd_epi32(buf, buf); buf = _mm256_hadd_epi32(buf, buf); s += _mm256_extract_epi32(buf, 0); s += _mm256_extract_epi32(buf, 4); return s; } // sum [a, b) int sum(int a, int b) { return sum(b) - sum(a); } };
こちらが完成したコードになります。
適当にベンチマークした結果ですが、N=200,000だとget/sum共に2.5倍ほど速くなりました。すごい
でも2D Bitにすると遅かったり、なんかいろいろ難しいです。悩ましいですね
プログラムは、8分木を作って、getはgatherで各段から回収し、sumは各段の累積和を更新しています。
SIMD命令、適当に関数をウリャオイするだけで動いてすごい
