Union-Findの利用？

おはようございます。進捗ダメすぎて死にました。この文章は私の思考をトレースしたAIが書いています。

このブログには一応、「プログラミング未経験者がプログラミングをゼロから勉強していく過程を残そう！」みたいな健気な理念があった気がするんですが、なんかどこかへ行きました。不思議ですね。

いや記事を書くより勉強するスピードの方が早いので仕方ないですね（笑）（嘘です、私の名前は怠慢です）

動的計画法の記事とか書いた覚えがあるんだけどどこにやったか、さては下書きに残ってるな、ワロタ。（ワロタじゃありません）

今回はUnion-Findの利用が重要な問題を二つまとめて今後の参考に残したいと思います。

atcoder.jp

この間の京大プログラミングコンテストのB問題です。sabaくんが京大まで行って出場していたっぽいですね、ずるい。ばーかばーか。

名前の通りナップサック問題です……が、普通と様子が違います。このままじゃ解けない。

頭が悪いので次のように思考を展開しました。

ナップサックに帰着できるorできない。前者を仮定。
「aが使われる時はbも使われないといけない」というような荷物をひとまとめにすれば普通のナップサック問題に帰着出来る。つまり動的計画法でO(n^2)で解ける。
ではどうやってひとまとめにするか？→Union-findで番号の繋がりを管理すればよい。

数学の問題を解くときとかはこんな感じで深さ優先探索のように解法を考えるんですが、他の人がどうなのか聞いたことがありません。もしよかったらTwitterとかで教えてください。

と言うわけでコードです。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < int(n); ++i)

ll dp[101][1000005];

int main(){
    int n, m, W; cin >> n >> m >> W;
    int w[n], v[n]; rep(i,n) cin >> w[i] >> v[i];
    union_find u(n);
    
    //ひとまとめにする
    int a, b; rep(i,m){
        cin >> a >> b;
        a--; b--;
        if(a > b) swap(a, b);
        u.unite(a,b);
    }
    
    //子の要素を親へ集中させる
    rep(i,n){
        if(i != u.root(i)){ 
            w[u.root(i)] += w[i]; v[u.root(i)] += v[i];
            w[i] = 0; v[i] = 0;
        }
    }

    //ナップサック問題に帰着
    rep(i,n){
        rep(j,W+1){
            if(j < w[i]) dp[i+1][j] = dp[i][j];
            else dp[i+1][j] = max(dp[i][j-w[i]] + v[i], dp[i][j]);
        }
    }
    cout << dp[n][W] << endl;
}

相変わらず読みやすいコードですね。うっとり。

Union-Findの実装は省略しています。分からない部分があったら以前の記事（
自作の関数の保存というのをやってみました - Re:ゼロから始めるプログラミング生活
）か、GitHubを参照してください。
（記事との変更点はクラスにしてコンストラクタを入れたことぐらいなので大丈夫だと思います。）

今回の問題の教訓ですが、次の二つが気になりました。

・グループの要素数が減らない場合、つまり連結しか行われない場合は対象に番号を割り振ることで、Union-Findでグループ分けが出来る。
・ナップサック問題で荷物の重量と価値を0にしておけば、その荷物はないものとして、荷物の数を変えないまま実装出来る。（要検証）

2つ目は他で使うのか？って感じなので放っておきます。

1つ目は、連結判定が本質的にグループ分けになっているという話です。考えたら当たり前のような気がしますが、Union-Findでグループ分けを手軽に行えるようになるのは大きいと思います。

次の問題です。

atcoder.jp

これDifficulty低くないですか、みんな当たり前のように全探索出来たりUnionFind使えるのなんなんでしょう。
sabaとか水色なのにUnion-findわからーん！とか言ってた時期があった（僕がプログラミングを始めた当初の話です）し、chokudaiさんの言うように各色の平均的な実力が上がっているのかも。つまりぼくはえらい。

さて、この問題ではまず実質的にA_xi+A_yiの偶奇が与えられているところから始まります。
A_xiとA_yiのどちらか一方の偶奇がわかればもう片方の偶奇も分かるということになります。
そこで、これらをグラフの要素とみて、繋いでおきます。
こうして繋いで行くと、グラフの繋がった頂点の集合では、どれか一つの偶奇がわかれば他の偶奇も分かることになります。

