読者です 読者をやめる 読者になる 読者になる

maroonさんのお正月問題

ヒント1 : FMTは使わない(MODが変な意味はない)

ヒント2 : 式の形は、個数に対応するハッシュではなく意味がある

おまけ

解法があってるかは未検証です。

ヒント1 : 係数がどうしようもなくなったので、長さごとにその長さの数列たちの和を独立に計算します

ヒント2 : 「長さ200,000の数列(各要素は109とか)を全部かけてください、ただしModではなく多倍長でそのまま」 を普通に順番に掛けるより早く計算するにはどうする?

Fenwick Treeの定数倍高速化

Fenwick Treeの定数倍高速化

この記事はrogy advent calenderの3日目の記事です。

日本時間では4日になっているような気がしますが、地球上にはまだ3日の部分が残っているのでセーフです。

(本当は丁寧に書くつもりだったのですが、時間がないので、プロコンをしている人向けの記事になりました。悲しいね)

概要

Fenwick Treeというデータ構造があります、これを高速化しようと頑張りました

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の綺麗な構造が消えるので、要するに遅くなります。

ポインタを使い、愚直に多分木を書いてみたのですが、もうハチャメチャ遅いです。

変なことをしようとすると、綺麗な構造が壊れてなんか逆に遅くなる、ということがわかりました。

Intel AVX2

予想していた通り、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命令、適当に関数をウリャオイするだけで動いてすごい

Codeforces Technocup F: Dirty plates

概要

スタックが3こある

1 -> 2はa個まで一気に運べて、2 -> 3はb個まで一気に運べる。sortできるか?

解法

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

まず、愚直にシミュレーションすることを考える

一番重要な事実は、2個目のスタックは常に2重階段みたいになっているということ

つまり、2個目のスタックを前から見ていくと、値が減るか、もしくは1増えるかしかない(これを想像すると2重階段というのが伝わってくれると信じます)

すると、かなり正しい操作というのは少ないのでは?という気持ちになる

なんと驚くことに、場合分けをすると次する操作が一意に定まることが示せて、適当に実装してもO(N2)になる。

場合分けの詳細は省く、僕は12パターンになった。(177行 3547byte)

頑張って全てのパターンに対し正確な実装を行えば通すことができる。

ICPC Bangkok 2016

ICPCBangkokアジア地区に参加してきました

出発まで

  • なんか中間を休むために理由書が必要だった
  • ライブラリの準備に手間取った(25枚以内で、チーム名と通し番号が必要)(pdfに通し番号振るのが難しすぎた)

帰国した翌日が情報実験第四(組み込み)の製作物発表日で、 何も準備ができていないのでバンコクでの製作が決定する

飛行機の暇つぶしとしてラノベ2冊と去年一昨年の過去問を持ち込む。

木曜日

空港で迎えと会うのに苦労した。飛行機に乗ってる最中に迎えの場所のメールを送られていたっぽい 迎えのお姉さんがハチャメチャ可愛くてびっくりした。

到着してコーチhadroriオススメの飯屋へ行く

さすがに疲れてたのですぐ寝た

金曜日

深夜に朝7時にバスで出発するよ!メールが来てた。ハチャメチャ(今確認したが、2時33分。) 早起きしていたので間に合った。

チュラロン大学を観光

プラクティスは左右が東大チームでハチャメチャ あと問題がコーナーケースまみれでハチャメチャ

疲れで完全に僕は死んだので、夜ご飯いかずに寝た

土曜日

深夜に(ry (1時22分) 更に、CCで全員のメールアドレスを配布するという典型ミスが行われた。ロック

コンテストはだいたいpirozさんの見てもらえばOKです。 訂正すると、僕の解法は8問ではなく6問

去年一昨年はかなりひどいセットだったのが、今年は何が起きたのか。 重考察まみれで、要するに良問セットで、ひたすら解法生成をすることになった。 問題の質としてはUTPCクラスだと思う。 去年までの作問陣が作った問題は多分プラクティスに回されたんだと思う。(失礼)(でもH問題はreadforcesで去年までの面影が残っていた)

一方環境の方はちゃんとロックしていて、 紙が配布されなかったり、途中でパソコンが止まったりした。 vscode/atom/sublimeが使えた。全く準備をしてなかったため使わなかったが(コンテストページに書いて欲しかった)

あと左右はやっぱり東大チームだった

紙は無駄にライブラリを3部印刷していたため、実質裏紙が50枚あり、困らなかった (でも僕は紙を大量消費するので、35ページぐらい使ったと思う)

めっちゃ僅差で2位を逃した。WFに行ける確率は0ではないがかなり低い、って感じらしい でもここまでCxiv-Dxivと接戦に持ち込めるのは想定外だった。

日曜日

観光をした。ボラれた。タイマッサージをした。

コーチhadrori、そろそろエオルゼアが足りなくてヤバイっぽい

月曜日

朝五時にホテルを出て空港へ。 組み込みの進捗が爆発炎上していて、飛行機で組み込みをしていた。

朝四時まで組み込みをした。

火曜日

組み込み発表会。まさかの優秀賞を取った。

Codeforces GYM 2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest J

数日掛けても全く解けなかった、提出コードも嘘っぽいものしかなくて、想定解っぽいものを得るために片っ端から読む必要があった

解法は知るとそんなに難しくないのだが、なんか異常に難しい。

問題概要

Dashboard - 2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest - Codeforces

長さNの文字列Sが与えられる。ただし文字の種類はN種類あることもある(各文字はcharではなくintで表される)

全ての部分文字列について、ABBA型となるか判定する。ただし、A or Bは空文字列でもよい。

N <= 5000

解法

ABB | A ←この縦棒を固定する。

| ABB | A ←そのつぎに左端を動かして調べていく

この固定方法のキモは、Aとしてありえる文字列長が区間となること。

追記

嘘です。まともな解法ないのでは?

ARC 059 F バイナリハック

math, tokoharu, n_vip(と僕)の集合知によりmagicを使用しないO(N)解が錬成されました。

はじめに

解説のとおりに"なんでもいいので最終的な長さがM"となる操作の仕方を考えています。

操作列の条件

0add, 1add, delの3種類がありますが、とりあえずaddを1種類で考えます。

長さNのadd, delの列が、最終的に長さMの数列を生成する条件はなんでしょうか?

これは、逆から見てmax(今までのadd - 今までのdel) = Mが条件です。

つまり、addを+1, delを-1として数列 a_1, a_2, ..., a_N を作ると、

max(a_i + a_{i+1} + ... + a_N)が最終的な長さになります。

経路へ

逆から見るとシンプルな条件になったので、経路で考えます。

addを上移動(y+=1), insを右移動(x+=1)とすると、最終的な数列の長さは経路上のmax(y-x)となります。

よって最終的な長さがM以下 ←以下です!!!!ぴったりMじゃないですよ!!!!!!!!!!❕❕❕❕❕❕❕❕ となる操作列は

  • (0, 0) からスタートして、y - x <= M を満たしながらN回移動

と対応します。

N回移動した後の目標地点は高々O(N)個しかないので、それぞれについて経路数を求めて足せばよいです。

これでM以下が出せたので、M以下-(M-1)以下を求めればよいです。

addを2種類へ

y+=1するときに2倍されるようになりますが、あんまり変わりません(投げ槍)