ARC059 : F - バイナリハック / Unhappy Hacking
追記3:
yosupoが最新版の解説を書いたようです。こちらを見ましょう。
以下は旧記事です。
AtCoder Regular Contest 059 で出題された F - バイナリハック / Unhappy Hacking の O(n)解法です。
解説はコードに埋め込みました。 カタラン数云々は http://www.mtholyoke.edu/~jjlee/Teaching/Intro_to_Catalan.pdf を見て下さい。
atcoderの提出はこちら Submission #839457 - AtCoder Regular Contest 059 | AtCoder
追記:
今回使ったA126087 - OEISにある漸化式ですが、 Conjectureだそうです。一応 n <= 3000まで正しい事は確認しましたが、気になる方がいるようなので追記します。
追記2: magicを使わなくても解けたようです。
Submission #839587 - AtCoder Regular Contest 059 | AtCoder
解説
@__math 最終的にK文字以下ってのを逆から考えると(0, -M)から(N-i, -M+i)へのカタラン経路数にの総和になるから、それを求める
— メロンパンファクトリー (@yosupot) 2016年8月13日
以下は旧コード
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)c.size()) #define ten(n) ((int)1e##n) using ll = long long; const int MOD = ten(9) + 7; const int N = ten(4); // O(N) ll inverse[N]; void init_inverse() { inverse[1] = 1; for (int i = 2; i < N; i++) inverse[i] = (MOD - MOD / i) * inverse[MOD%i] % MOD; } // O(N) ll fact[N], infact[N]; void init_fast_fact() { init_inverse(); fact[0] = fact[1] = 1; for (int i = 2; i < N; i++) fact[i] = fact[i - 1] * i % MOD; infact[0] = infact[1] = 1; for (int i = 2; i < N; i++) infact[i] = infact[i - 1] * inverse[i] % MOD; } // O(1) ll fast_nCk(int n, int k) { if (n < 0 || k < 0) return 0; if (k > n) return 0; ll ret = fact[n] * infact[k] % MOD * infact[n - k] % MOD; return ret; } //O(1) ll pseudo_catalan(int a, int b, int c) { if (c == a - 1) b--, c--; if (c == b - 1) a--, c--; ll ret = fast_nCk(a + b - 2, a - 1) - fast_nCk(a + b - 2, c - 1); if (ret < 0) ret += MOD; return ret; } int solve(int n, int m) { // O(n) にできるが、今回は十分に大きい定数回回している init_fast_fact(); // https://oeis.org/A126087 // magic[i] = i回タイプした時、文字列が空になるようなキーの押し方の個数 // O(n) vector<ll> magic = { 1, 1, 3 }; for (int i = 3; i <= n; i++) { ll tmp = 3 * (i + 1) * magic[i - 1] + 8 * (i - 2) * magic[i - 2] - 24 * (i - 2) * magic[i - 3]; magic.push_back(tmp % MOD * inverse[i + 1] % MOD); if (magic[i] < 0) magic[i] += MOD; } // 2の累乗 // O(n) vector<ll> power_of_2; power_of_2.push_back(1); FOR(i, n) power_of_2.push_back(power_of_2.back() * 2 % MOD); ll ans = 0; FOR(s, n) { // ループ内はO(1) // // |------|X|-------| // <------>^<-------> // | | | // s | rem - 1 // s回目(0-indexed) // // 前半s回のタイプ後、文字列の長さが0 // s+1回目、最初の文字を打つ // 後半、s+2回目以降は、文字列が空にならないよう注意しながらタイピング // こうすると重複せず数え上げられる // // 前半はmagicに係数が入っているので、後半のs+2回目以降のタイプの仕方について数え上げればよい const int rem = n - s; //後 rem 回タイプ出来る if (rem < m) continue; if ((rem - m) % 2 != 0) continue; const int B = (rem - m) / 2; // s+2回目以降のバックスペースの回数 const int A = rem - B; // s+2回目以降タイプする文字列 (= {0,1}をタイプする回数) const ll a1 = B == 0 ? 1 : pseudo_catalan(A , B + 1, B); //カタラン数の計算方法と同じやつ // バックスペースで消される文字列は{0,1}のどっちでもいいので、 2^B を掛ける const ll s_ans = a1 * power_of_2[B] % MOD * magic[s] % MOD; ans += s_ans; } return int(ans % MOD); } int main() { int n; cin >> n; string s; cin >> s; int m = sz(s); int ans = solve(n, m); cout << ans << endl; return 0; }
n以下の素数のsumを高速に計算する
目次
- 動機
- 問題概要
- 準備
- 計算量
- \(1 \le p_b \le n^{1/4} \) の時
- \(n^{1/4} \le p_b \le n^{1/2} \) の時
- 素直なプログラム
- 最適化したプログラム
- 余談
動機
Project Euler で、n以下の素数の合計を求める問題がありました。 Problem 10 - Project Euler
この問題は2*106以下の素数の合計を求めるだけなので簡単なのですが、Lucy_Hedgehog さんという方が面白いアルゴリズムをpostしていました。
せっかくなので、なるべく初心者にも分かりやすいようにアルゴリズムの概要を説明したいと思います。 アルゴリズムとか計算量とかどうでもいい人は、
optimized_prime_sum.cpp · GitHub
のプログラムをコピペして使って下さい。
問題概要
競技プログラミングで以下のような問題が出た場合、どう実装すればいいでしょう?
\(n\)以下の素数の合計を出力して下さい。ただし、n <= 106
エラトステネスの篩を使えばn以下の素数の列挙は \( O(n \log\log (n)) \) で出来るので、このアルゴリズムで十分だと思います。
では次の制約の場合はどうでしょうか。
\(n\)以下の素数の合計を出力して下さい。ただし、n <= 1012
答えは 64bitに収まらないので、109 + 7で割った値を答えて下さい。
アトキンの篩を使えば 計算 \( O(n / \log\log(n)) \) , 空間 \( O(n^{1 / 2}) \) で計算出来る(らしい)ので、これで十分かも知れません。 が、今回は計算 \( O(n^{3/4}) \), 空間\( O(n^{1 / 2}) \) で計算出来る方法を紹介したいと思います。
続きを読むISUCON5 オンライン予選 通過しました
優勝賞金100万円!今年もやります ISUCON5 開催と日程のお知らせ #isucon : ISUCON公式Blog
「お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係ない、結果が全てのガチンコバトルです。」(公式説明)であるISUCON5のオンライン予選に参加してきました。
...
ISUCONは Iikanjini Speed Up Contest の略で、Webアプリケーションがデプロイされたイメージを渡されて、その上で何をしてもいいからとにかくパフォーマンスを上げることが競技内容です。
ということで参加してきました。
チーム マウント竹田氏(メンバー: @misodengaku, @chibiegg, @__math) で出ていました. 16位で予選通過です。 いつもは @aki33524 も参加するんですが、上限が3人までということだったので、裏番組のTrend Micro CTFを頑張ってもらいました…、きひろくんごめん。
他のメンバーの参加記です
- chibiegg : ISUCON5オンライン予選に参加してきた « chibiegg日誌
- misodengaku : ISUCON5予選に出ました - misodengakuのブログ
初参加でしたが決勝に進出出来てよかったです。
続きを読む任意modでの畳み込み演算をO(n log(n))で
http://misawa.github.io/other/fast_kitamasa_method.html を見て刺激されたので書いた.
- 畳み込み演算?
- 任意modでの畳み込み演算
- 中で使われてる技術達
- c++のコード
コードと原理の説明をちょっとだけ載せています.
コードだけ欲しい人は https://gist.github.com/math314/6a08301b8b75b8172798 をどうぞ. fast_int32mod_convolution を使うとint32の任意のmodが取れます.
実はまだverifyしてない.
続きを読むBoston Key Party 2015 Wood Island : 150 Write up
問題概要は省略します…聞きたい人がいたらリプライかコメント下さい
続きを読むSECCON CTF 2014 決勝戦 サーバ六 write-up
SECCON CTF 2014決勝戦・全国大会カンファレンス
チーム Mr.Takedashi(メンバー: @misodengaku, @aki33524, @chibiegg, @__math) で出ていました. 9/24位です. 日本人チームの中では4/13位でした.今年はcryptoがあったので幾つか問題が解けました.
他のメンバーのwrite-upです
SECCON CTF 2014 決勝戦 参加記 « chibiegg日誌
SECCON 2014 全国大会に出た - misodengakuのブログ
去年も決勝大会(http://math314.hateblo.jp/entry/2014/03/03/210318)に出たのですが,順位が下の方で悔しい思いをしました.2014年も出れたなら1桁の順位をとろう!とチームで言っていたので,目標が達成出来て満足です.
私は主に サーバ六 の問題を担当したので,簡単にwrite-up を書きたいと思います.
続きを読むdwangoプログラミングコンテスト
Welcome to dwangoプログラミングコンテスト - dwangoプログラミングコンテスト | AtCoder
26位でした.D問題が通せなかったの悲しいですね.