ロアちゃんかわいい

競プロっぽい話がなされる駄文の掃きだめ

緑になったよ!

おはようございます。

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

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

atcoder.jp

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

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

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

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

f:id:zero_kpr:20190818033848p:plain

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

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

f:id:zero_kpr:20190818035415p:plain

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

f:id:zero_kpr:20190818035432p:plain

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

f:id:zero_kpr:20190818034821p:plain

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

ではおやすみなさい。

基本的な計算量まとめ

おはようございます。

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

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

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

ランダウの記号
よく見るO()の記号。競技プログラミングではもっぱら計算量の評価に使われますが、本来は数学で関数の挙動を考える時、漸近的な評価に対して用いる記法です。
プログラミングで計算量を評価するために使う定義は次のようにすればよいかと思います。
「十分大きな全ての実数xに対して定義されている実数値関数f(x)、g(x)に対し、
 f(x) O(g(x)) である」

「実数 x_0, Mが存在し、 x > x_0 ⇒ f(x) < Mg(x)となる」
と定義する。
これだと大雑把すぎる評価を招きかねないですが、より厳密な評価が得られる場合はそれより緩い評価は使わないとしておけば十分でしょう。
厳密な解析が難しいものもあるので、この方がよいと思います。

ランダウ記号の性質
 f_1(x) = O(g_1(x)), f_2(x) = O(g_2(x)) ⇒ f_1(x)f_2(x) = O(g_1(x)g_2(x)), f_1(x) + f_2(x) = O(g_1(x)) + O(g_2(x)) (積と和の評価)
 O(O(f)) = O(f) (合成しても同じ)
 O(f + g) = O(f) + O(g) (線形っぽいやつ)
 O(f) + O(g) = O(max{O(f), O(g)})ランダウ記号の和)
 O(f)O(g) = O(fg)ランダウ記号の積)
 O(kf) = O(f) (定数kは無視できます)
 O(c) = O(1) (定数倍は1と表記します)

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

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

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

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

O(logN)
二分探索などが該当します。要素数を2で割っていくので、その回数をxとすると
大体2^x = Nとすると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))
と考えて、
 \sum_{k=1}^{N} \frac{1}{k} を図を描いて、積分を使って上から評価してやると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)];
}

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

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

典型攻略:絶対値の和の最小化

おはようございます。 明日から夏休みですね。

DP記事とか言うのは知りません。(もうちょっとかかりそうです)

ここまで解いた問題で2回使うことになった内容なので知識として記録しときます。

TeX記法とかいうので表示する練習も兼ねています。上手く表示されない場合はご一報ください~。

実数列a_{i}(1≦i≦n)に対して
\sum_{i=1}^{n}|a_{i} - x|
というxの関数を考えます。
この式をf(x)と置くと、y=f(x)は折れ線のグラフを書きます。
絶対値の和なのでf(x) ≧0は明らかですが、これはxをどこまでも小さく、あるいは大きくしていくと、無限大に発散することがわかります。
この関数の最小値を与えるxを考えます。

さて、最小値を求めるにはどうしたらよいでしょうか?
結論から言うと、xがa_{i}の中央値になる時にf(x)は最小になります。
例えば数直線で級数の各項はxとa_{i}の距離なので、xの右にa_{i}がn個ある時にxを右に1動かしたらf(x)の値はn減ることがわかります。
それぞれの点にxが1だけ近づくので。

xが右にΔx動くとすると、右にn個a{i}があればf(x)は当然nΔx減ります。
xの左にm個a_{i}があるなら、右にxを1動かすとf(x)はm"増え"ます。
なのでxの左と右にあるa_{i}の個数が等しくなる時に値が最小でーす。

勝った!第三部完!
一見当たり前だけど!こういう典型知識の積み重ねがなんかいい感じにあれするんですよ!

以下使う問題です。(なんか2017年の慶應医数学で似た問題が出てたみたいです。こういう各場合にxをちょっとずらして考えていくみたいな発想は受験生諸氏も覚えておくといいかもしれません)

C - Linear Approximation

B - AtCoder Market

ではおやすみなさい~。

茶色になったしC問題も実装できたぞ!

おはようございます。(今回の記事は例の如く、流れが分からない人は第一回を見てください。)

 

茶色になった!

 

f:id:zero_kpr:20190422010919p:plain

 

謎の新生物こと私こるぼーですが、ABCのコンテスト中にC問題を実装して、さらに茶色になったのでこの度進化しました。

自撮りです↓

f:id:zero_kpr:20190422012611j:plain

これが

 

 

f:id:zero_kpr:20190422011310j:plain

 

ちょっと成長して腕とか固まりました。まっくろくろすけとはもう呼ばせない。

 

このまま精進して最強の新生物になるね!

 

おやすみなさい!

プログラムってどこに書いたらいいんですか?

おはようございます。

 

今日はテキストエディタとかいうやつの話です。

 

前回、前々回とプログラムの書き方を習ったわけなんですが、そもそもプログラムってどこに書いたらいいでしょう?

 

これまではAtCoderのコードテスト(※前回記事のAPG4bに載ってたはずです)に直接書いてたんですが、みんななんかかっこいいやつをpcに入れてる。ぼくもあれほしい。

 

例えばゲームをやったりする時に動くプログラムはPCのどっかに保存されてるわけです。しかしどこに書けばええんや?

 

それで調べたら出てくるのがこれです。

 

メ モ 帳

 

おちょくってんのか?

 

……と思いましたが、どうやら本当らしいです。

 

適当なメモ取る時に使うだけじゃなかったんかお前……

 

プログラムって結局は文字列で出来てる情報なので、書けて保存出来れば何でもいいらしいです。書いて保存するためのソフトウェアをテキストエディタといいます。

 

メモ帳はWindowsに最初から入ってますが、もっと便利なテキストエディタが色々と開発されているらしいです。

 

沢山あってよく分からんので適当なのを入れよう!

 

https://azure.microsoft.com/ja-jp/products/visual-studio-code/

 

Visual Studio Code!通称VScode、なんだか高機能らしいです。

 

とにかくこれで書きやすくなるわけですね。

 

早速使ってみましょう!

 

ç»å

 

なんだかかっこいいですね。

 

このVSCode、最初は機能とかも全部英語で書かれてるんですが、拡張機能(expansion)とやらの項目で日本語化機能をインストールすると日本語表示ができます。英語あんまり読めないので助かります。

 

これで狂気のマッドサイエンティストに一歩近づけたような気がするぞ!

 

でもなんだか味気ないですよねこれ。他のみんなのを見てると文字に色ついてるんですよ。

 

おかしいなーなんでぼくのは色ついてないんだろーなーと思って色々調べると、どうやら使用言語を選べるようです。

よく考えるとテキストエディタの方で使う言語を認識できるはずないんで、こっちから選ばなきゃいけないのも当然なんですが、これ分かるまでにかなりの時間を要しました。

ç»å

 

VSCode画面の右下の方が↑のようになっているので、「プレーンテキスト」をクリックします。すると言語を選択できるので、そこからc++だのpythonだのを選べばいいわけです。

 

実際にやってみましょう。

 

ç»å

 

すごい!色が付いた!世界は美しい!ありがとう!ありがとう!第3部完ッ!

 

これで書きやすくなったね!書いたプログラムをどうやって動かせばいいのかとかよく分からんので後回し!

 

今回は以上!さよなら!さよなら!