結局、頂点がグループになっていて、このグループ数を求めたいわけです。明らかにUnion-Findの出番です。

int main(){
    int n,m; cin >> n >> m;
    union_find graph(n+1);
    int x,y,z;
    int ans = 0;
    rep(i,m){
        cin >> x >> y >> z;
        graph.unite(x,y);
    }
    rep(i,n) if(graph.root(i+1) == i+1) ans++;
    cout << ans << endl;
}

このように解けます。

Union-Findの利用例はもっとありますが、体力が切れたのでここまでにします。

今回当たり前のようにナップサック問題を解いていましたが、結局動的計画法の勉強記録を載せていないので流れとして不自然な気がしますね。気がするだけなので諦めることにします。

ではおやすみなさい。

二部グラフ判定

おはようございます。愛と正義の侵略者です。そろそろゴールデンウィークですね。

AGC039お疲れ様でした。何も分からなかった。

Aだけ解いて水パフォ出してレートを少し上げるみたいな生活をそろそろやめたいです。まだ緑で消耗してるの？（笑）

そんなわけで少しずつ学習を進めていくべく、二部グラフについてちょっと勉強しました。

二部グラフってなに？ 調べてみた！

いかがでしたか？ 二部グラフというのは頂点が二つのグループに分けられ、同じグループ同士の頂点同士を繋ぐ辺が存在しないようなグラフのことなんですね！

二部グラフの応用例は広く、中々全部を網羅するのは難しそうです。

ひとまずグラフが二部グラフに出来るかの判定をする関数を書いてみました。

深さ優先探索でグラフを見ていきます。
各頂点に色を交互に（つまり同じ色が隣合わないように）割り振っていき、既に探索済みのところに当たったらその頂点の色と現在引数で持っている色との整合性が取れるかを判定します。
（色は配列に収めるようにします。）
整合性が取れるなら問題なし、取れなければ二部グラフには出来ません。

//二部グラフに出来るかを判定
//now:現在の頂点番号
//color:1か2
//colors[i]: i番目の色、1か2を入れる。初期値は0で、このときi番目は未訪問
//graph:　探索対象のグラフ。適当に構成する。
//呼び出し方はisPartited(0,1)とかでよさげ
int colors[10000];
vector<vector<int>> graph(10000);
bool isPartited(int now, int color){
    if(colors[now]){ //探索済み
        if(colors[now] != color) return false; //探索済みなら色の整合性が取れないとダメ
        else return true;
    }
    colors[now] = color;
    int g_size = graph[now].size();
    for(int next = 0; next < g_size; ++next){ //ここの処理はグラフの実装によって適当に変えます
       if(!isPartited(graph[now][next], 2-((color+1)%2))) return false; //1つでもfalseがあったら二部グラフにはならない
    }
    return true; //分岐が全てtrueならtrue
}

昨日のB問題を通す時に使ったのを元に書いたので多分バグはないと思いますが、使う人（いるのか？）は自己責任でお願いします。

グラフの構成とかは適当にやってください。僕は基本的にvector> graph(適当なサイズ)をやってここに要素を追加して隣接リストにして作っています。

しかし「そんな甘っちょろいことやってられるか！」みたいな人がいる（訳ないけど万が一いる）なら上手く実装を変更してどうぞ。

（このブログ見るの僕と同じかそれ未満の実力の人ぐらいだと思うので、そんな人はいないとは思うんですが）

そういえばグラフの直径を求める時にワーシャルフロイド法を使えるのは知りませんでした。考えたら当たり前なんですが……＞＜

いやもっと精進しないといけない。某に「精進グラフが対数になってるよ？（笑）怠惰くん大丈夫？（笑）あっこるぼーくんだった（笑）」とか煽られました。

ではおやすみなさい。

大雑把に夏休みのまとめ

おはようございます。ブログの方は随分ご無沙汰だったので、夏の間の成果を自慢しておこうと思います。

というのは冗談で、あまり満足できる感じではなかった。

以下進捗。

