「そこにある」ってどう確かめるの？プログラミングで学ぶ唯物論
A.bool値を使う！
終。
はい、ということでタイトル詐欺からスタートいたしました。ベリーソーリー。
ただプログラミングって本質的に唯物論者じゃないと無理じゃないすか？数字でどうこう表せないけど「でもそこに愛があるから……」とか抜かす人ぶん殴りたくなるでしょたぶん。
ということでこの記事を読んでいる情報のオタクとうっかりでクリックしてしまった一部の哲学オタクである紳士淑女の皆様は唯物論者です。そのような皆様は(ある/なし)を個数や数値で判断できるんです。今回は数の表し方について学んでいきましょう。
1.存在性の証明
A.配列
プログラミングにおいて我々が存在を認識する瞬間とは何か。それはその値や文字列があるかないかで判断するだろう。素朴な発想ではそれがいくつあるかで判断するに違いない。もし0個なら「ない」、それ以外なら「ある」。all or nothingの精神だ。
ここでは簡単に数としよう。ある数がそこに存在するかどうかをどう判断すべきか。 もちろん配列を使うべきだ。我々は唯物論者であるため、素朴に自分の見た物の存在を記録すればよい。
例えば、
サイズ$${N}$$の非負整数列$${A(0\le A_{i}\le 10,000|i=1,2…N)}$$が存在する。
$${Q}$$個のクエリが与えられる。各クエリで与えられた非負整数$${q(0≦q≦10,000)}$$が整数列$${A}$$に存在するかをそれぞれ判定せよ。
といった問題が与えられたとする。唯物論者はこれをお気持ちやフィーリング、超能力では解けない。残念なことにあるかないかを実際に確かめなくてはならない。こんな風に。
#include <bits/stdc++.h>
using namespace std;
vector<long long> A(10010, 0);
int main() {
long long N;
cin >> N;
while (N--) {
long long x;
cin >> x;
A[x] += 1;
}
long long Q;
cin >> Q;
while (Q--) {
long long q;
cin >> q;
if (A[q]) {
cout << "exist!" << endl;
} else {
cout << "not exist!" << endl;
}
}
}これが配列による存在性の証明である。コンピューターに数を読ませ、その個数を逐次記録することで、後で特定の値にアクセスした時にその数の存在性を簡単に判断する事ができる。実にクールだ。
B.木(特に二分探索木)
一方で、そうでない判断方法もあるだろう。外に出てみて欲しい。数々の動植物が春の訪れをいつかいつかと待ちわびているではないか。これこそが美しさであり、これこそが生ではないか！Life is beautiful!!!
ところで生を語源としたとされる言葉に木というものがある。木とは何か。その辺に生えてるやつだよね？違う違う。一般に情報のオタクは外に出ず、ただの猫背を丸め誤差と言い張って身長を盛る事で有名なのだからそんなもの知らないに決まっている。
木はもちろん連結で閉路を持たないグラフである。特にその中の二分探索木という小さいのと大きいのとで2つに割って振り分けるアルゴリズムを使うと多くのデータに高速でアクセスできる。たぬかなは二分探索木を作成中に唯心論者の妨害を受け、無職となった。アーメン。
ともかく、二分探索木は優れたアルゴリズムである。上の問題を二分探索木を用いて解いてみよう。ここでは二分探索木で実装されたコンテナであるmapを使う。
#include <bits/stdc++.h>
using namespace std;
map<long long, long long> A;
int main() {
long long N;
cin >> N;
while (N--) {
long long x;
cin >> x;
A[x] += 1;
}
long long Q;
cin >> Q;
while (Q--) {
long long q;
cin >> q;
if (A[q]) {
cout << "exist!" << endl;
} else {
cout << "not exist!" << endl;
}
}
}以上のようになる。ここからはこれら2つの利点、欠点について説明する。
閑話.鬼滅の刃面白いよね！
こんな問いを考えた事はないだろうか。
このキャラクターって所詮空想にすぎないのかな？それとも心の中に存在するから実際に存在するのかな？
いや待てそもそも心って何？存在って何？俺や私や彼や彼女や先生や犬や猫も所詮はパラメータやデータの結晶体でしかなく、本当にそれはあるっていうの？それら結晶体とキャラクターには何の違いがあるの？そこに実在と非実在とで区別する違いはあるの？
「意思を持つものが実在している。」と言っても所詮それは0と1のビットをたくさん集め、それらによって脳の電気信号が作られ、それが判断を決定しているにすぎないんじゃないの？じゃあ「本物」って何？
今見ているこれも、聞いているこの音も、感じている気持ちも、電気信号によってそうなっているように錯覚しているに過ぎないんじゃないの？結局それは「本物」なの？
ゲームで我々がキャラクターの行動を外界からコントロールするように、我々も外界からコントロールされているんじゃないの？
この世界は「本当に」あるの？
「俺は本物が欲しい、うがががが。」
書いててめちゃくちゃめちゃくちゃめちゃくちゃ恥ずかしくなった。28:30に何書いてるんだろ。20歳超えたジジイにこんな小便臭い文書かせんといてください。見つかったら就活に響く。
とはいえこれはアイデンティティーの揺らぎから来る問いであり、そしてどういうわけかこれは万人がめちゃくちゃ好きでハマる問いである。「真実の愛」を探し、嘯き、それに振り回されるものは今昔世界中に大勢いる。「B4の紙切れに収まる僕の人生」に疑問を持つ人はあまりにもベタすぎてもはや創作ですら出てこない。
あなたの好きな小説やライトノベルの主人公もこういった問いでよく悩んでたでしょう。
「人間関係なんて所詮表面上の存在。俺の本質は誰にも分からない。自分ですら分からない。」とかいう拗らせた主人公。きっと今この記事を読んでいるであろう10年代の当時中高生のオタクに多大な影響を与え、黒歴史を量産させたことでお馴染み比企谷八幡君です。
彼はこの世の多くの人がぶつかり、悩み、苦しむであろう問いを中高生にありがちな全能感でさも自分だけが悩んでいるかのように勘違い、特権意識を持ち、なんか上から「俺はお前らより物知ってるし考えてるぞ。国語の点もいいし。」って雰囲気で消極的虚無主義から来る謎のアレソレをいっぱい抜かしたあげく、同じ部活内で自分が年齢や知識面で優位が取れるという理由で母校に頻繫に顔出しして多感な時期の高校生の人間関係に頻繫に茶々入れてくる本当に終わっている大学生の姉がいる貧乳の彼女作って全てなあなあで片つけましたね。
ま、人ってそんなもんだよね。たぶん彼も大学生になったら突然夜中に過去の出来事がフラッシュバックしてベッドで暴れ回っとります。ガハハ！
人は様々な事象が多元的に絡み、非常に複雑な事物を理解、吸収するために脳内で単純化、圧縮、矮小化し、ついつい0か1かだけで評価を付けたがります。それは一般に完璧主義的思考の特徴と言われ、抑うつ状態によるものでしょう。Twitterの謎界隈は「理解ある彼くん」なるデウス・エクス・マキナが登場していい感じに終わる事に対し終わる事のない論争を繰り広げている点を見るに、俺ガイルも実はそれを皮肉った作品なのかもしれませんね。登場人物やべー奴ばっかだし。
ということで閑話休題。今から0/1の世界に戻りましょう。お前らを病ませてやる。
2.道具の選択
先ほど紹介したようにプログラミングにおける存在性の証明には以上の2つが使われる事が多い。ではこれらのどちらを使ってもいいかというと必ずしもそうではない。ここではこの2つのメリット、デメリットについて考察しよう。
配列使用のメリット
値の参照が$${O(1)}$$で済む。これが最も大きい。存在するかどうかをごくごく軽量の時間で確認できる。我々はこの世界に$${100,000}$$という数字が存在するか確かめるために、一々リストを$${100,000}$$回辿る必要がない。$${A_{100000}}$$の値を見るだけで事が終るのだ。
配列使用のデメリット
コンストラクタに時間を食うのが大きい。世界に$${100,000}$$という値があるかどうかを確かめるためにはそれ以上のスペースを確保しなくてはならない。配列のコンストラクタの計算量は$${O(配列のサイズ)}$$となる。めちゃくちゃざっくりとした解釈だが$${O(max(A))}$$としていい。来そうな値の最大量は枠を取っておく必要がある。
という事はもし$${1,000,000,000}$$が来るとなるとちょっとしんどいだろう。我らが誇らない電通大はこの額は出せない。もしこのnoteを見て電通大を助けたいな～と思ったそこの貴方！まず私にご連絡ください。私がお金まとめて電通大に渡します！！！何かしらの税金的な大人の事情らしき関係で一億最低ラインね！！！よろしゅう。
木のメリット
前計算が$${O(1)}$$。これが強い。事前に来るかも分からない数値の存在に怯えてわざわざスペースを空けておく必要がないのだ。我々が夜安心して寝られるのも木のお陰である。嘘だけどね。
木のデメリット
値の追加、値の参照に$${O(log(木のサイズ))}$$がかかる.残念ながら前計算無しの帳尻合わせはどこかでしなければならない。
一番最初に紹介した$${N}$$個データを追加し、その後に$${Q}$$回参照するだと計算量は$${O(N log N+Q log N)}$$である。これは$${log}$$の和を求める事で計算がしやすいだろう。
一方で上の問題を配列で解いた場合、計算量は$${O(max(A)+N+Q)}$$となる。$${O(max(A))}$$次第では配列の方が計算量を節約できるのが分かるだろう。ここが大事である。
3.具体例
値の存在性を担保するために配列を使うべきか、木を使うべきか、それは$${max(A)}$$次第である事を理解してもらえただろうか。具体的な問題を見て判断していこう。
この問題は配列による参照を使ってはいけない典型である。見ての通り、値の上限が$${10^{9}}$$と大きく、配列によって階層の繋がりを表現しようとすると情報がないスペースを無数に作らされることとなり間に合わない。
従ってこれは木を用いて解く事が想定解である。特定の階をkeyとし,それに繋がる階をまとめてvalueとする事で数値が大きい場合でも十分に解く事ができる。
もしかしたら「座標圧縮で解けたぞ」という声もあるかもしれない。しかしあれは形の上では配列を使っているが、本質ではlower_bound函数によって二分探索木上でのその値の位置を出している点で木を用いていると解釈する。
一方で木を用いてはいけない場合も存在する。先ほどの問題はグラフなのに頂点数と頂点番号に著しい乖離がある点で珍しいが、こと競技プログラミングにおいてはそう多くない。どちらかというと頂点数と頂点番号の上限が一致する事がほとんどである。つまり、$${N=max(A)}$$である事が非常に多い。
こうなるともはや木を使う事のメリットは非常に薄く、ただ計算量$${O(log N)}$$相当だけ遅くなる。その最たる例が以下の問題である。
この問題の本質はTakahashiとAokiが存在する頂点の位置が前のいずれかの移動による頂点の位置と同じになった場合、それ以上を考える必要が一切なく、そもそも記録すらしなくていいという点にある。
つまり、この2人がある頂点ペアにいつ最速で辿り着くかだけを記録し、処理すればいい。
配列の値参照が$${O(1)}$$で出来る事を鑑みると、これによってクエリ1つ辺りの計算量が頂点ペアの組み合わせの個数である$${O(N^{2})}$$またはある頂点から生える辺の本数の最大値が$${M}$$本である事を活かし、TakahashiとTaroの行き先の決め方から$${O(N^{2}+M^{2})}$$となると分かる。
その記録方法には様々な方法があるが、なるべく最速のものから順々に試したいという点で配列とqueueを用いて記録と処理を行うのが鉄板だろう。
このような特定の位置に到達する最速手数を記録し、それをqueueに格納して手数の小さい順に処理する事で、目的地までの最短手数を求める手法を幅優先探索(BFS)という。
話を戻そう。この問題は制約から明らかなように$${N=max(A)}$$型の問題である。これに木を使った場合どうなるか。
(^_^;;;)
……
……
……
……
…
.
はい。
一応失敗の理由を書く。上の提出例を見てもらいたい。お分かりであるかと思われるが木において存在を参照する場合に付く$${O(log N)}$$が致命的であった。
先程言及した通り、ペアの組み合わせは最大で$${N^2}$$であるため、木を使うとまず値の参照だけで計算量$${O(log N^{2})=O(log N)}$$がのしかかる。
しかも今回はこれに加え値を挿入するため、嫌なタイプの手間と暇がかかってしまった。
計算量の見積もりが正しければこの問題で木を使う事で今回$$(O((log N)^{2}))$$だけ計算量が上乗せされるはずだ。あまり自信がない。
そうであると仮定すると$${log 2000≅10}$$となるため今回は約$${100}$$倍だけ重たくなってしまった。$${O}$$記号はあくまで計算量の最悪見積もりを表すものであり、本来はこのように比較をする事が適切なツールではないのだが、ともかくよろしくない事をしているのが理解できただろう。
$${O(N^{2} (log N)^{2})}$$はNが2000の時、$${O(10^{9})}$$となる。このため意図的に用意された最悪計算量に近くなる苦しいケースを残念ながら通過できなかった。
4.総括
前計算でTLEを警戒する程に$${max(A)}$$が大きい、与えられた数列に小数があるもしくは数列ではなく文字列の集合であり、かつ値の上下や辞書式順序によって整頓してからの対応が必要である場合には木の使用を検討しよう。
もしソートをかけるならば、逆にいうとソートをしても時間が大丈夫であると見積もれる場合は木を使ってもあまり問題にならないケースが多いためである。尤も文字列のソートや桁が多い場合のソートは慎重になるべきだが。
逆にいうとそうでない場合、$${N=max(A)}$$型の問題やソートがいらない配列による番号付けで間に合う場合には木を使う必要は全くない。
配列が活用されるどの問題も配列の要素数$${N}$$個だけデータを受け取る$${O(N)}$$時間は避けられず、受け入れるしかないためだ。
競技プログラミングの問題は$${O(N)}$$は保証されている事がほとんどであるため、配列による値の記録も「ついで」にやることができる。入力受け取ってる最中にTLEなったらクソゲーです。
これは自分を含めた初級者～中級者にありがちだがつい何らかの技やアルゴリズムを使いたくなってしまう。高度なアルゴリズムを綺麗に使う、技巧的に問題を解く上級者は非常に魅力的であろう。
ただそれは多くの場合、既存の手段が上手く行かない、計算量的な問題が大きいから開発されたものであり、まず典型の手段を試そうとせずにすぐアルゴリズムや技に走るのはその問題の理解をブラックボックスとしてしまう点でもあまりいい効能をもたらさない。
我々は技を使って問題を解くのではなく、問題を解くために技を使うのだ。決してあるアルゴリズムを使いたいからという理由で問題を解くべきではない。それは手段の一つでしかないからである。
どうですかみなさん？もしかして区間和を求める問題をめんどいからってセグ木でやってませんか？それ、累積和の差分で良くない？遅いよ笑。
当たり前のこと、計算量が少ないものを検討した後に初めて技やアルゴリズムを使えるかを考えるべきだろう。同じことができるなら地味であっても計算量が少ない方を優先すべきだ。それはどんなテストケースが来るかは分からないからである。私のように1TLEが通らず辛酸を舐める事があるかもしれない。たとえ$${O(log N)}$$だけ遅くてもあまり軽視すべきではない。
纏めると基礎基本の把握、計算量の理解は非常に大事である。例え解けたとしても自分が大雑把なコードを書いていないか、そこに無駄がないか、それを意識するとまた一歩上に行けるだろう。反省と振り返りは非常に大事だ。
大変長くなってしまった。ここまでお読みいただきありがとうございました。
次回、「『存在証明 愛だって愛だって吐いたって』ってどういう事？－ダーリンダンスから学ぶ唯心論」こうご期待。
5.おまけ
このせいで昨日入水できなかった。ざ～こ💕
6.参考文献
この記事が気に入ったらサポートをしてみませんか？