Combinationの求め方まとめ

c++でnCkの計算でnの値に応じた2種類の導出方法をメモ。

  1. nの値が50程度でlong long型に収まるとき

このときはオーバーフローや時間制約を気にする必要はないが、階乗を愚直に計算することはできないので注意する。
nCk = n-1Ck-1 + n-1Ckというパスカルの三角形から導かれる公式を用いることでO(n^2)で計算が可能である。

#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e9)
using namespace std;
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;
int N,K;
ll v[51][51];

void nck(){
    rep(i,0,N+1){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    rep(i,1,N+1){
        rep(j,1,i){
            v[i][j] = v[i-1][j-1] + v[i-1][j];
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    nck();
    print(v[N][K]);

}

50C25で1e14程度のオーダーなのでN<=50程度の制約であればこちらの方法で問題ない。

  1. nが大きくmodを用いる場合

当然nが1000などになってくればオーバーフローするので1e9+7などの値でmodを取ることを要求してくるのが普通である。
また、nが100000程度になればO(n^2)で計算を行うことも不可能である。
このような場合、逆元を用いたmod計算を行うことで結果を導出することができる。
ここで用いるのがフェルマーの小定理
aとpが互いに素であるときに
 a^{p-1} \equiv 1 \bmod  p
が成り立つというものである。詳しいことはこちら↓
mathtrain.jp
この式の両辺にa^{-1}をかけると
 a^{p-2} \equiv a^{-1} \bmod  p
となる。したがって、aの逆数のmodはa^{p-2}のmodに等しいということがわかる。
これで準備が整う。こうして求まったmodの値を保持しておいて、 n!, ((n-k)!)^{-1}, (k!)^{-1}の3つを掛け合わせて再びmodを取る(この時オーバーフローに注意)ことで答えが求まる。
その場で考えずに貼り付けるケースが多そうだから原理はそこまで重要じゃなさそうだけど。
以下実装の例。

#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define INF (1e9)
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;

using namespace std;
const ll max_N = 110000;
ll fac[max_N + 1000], facinv[max_N + 1000];
const ll MOD = 1e9 + 7;
ll N,K;

ll power(ll x, ll n){
    if(n == 0) return 1LL;
    ll res = power(x * x % MOD, n/2);
    if(n % 2 == 1){
        res = res * x % MOD;
    }
    return res;
}

ll nck(ll n, ll k){
    if(k == 0 || n == k){
        return 1;
    }
    return fac[n] * facinv[k] % MOD * facinv[n-k] % MOD;
}

ll npk(ll n, ll k){
    if(k == 0 || n == k){
        return 1;
    }
    return fac[n] * facinv[n-k] % MOD;
}



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    fac[0] = 0;
    fac[1] = 1;
    rep(i,2,max_N){
        fac[i] = (fac[i-1] * i) % MOD;
    }
    rep(i,0,max_N){
        facinv[i] = power(fac[i], MOD - 2);
    }
    print(nck(N,K));
}

facが通常の階乗のmodで、facinvが逆元を表している。
これを用いるとn = 100000程度であっても答えを得ることができる。

c++でpriority_queueを使ってみた

通常のqueueはbfsなどで使うことがあったが遂にpriority_queueを使う問題に遭遇したので使い方をメモしておく。
使ったのはこのD問題
beta.atcoder.jp
これ、結構考察と実行ともに充実してていい問題だと思った。

priority_queueの基本的な使い方はこんな感じ。

#include <"bits/stdc++.h">
using namespace std;

int main(){
    priority_queue<int , vector<int>, greater<int> > pq;
    pq.push(5);
    pq.push(8);
    pq.push(1);
    while(!pq.empty()){
        print(pq.top());
        pq.pop();
    }
}

greaterは取り出す順番を決める比較演算子で、これを指定すると小さいものから順に出てくる。
名前と挙動が少し間違いやすいので注意が必要かもしれない。
デフォルトではlessなので、何も書かなければ大きい順に出力される。

pairなどの型も要素として用いることができる。その場合定義は下のようにする。

  priority_queue< pair<int, int> , vector< pair<int, int> >, greater< pair<int, int> > > pq;

priority_queueは並び替えをO(logN)で行うことができるので実行後にソートを実行する必要のある問題においてオーダーを下げることが可能となる。

sortのように自作の比較関数も定義できるようなので、時間があればやってみようと思う。

Tampermonkeyを用いたuser scriptの作成

最近AtCoderでuser scriptを用いた自分だけのページを作ろうみたいな流れがあるので試しに簡単なuser scriptを作成してみた。

Chromeを使っているので今回はTampermonkeyというChromeプラグインを用いる。

https://tampermonkey.net/

新規スクリプトを選択すると次のような初期状態になっている。

// ==UserScript==
// @name       ac-menubar
// @namespace  None
// @version    0.1
// @description  メニューバーを自分のrateに合わせて変更
// @match      https://beta.atcoder.jp/*
// @copyright  2018 ysugiyama
/* load jQuery */
// @require http://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js
// ==/UserScript==

一見してコメントのようだが、ここにuser scriptに必要な情報が含まれている。重要なものをいくつか紹介。

  • @name - script名
  • @match - どのurlの時にこのscriptを動かすか
  • @require - このscriptを実行するのに必要なincludeファイルを書く。pathを書けばローカルファイルも読み込むことができる。

続いて、メインとなる処理をJavascriptで書いていく。
今回実装したものは「AtCoderで自分のレートに合わせてヘッダの色が変化する」というもの。
実装はこんな感じにしてみた。AtCoderAPIあたりの知識がなかったのでajax使って結構無理やりレートを取得したのでいい方法があれば知りたい。

// ==UserScript==
// @name       ac-menubar
// @namespace  None
// @version    0.1
// @description  メニューバーを自分のrateに合わせて変更
// @match      https://beta.atcoder.jp/*
// @copyright  2018 ysugiyama
/* load jQuery */
// @require http://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js
// ==/UserScript==
jQuery(document).ready(function($) {
    function getElementByXpath(path) {
      return document.evaluate(path, document, null, XPathResult.FIRST_ORDERED_NODE_TYPE, null).singleNodeValue;
    }
    var dom = getElementByXpath('//*[@id="navbar-collapse"]/ul[2]/li[2]/a').text.split("(");
    if(dom.length > 0){
        var user_id = dom[0].replace(/[\n	 ]/g, "");
        var user_score = 0;
        $.ajax({
            url: "https://beta.atcoder.jp/users/" + user_id +"/history/json",
            type: 'GET',
            dataType: 'json',
            success: function(info){
                info.forEach(function(e){
                    if(e.IsRated){
                        user_score = e.NewRating;
                    }
                });
                if(user_score < 400){
                    $('.container-fluid').css('background-color', 'gray');
                }else if(user_score < 800){
                    $('.container-fluid').css('background-color', '#a0522d');
                }else if(user_score < 1200){
                    $('.container-fluid').css('background-color', 'green');
                }else if(user_score < 1600){
                    $('.container-fluid').css('background-color', '#afeeee');
                }else if(user_score < 2000){
                    $('.container-fluid').css('background-color', 'blue');
                }else if(user_score < 2400){
                    $('.container-fluid').css('background-color', 'yellow');
                }else if(user_score < 2800){
                    $('.container-fluid').css('background-color', 'orange');
                }else{
                    $('.container-fluid').css('background-color', 'red');
                }
            }
          }
        );
    }
});

過去のレート一覧のページで/json叩くとjsonファイルが取得できるのは初めて知った。
あと、xpathを使ってDOMを選択することも実は初めてだったので勉強になった(前は直接xpathを書いてアクセスする関数があったらしいが廃止されたらしい)。
これを実行するとbeta版のAtCoderのサイトでは下のようにヘッダーの色が変わるようになった。
f:id:yuji9511yuji:20181008001915p:plain

そろそろ水色になりたいなぁ...

ぼくのDOSS奮闘記 〜LibreOfficeを手探ってみた〜 3/3

論理和論理積、そしてシェル関数

発表まで残された日数はあと授業2回分しかないが、流石に実装したものが1つだけというのは物悲しいので、追加で機能を実装することにした。まず自分たちで思いついた案としては「if文で用いるような論理和論理積を記号を用いて"&&", "||"のように書けるようにする」というものがあった。もう一つ、先生が出してくれた案として、「libreoffice上からターミナル上で入力できるようなコマンドを実行できるようにする(シェル関数の実装)」というものがあり、これは自分たちには思いつかなかった面白い発想かつ大して面倒な実装ではない気がしたので、圧倒的感謝をしつつ早速取り組むことにした。

しかし、ここで1つ目の実装に6日もかかってしまったことを思い出した。また軽い気持ちで取り組んだらこの前のようになるのではないかという不安が3人の頭をよぎった。

だが、この2つの実装、どちらもあっけなく1日で終わってしまった。やはり前回のCombinationでノウハウを習得していたことが大きかっただろう。

簡単に実装内容を説明しておこう。まずシェル関数の実装に関しては=SHELL("")という形でコマンドを入力する形をとり、ユーザーが入力した文字列を中でpopen関数に渡すという形をとった。出力結果を返り値として取得してセルに反映させる。ただ1つ注意点として、libreofficeの中で文字列はOUStringという独自に定義した型を用いている。したがって入力として受け取ったOUString型をString型に一度戻してからpopenに流し込み、得られた出力結果は再度OUString型に直してからセルに出力するようにした。こうすることで各種シェルコマンドを実行してくれる関数が実装できたわけだが、当然セキュリティ的にはとても問題がありそうな匂いがするので実際に有用かと言われると微妙なところである。

さて、もう一つの実装である論理和論理積についてもまとめておく。こちらは一見すると組み合わせ演算子の時と変更点は全く同じように見えるが、一つだけつまずいたポイントがあった。それは演算子が&&など2文字で表されることである。どういうことかというと、組み合わせ演算子の時と同じようにするとプログラムは1文字目の&を読んだ時点でそれを演算子(&1文字だと文字列結合の演算子)と認識してしまい、演算子のあとに再び演算子→構文エラーとなってしまうのである。そこで、文字列から演算子を切り出す条件を決めている部分を探す必要があり、ここを見つけ出すのに少し苦労した。結果的にsc/source/core/tool/compiler.cxxに「この記号がきたら次来るのはこの要素」と決定している部分があった。言葉ではわかりづらいので具体的にコードを載せておく。

$ /* & */ t[38] = ScCharFlags::Char | ScCharFlags::WordSep | ScCharFlags::ValueSep;

 38は&の文字コードで、この行は&演算子の後にCharまたはWordSepまたはValueSepが来ることを示していて、演算子としてはここで区切られることを示している。ここを変えてしまうことも考えたが、とりあえず&& と ||の時のみ対応させようと考え、「文字&または|を読み取った時、次の文字を見てそれが&か|だったらそれも同一の演算子に含める」という記述を加えることでこの問題は解決した。

おわりに

こうして追加で考えた2つの機能の実装も完了し、なんとか発表までにまとめることができた。一人では到底ここまで到達することができなかったので、ひとえに他のメンバーや教授、TAの方々のおかげである。ここに書いたことは実際に進捗を生んだ部分をかいつまんで書いているだけであり、本当はかなり何もできない時間が長かったことを知っておいてほしい。

この実験を通して普段いじらないような大規模なソフトに取り組めたことは貴重な経験だったし、デバッガがとても有効な手段だということを改めて知ることができた。また、全体像がわからなくても適当に存在しそうな変数名でgrepを実行すると案外たどり着くものだなという地道な努力の素晴らしさにも気づくことができた。後からこの記事を読んだ人がこの授業がどのようなものなのか、どのような成果が得られるのかを少しでも吸収してもらえたら嬉しい。

ぼくのDOSS奮闘記 〜LibreOfficeを手探ってみた〜 2/3

makeを無事終えたこの日の実験。全員がcalcの起動までできていたのでここからデバッガを動かしてみることにした。gnuplotの時に行った方法とは異なり、LibreOfficeでは開発用にこのようなコマンドが用意されていた。

$ make debugrun

これを実行することでgdbデバッグモードに移行する。何事もなくデバッガが立ち上がったように見えるが実は./autogen.shの実行時のオプションとしてつけた--enable -dbgutil がないとおそらくできなかったと思われる。つけ忘れていたらまたmakeし直しだったと思うと恐ろしい。

とりあえず上手いやり方もわからなかったのでgnuplotでやったようにmainにbreak pointを置いてrunしたのだが、この方法は完全に間違っていた。gnuplot程度の規模なら起動時点から動作を追っていけばいずれ所望の部分にたどり着くのだが、LibreOfficeはそんなことを許してくれる規模ではなかった。TAさんのアドバイスによれば、具体的に何を変えたいのかを決めてからそこの変更をするための部分をピンポイントで見つけ出した方が良いとのことだった。

そう、何を変えるかをまだ決めていなかったのだ。メンバーで話し合った結果、関数を用いた計算の処理に少し変更を加えようという話になり、まずウォーミングアップとして=Combin(9,2)と表記する組み合わせの計算を=9C2のように演算子のように書けるようにしようと決めた。今考えると、これをウォーミングアップなどと言っていた過去の自分を殴りたい。

ここからの作業がひたすら泥沼だった。とりあえず+や-などの演算子の記号と処理の対応づけをしているファイルがあるはずなのでそれを探すことにしたが、いくら探しても見つからない。というか探す出発点がまるで思いつかない。とりあえず思いつく演算子関連のワードを色々とgrepで検索してみるがいまいち見つからない。GUIでセルを選択した時に新たなスレッドが立つのでこのスレッドから流れを追おうとも考えたがこの作戦もうまく行かなかった。また困ったことにルートディレクトリからgrepをかけてもファイル数が多すぎるため検索ができないのである程度フォルダに検討をつけてgrepするしかないのだ。幸い、Calc関連のファイルがscというディレクトリにまとまっていることに気づいたので少し探索はしやすくなったのだが、このディレクトリ内にあるだろうという先入観がまた発見の遅れを生むことになる。3人がかりでクサいファイルの捜索にあたっていたが、丸々2日間ほどは大きな進捗は生まれずただ時間だけが流れていった。

4日目あたりでようやく演算子の定義に関する重要なファイルをいくつか発見できた。まず /formula/inc/core_resource.hrcというファイル(hrcってなんの拡張子?)に記号と実行する演算の対応表を見つけた。具体的には下のような感じ。

 

{ "+" , SC_OPCODE_ADD },
{ "-" , SC_OPCODE_SUB },
{ "*" , SC_OPCODE_MUL },

 つまり、追加したい演算子の文字と、それに対応する何かを関連づけている。このSC_OPCODE_ADDなどを定義している部分を探すと、include/formula/compiler.hxxにこれらを定義している部分を見つけた。 

 

#define SC_OPCODE_ADD 50
#define SC_OPCODE_SUB 51

また、include/formula/opcode.hxxには演算子を識別するtokenをこの定数に結びつけていると思われる部分を見つけた。

 

 ocAdd = SC_OPCODE_ADD,
ocSub = SC_OPCODE_SUB,

 

ocAddなどのtokenを実際の計算では使用すると推測されたので、この3つを書き換えることで新たな演算子を登録することができるのではないかと考えた。

また、ScCompiler::CompileStringという関数で入力文字列から演算子に変換すること、ScInterpreter::Interpretという関数で実際に計算をする関数に飛ぶ(ocAddならScAdd関数など)ことを突き止めた。この辺りを新しい演算子に対応させれば早くも動作するようになるのではないかと少し希望が見えてきたところである。

さて、ここで少し別の問題が浮上していた。makeをすると途中で落ちてしまうのである。どうやらTestで落ちているらしいのだが、実行するごとに違う部分でエラーを吐いてしまうのでとても困っていた。TAさんに聞いても根本的な解決方法はわからなかったため、いっそテスト自体を実行しない方法を探したほうが良さそうと言われた。探してみるとすぐにテストなしのmakeを行う次のようなコマンドを見つけた。

 

$ make build-nocheck

この方法でmakeをしたところ正常にmakeが完了したのでとりあえずこれで先に進むことにした。結局最後までtestが通らない原因はわからなかった...

さて、演算子の実装の話に戻ろう。表示されるエラーなどから演算子の文字として用いようとしている'C'はセル番号や関数名の先頭の文字と重なることから不適切であることがわかった。そこでおそらく何にも使われていないであろう'@'を'C'の代わりとして用いることにした。

ここまでで'@'が今回実装したいCombinationの演算子としては認識されたが、なぜか演算が実行されなかった。ここでまたしばらく足止めを食らうことになるのだが、再びgrepなどを繰り返し行った結果、formula/source/core/api/FormulaCompiler.cxxで木構造から演算の順序を決める処理をしている部分を発見した。つまり掛け算は足し算より優先して行う、のような取り決めをしている部分である。組み合わせ演算子は当然加減算よりは優先されるので、今回は累乗を表す演算子ocPowと同等の優先度を持つ位置にocCombinを配置することにした。

さて、6日間かかってようやく一つの演算子を追加することに成功した。全くウォーミングアップという内容ではなかったが、計算の流れをなんとなく追うことができたと思う。ラストの記事ではこの実装をもとに残り2つの機能の実装をどのようにしたかをまとめようと思う。

 

ぼくのDOSS奮闘記 〜LibreOfficeを手探ってみた〜 1/3

ここから後期実験「大規模ソフトウェアを手探る」のレポートを書いていきたいと思います。時系列に沿ってどのようなことを行ったか、裏にはどのような苦労があったのかをわかりやすくまとめていきたいと思います。なお、変更点の部分をコードでガンガン載せようとも考えたのですが、いきなりどこからか出てきたコードを出されてもわかりにくいと思ったのでできるだけ言葉でまとめました。

  •  make、そしてビルドまで

1日目で簡単なデバッガの使い方を身につけた後、2日目に僕たちは扱うソフトウェア決めという重要な分岐点に差し掛かっていた。emacsでのデバッグは少々不慣れだったもののある程度流れは掴めていたので、多少ソースコードの量が増えても同様の手順で進められるだろうとこの時は思っていた。

チームを組んだ3人がそこまでプログラミングに長けたメンバーではなかったため、ハードルは高いソフトウェアは避けようと思っていた。過去のブログなどをみた結果からchromiumなどのブラウザ系は処理が追いにくくソースコードも多そうだと(ほとんど推測のみである)見切りをつけた。また、InkSpaceなどのお絵かきソフトも手をつけやすそうだったが、触ったことのないソフトウェアを手探るのは流石に無茶ではないかという話になりこれもスルーした。そんなこんなでテーマ決めに悩んでいるときにふと学科PCに入っていたフリーのソフトウェア、LibreOfficeが目に入った。これなら全員が触ったこともあり、それほどコードが大規模すぎることはないのではないか(これが大きな間違い)と思い、軽い気持ちで着手することにした。これが僕たちとLibreOfficeの運命の出会いである。

さて、コードを手探るも何もまずはローカル環境でビルドしてみないことには話が進まない。僕たちは最初の関門「ビルド」に立ち向かっていく。

まずはビルドするにあたって公式のページを探っていくと、いい感じにビルドの手順がまとまっているページを見つけた。

https://wiki.documentfoundation.org/Development/BuildingOnLinux

このページに載っている通りにファイルをgit cloneしてautogenしてmakeすればいけそうな気がする。とりあえず以下のコマンドを叩いてみる。

$ git clone git://anongit.freedesktop.org/libreoffice/core
$ cd core
$ ./autogen.sh --enable-dbgutil --without-java --without-help --without-myspell-dicts

git cloneして「450万ファイルあるで」と出てきた時にこのソフトウェア実はやばいんじゃないかという予想が頭を掠めた。autogen.shの後についているオプションはlinuxでビルドする時につけといたほうがいいよーというものらしい。特に--enable-dbgutilは後でその重要性を知ることになる。

autogen.shを走らせるといくつかインストールしろと言ってくるので言われたとおりにいくつかインストールしたら無事に終わってくれた。さて、あとはmakeするだけなんですが、これがとーっても長いんですね。公式でも

"make is the command which takes a vast quantity of time to run for the first time."

って脅してくるくらいですから。vast quantity of timeって強そう。笑

さて、それではmakeしましょう!

$ make

 ......

 ........

 ..........

TAさんには5時間くらいかなと脅されたが、幸い3時間ちょいで終わった。はやいはやい。(汗)ちょっと外が寒い日だったのでフル稼働で激しく放熱する学科PCがいい暖房として機能していた。

makeが終わった後、instdirというディレクトリができていたので、サイトに従い以下のコマンドを打つと指定したソフトが起動した。この場合は--calcと指定することでLibreOffice Calcを起動する。

$ instdir/program/soffice --calc

ここでLibreOfficeについて簡単に説明しておくと、MicrosoftのWordやExcelに対応するようなソフトウェアをオープンソースとして無償で提供しているものである。現在も開発が積極的に行われていて、企業向けの安定版と最新機能をふんだんに盛り込んだ最新版の2つがリリースされている。今回は様々あるLibreOfficeのソフトの中からExcelに対応する「LibreOffice Calc」を手探ることにした。

とりあえずそこまで大きなトラブルもなくLibreOffice Calcの起動まで終えて割と順調な出だしだと思えた。makeが長いのは一回目だけだからと言われたのでとりあえず一安心してこの日の実験を終えた。この先に広がるデバッグgrepの闇などまだ知るはずもないのである... (次の記事に続く

 

はじめまして

こんばんは、ブログなんて書くの初めてな杉山です。

きっかけはeeicの授業「大規模ソフトウェアを手探る」という実験の最終レポートがブログでもいいよと言われたことですね。

せっかくなので備忘録的な何かをまとめておける場所になればいいかなーと思います。三日坊主にならなきゃいいですが、、

主な目的はプログラミング関連になると思いますがどんなジャンルに傾いていくのか楽しみですねw

それではよろしくおねがいします(๑╹ω╹๑ )