・「徹底マスター JavaScript」：　完了
　クソ分厚い黒い本。JavaScriptは完璧……と言いたいが、この言語やべえ。マスターとか考えない方がよさそう。
　ブラウザに関する知識を付けるのが目的だったしまあ良しとしましょう。Reactの学習にも手を出せそう。
　使える言語がC、C++、Python、JavaScriptの4つに増えました。

・集合と位相：　だめ
　松坂位相、なんとかzornの補題までこぎ着けたが、いかんせん内容が重たすぎる。
　副読本というか、もう少しかみ砕いてある本を借りることに。早く次の段階に進みたい……。

・ゲームプログラミング：　だめ
　参考にしていたサイトの内容は大体抑えた。Dxlibに多少慣れた。
　……が、実際にゲームを作るには素材を作らねばならず、断念。シナリオすら進んでいない。

・競プロ：　だめ
　まだ緑ってマジ？ 600どころか500覚束ないんですが？？？？
　チーター本多少進んだ。夏の間に終わらせたかったなあ
　後述しますが、セグメントツリーを実装できたのはよかった。C++周りの知識も多少増えた。

・知識全般：　まだマシ
　クソ時間かかってるけど、知識量自体は着実に増えつつある。
　もう少しすれば全体の伸びが期待できそう。

というわけで大体撤退です、人生は厳しい。

次はここ数日の近況ですが。
一人でゲームプログラミングのお勉強をしていると、圧倒的先輩のぽうえっと（@poet_official）に誘われ（というか煽られ）数人の集まりを結成。
sabaも誘ったけど忙しそうなので数に入れないとして、slackでぽうえっと、福知ダイズ（@FukucheeDaize）、ぼくの3人で集まりちょっとずつゲームを作ることに。
しかし知識が皆無、特に集団開発とか出来ないのでGitHubの使い方から覚えています。（ぽうえっとくんマジでなんでも知ってて感動しています）
追伸：sabaが多少時間ありそうなので参加してえ！という事になった。Pythonでサーバーサイドを皆殺しにしてくれるかもしれない。Unityを授業で扱うとかで、その辺にも乗り気のようです。

とりあえずリポジトリとかいうのを作って競プロ用ライブラリを上げてみました。
https://github.com/zerokpr/Kpr_Library

cordata.cppには適当なデータ構造を放り込んでいこうと思います。今のところunion-findとsegment-treeのみ。
cormath.cppには適当な数学関数を入れていこうと思います。今のところ最大公約数と素数判定、指数関数と二項係数です。
後は文字列操作用の関数を用意していますが色々難しいのでまたあとで上げようと思います。
後者二つは普通に第二引数までの使用の他、第三引数にmodを入れればmodの範囲内で計算してくれます。Pythonのと同じ感じにしたかったんですよね。素因数分解作りかけになっててワロタ

多分見られるはず。もう少し使い方を覚えればもっと色々出来そうだけどまだよく分からない。プッシュってなんだ、なんか押すのか。

眠い。さらば。

緑になったよ！

おはようございます。

金ローで千と千尋の神隠しやってましたね。面白かったです。
ジブリ作品ってどうしてああも惹かれるものがあるんでしょうか。千と千尋の神隠しは音楽も世界も含めて一番好きな映画です。

金ローよりも前の話になりますが、AtCoderでついに緑になりました！

atcoder.jp

コルボーシュ・ヴィ・ブリタニア「ここでプログラミングをさせてください！」
sabaー婆「贅沢な名だねぇ、今日からお前はこるぼーだよ」
こるぼー「すぐに追い抜いてやるからな……」

……なんてことがあってプログラミングを始めて早5か月。
色々と寄り道したけど、そろそろsabaを追い越す日も近いかもしれません。（水パフォ安定して出せてるし（>‿<））
緑になったことだしアイコンの服の色緑にしようかな？

話は変わりますが、最近JavaScriptに手を出しています。
折角競技プログラミングでアルゴリズムの知識を蓄えていることだしと思い、練習がてらCanvasで図形を描いてみました。一応本を参考にしていますが、丸写しすると謂れのない不安感に襲われるので、結局自分で書きなおす羽目になりました。

まずはダイヤモンド型。円周上の円のn分点を互いに結ぶことで描けます。（二重ループで出来ます）

n分点の指定には三角関数を使って対応します。ようやく数学が役に立ち始めた感じがあって楽しい。

次はドラゴンカーブ。再帰関数を使って実装したんですが、なんでこんなんになるのかはあまり自信がありません。

再帰呼び出しの回数を増やすともっとフラクタルなのがより分かりやすくなります。

最後はMandelbrot集合。本に書いてあるのを参考に書きました。
これもフラクタル図形のようです。この模様キモくていいですね。

とまあこんな感じで、一応順調に進んでいます。（html周りの知識がないのでたまに困りますが）

ではおやすみなさい。

基本的な計算量まとめ

おはようございます。

いつぞやの記事で大ざっぱな意味を書いた覚えがあるんですが、計算量の評価についてのあれこれをメモしておこうと思います。

知っているとTLEなどを防ぎやすくなるだけでなく、解法を思いつきやすいという利点があるので計算量評価に慣れることは有効だと思います。

・計算量とは
コンピューターに何らかの処理をさせるとき、その処理にかかる時間は処理内容によります。
元を辿ればコンピューターは電子回路で設計されているので、同じような内容でも各計算事に若干の誤差は考えられますが、使用者である僕たちが認識することの出来ない程度の誤差なので無視しても問題ありません。

・ランダウの記号
よく見るO()の記号。競技プログラミングではもっぱら計算量の評価に使われますが、本来は数学で関数の挙動を考える時、漸近的な評価に対して用いる記法です。
プログラミングで計算量を評価するために使う定義は次のようにすればよいかと思います。
「十分大きな全ての実数xに対して定義されている実数値関数f(x)、g(x)に対し、
が である」
を
「実数が存在し、となる」
と定義する。
これだと大雑把すぎる評価を招きかねないですが、より厳密な評価が得られる場合はそれより緩い評価は使わないとしておけば十分でしょう。
厳密な解析が難しいものもあるので、この方がよいと思います。

・ランダウ記号の性質
（積と和の評価）
（合成しても同じ）
（線形っぽいやつ）
（ランダウ記号の和）
（ランダウ記号の積）
（定数kは無視できます）
（定数倍は1と表記します）

……正直もっと厳密なのが書けそうですが、実用的には使い方を覚える方が大事なので余り気にしないことにします。（これを見た人がもっといいのを知っていたら是非教えてください）

・
定数倍ですね。宣言、代入などがこれに当たります。

・
定数倍の処理をN回繰り返す場合が該当します。上の面倒な性質を使うと、
（定数）×N = O(1 × N) = O(N)
みたいな感じで評価できます。

・
バブルソートなどが該当します。定数倍の処理の回数が1+2+3+…+N = N(N+1)/2 なので、最大次数の項以外の項や定数倍を無視することで評価が得られます。

・
二分探索などが該当します。要素数を2で割っていくので、その回数をxとすると
大体とするとx = logNとなります。
対数なのでとても高速です。

利用例として、昨日のD問題（https://atcoder.jp/contests/abc134/tasks/abc134_d）の計算量の評価として
O(N+N/2+N/3+…+N/N) = O(N(1+1/2+1/3+...+1/N))
と考えて、
を図を描いて、積分を使って上から評価してやるとO(logN)になるので、結局
O(NlogN)と見積もることが出来たりします。

以上の組み合わせで、基本的な計算量は評価できます。さらばTLE。

ではおやすみなさい。

mod付きの二項係数を使ってみる

おはようございます。今日も夢月ロアちゃんが可愛いです。

この間のmod二項係数、折角実装したことだし使ってみるかと思い、問題を二問解いてみました。

atcoder.jp
atcoder.jp

C++なのにmain関数が数行で済んでしまった、暴力なのだ……なのだで思い出したんですが、夢月ロアちゃんというVtuberが天使のように天使です。友人諸氏はこんな駄文読んでないで早く動画を見に行ってください。

美玲先生のDMを晒しまくる夢月ロアちゃん初回配信まとめ - ニコニコ動画

ロアちゃんの動画を見るのに忙しくてこんなブログ書いてる場合じゃないんですが、記録は大事なので仕方なく実装しておきます。

long long mod_pow(long long a, long long b, long long mod){
    if(b == 0) return 1;
    if(b % 2 == 0){
        long long d = mod_pow(a,b/2,mod);
        return (d*d)%mod;
    }else return a%mod*mod_pow(a,b-1,mod)%mod;
}
long long mod_combination(long long n,long long r,long long mod){
    if(r > n) return 0;
    if(n == r || r == 0) return 1;
    long long fact1 = 1,fact2 = 1;
    for(long long i = n; i >= n-r+1; i--) fact1 = fact1*i%mod;
    for(long long i = r; i >= 1; i--) fact2 = fact2*i%mod;
    return fact1*mod_pow(fact2,mod-2,mod)%mod;
}

まずは経路。高校数学で何度見たかって感じですね。
進む手順は(W-1)個の右向きの矢印と(H-1)個の上向きの矢印で表されるので、これらの並び替えの総数で表現可能。
よって、(H+W-2)!/{(H-1)!(W-1)!} = (H+W-2)C(H-1)で計算すればよい。

int main(){
    long long W,H; cin >> W >> H;
    cout << mod_combination(W+H-2,H-1,1e9+7);
}

関数貼るだけで終わるの、暴力だな？
便利なデータ構造とかは予め実装しておくことにしよう。

次は何とかかんとかいう問題。
かかる操作の回数が最小→連続している青いボールは一度に回収される。
なので赤の隙間（両端を含むのでN-K+1個隙間がある）からi個選んで、各場合について、各隙間最低青ボールが一個は入るような並べ方の総数を考えればOK。
赤の隙間を選ぶのは(N-K+1)Ci通り
青ボールの詰め方は｜（仕切り、ここでは赤ボール）と◯（青ボール）の並び替えを考えればよくて、最小でも各隙間に一個は入らないと行けない。
◯の数はK個、｜の数はi-1個なので、◯の隙間に｜を入れればよいので(K-1)C(i-1)通り。
結局(N-K+1)Ci×(K-1)C(i-1)通りを1e9+7で割った余りを求めればよい。
なので後は暴力をします。

int main(){
    const long long mod = 1e9+7;
    long long n,k; cin >> n >> k;
    for(long long i = 1; i <= k; i++) cout << mod_combination(n-k+1,i,mod)*mod_combination(k-1,i-1,mod)%(mod) << endl;
}

ロアちゃんかわいいって感じですね。どうでもいいけど学生証見つかりました。

ではおやすみなさい。

自作の関数の保存というのをやってみました

おはようございます、すっかり冬休みですね。今日も夢月ロアちゃんが可愛いです。

2週間何してたんだ？（不敵に笑う麻生さんの画像）とかやるのやめてください。何もしていません。
何もしてない割に学生証なくしたりして散々です。自殺～！

前置き長いと某ーたくんとかに嫌味を言われるので、さっさと本題に入ります。

いくつか、関数とかデータ構造を実装したのでここに載せておきます。

本当は関数テンプレートとかなんとかすればもっと便利なのが使えると思うんですが、某cebookの創設者が言っているようにとりあえず完成させました。

今回実装したのは次の3つです。

1．mod付き指数関数

その名の通り、modの範囲で整数のべき乗を求めます。
数学関数だけど、競プロはたまに使うっぽいので保存しておくことにしました。

//関数名：mod_pow
//概要：modつき指数関数
//第一引数a：指数の底
//第二引数b：指数
//第三引数mod：法となる値
//戻り値：a^b(m mod)
long long mod_pow(long long a, long long b, long long mod){
    if(b == 0) return 1;
    if(b % 2 == 0){
        long long d = mod_pow(a,b/2,mod);
        return (d*d)%mod;
    }else return a%mod*mod_pow(a,b-1,mod)%mod;
}

まあ、これは次の関数の為に作ったと言っても過言ではないです。

2．mod付き二項係数

modの範囲で二項係数を求めます。
「普通に二項係数を求めたい！」「long long int型以外も使いたい！」みたいなのは知りません、普通の二項係数なら簡単に実装出来ると思うのでどうぞ。

二項係数を知らない人（中学生がこんなブログを見るか知らんけど）に向けて簡単に説明を書いておきます。

二項係数nCrとは、n個の異なるものからr個を選ぶときの選び方の総数です。数Aでやります。
例えば5個のボールに1から5までの番号が振られているとして、この中からボールを3個選ぶとすると、
(1,2,3),(1,2,4)(1,2,5)
(2,3,4),(2,3,5)
(3,4,5)
の6通りです。しかし全列挙していては手間なので、計算方法が考案されています。
まず、n個のものからr個の物を取り出して並べるような並べ方の総数（これはnPrと表記されます）を求めてみましょう。
上の例で5P3を求めるなら、まず5個のうちから1つ選んで並べ、残った4個から選んで……とやると、
5P3 = 5×4×3 = 60 （通り）
が分かります。同様に、
nPr = n(n-1)(n-2)……(n-r+1)
となります。
さて、nCrというのはn個のものからr個を選ぶときの選び方の総数なので、nPrはこの選び方1つに対し、r!の並び替え方を掛け合わせたものという事が分かります。つまり、
nCr×r! = nPr
という事になります。なので、結局
nCr = n!/{(n-r)!r!}
とすればよいことが分かります。
表し方がいくつかあるので、状況に応じて使い分けるのがいいと思います。詳しくは高校数学の美しい物語とか見てみるといいかもしれません。

さて、この実装は階乗の計算か、掛け算と割り算を交互にやっていけばいけそうです。（もちろんオーバーフローに気を付ける必要はありますが）
しかしmodの範囲ではそうはいきません。何しろ上手く割り算が出来ないので。

ただし、modが素数の場合は別です。フェルマーの小定理（知らん人はググって）から考えると、割り算は出来なくても割り算相当の演算ができます。
次に掛け算をしたら1と合同であるような数、すなわち逆元を求めればよいことになります。
というわけで、aで割る代わりにa^(mod-2)を掛けたらよさそうですね。
これは掛け算なのでmodでも可能ですし、この指数計算は上の関数を利用することで上手く行きます。
（当然使うときは上の関数もコピペしないといけません）

以下実装です。

//関数名：mod_combination
//概要：modつき二項係数
//第一引数n：組み合わせの全体
//第二引数r：何個取り出すか
//第三引数mod：法となる値
//戻り値：nCr(m mod)
long long mod_combination(long long n,long long r,long long mod){
    if(r > n) return 0;
    if(n == r || r == 0) return 1;
    long long fact1 = 1,fact2 = 1;
    for(long long i = n; i >= n-r+1; i--) fact1 = fact1*i%mod;
    for(long long i = r; i >= 1; i--) fact2 = fact2*i%mod;
    return fact1*mod_pow(fact2,mod-2,mod)%mod;
}

3．Union-find

Union-findはグループ分けの為のデータ構造です。
グラフを連結したり、各要素が繋がっているかの判定を行ったり、属しているグループの要素数を求めたりできます。
これらは他のアルゴリズムでも出来なくはないですが、実装が大変だったり時間がかかったりします。

データ構造はこれの他にも二分探索木とか実装してあるんですが、貼る気が起きないのでやめておきます。
以下実装です。

//unionfind
//根にはグループの要素数（負）、それ以外には根の値
//初期値は-1
vector<int> uni(100000,-1);
//引数aの根を求める、なければaを根として返す
int root(int a){
    if(uni[a] < 0) return a;
    return uni[a] = root(uni[a]);  
}
//頂点aとbを繋ぐ
//元々同じグループであればfalse
bool unite(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;
    if(uni[a] > uni[b]) swap(a,b);
    uni[a] += uni[b];
    uni[b] = a;
    return true;
}
//頂点aとbが同じグループかを調べる
bool isconnected(int a, int b){
    return root(a) == root(b);
}
//頂点aを含むグループの頂点数を調べる
int unisize(int a){
    return -uni[root(a)];
}

以上が最近の成果になります。
あまりめぼしいのがないので、今週は頑張りたいと思います。差し当たっては失くした学生証を見つけようと思います。

ではおやすみなさい。僕は交番に行ってきます。