AtCoder ABC149F「Surrounded Nodes」で木DPに落とすまでってそんなに簡単じゃないよねっていう話

はじめに

多分はじめて競技プログラミングの記事をかきます。ashiato45です。気にする方のために始めに申しますと、私はAtCoder水色ですので「黄未満のやつの書いた記事なんか読むだけ時間の無駄。」という方はお引き取りください。

追記(4/5)

コメントでid:sugarknri さんが解説1の解説をしてくださいました！

これは何？

F - Surrounded Nodesは「期待値の線形性」を使って最終的に木DPに落ちるのですが、そこに到達するまでの期待値の考察は、確率の独立性に関する落とし穴があるよねと思っています。参加記や公式解説を読んでも誰もそのことに言及してないのであれこれ僕がおかしいんですか誰か教えてくださいっていう記事です。

あと、公式解説や他の方の説明を読んでも木DPに落とすまでがピンと来てないという方の役に立つかもしれません。

経緯

e869120さんの力作記事に
qiita.com
というのがありこれを解いていたのですが、どうしても上記ABC149Fの解説2がよくわからなくて困ってしまいました。
2、3日ぐらい考えたらわかった気がしたしACもしたので共有します。
解説1は余計わかんないです。

偽証明

AtCoderの解説2は初っ端からこのようになっています:

期待値の線形性から、各頂点vについて、vがSに属しかつ白く塗られているような確率を計算し、その合計を求めればよいです。

というのですが、この後「vがSに属し」の話しかせず、白の条件の話をしないのです。これは白の条件が明らかだと皆思っているからなのだと思われますし、解説放送を見てもそんな感じがします。
ちなみに、解説1のスタートはこうなっています:

求めるものは「Sの頂点の個数-黒く塗られた頂点の個数」と等しいです。期待値の線形性から、それぞれの項の期待値が求まればよいです。黒く塗られた頂点の個数の期待値は明らかにN/2です。Sの頂点の個数の期待値を考えます。

これでもいきなりSが出てくるのが結局わからないのですが、つまるところ、問題にある「Tの各頂点を、それぞれ独立に確率 1/2 で黒く、確率 1/2 で白く塗り、」というところから1/2で割って、そこからスタートしているように見えます。この考え方を数式的に表わしてみるとこんな感じになります。ここで、どの要素が何に依存しているかをはっきりされるために、次のような記号をもちいます。

$x\in 2^T$ : Tの塗り分け方。いま考えている確率空間の根源事象ですね。問題文の独立性の仮定よりどのxも出方は同様に確からしいです。
$S_x \subset T$ : Tをxで塗ったときに定まるSを、xが決まってはじめて定まるものだということを強調してこう書きます。
$w_x(v) \in \{0, 1\}$ : $v\in S_x$ を頂点とし、xを塗り分け方としたとき、頂点vが白く塗られているなら1、そうでないなら0を返す関数。
χ(P): 命題Pが成立しているときに1、そうでないときに0をとります。指示関数といいます。

すると、求めたかったのは $S_x$ の穴開き度の期待値だったので、
$\begin{align} &E_{x} [S_xの穴開き度] \\ &= E_{x} [\sum_{v\in S_x} \chi(vは塗り分けxで白) ]\quad (←穴開き度の定義)\\ &= E_{x} [\sum_{v\in T} \chi(v\in S_x 、かつ、 vは塗り分けxで白) ]\quad (←総和の条件を値の側に持ってきた)\\ &= \sum_{v\in T} E_{x} [\chi(v\in S_x 、かつ、vは塗り分けxで白) ]\quad (←期待値の線形性)\\ &= \sum_{v\in T} E_{x} [\chi(v\in S_x )]E_{x} [\chi(vは塗り分けxで白) ]\quad (←「かつ」をかけ算に直す？)\\ &= \frac{1}{2}\sum_{v\in T} E_{x} [\chi(v\in S_x )]\quad (←1/2の確率で白く塗られる)\\ &= \frac{1}{2}\sum_{v\in T} p_{x} [\chi(v\in S_x )]\quad (←指示関数の期待値は結局確率)\\ \end{align}$
さあこれで各頂点について $p_x[v\in S_x]$ 、すなわちvが $S_x$ に入っている確率を求めればよく、そのためには解説にあるように「vがSに含まれるための必要十分条件は…」を考えはじめればよい、ように見えます。

が、上の変形はいろいろ間違っています。

「かつ」をかけ算に直す

上の「「かつ」をかけ算に直す？」でやっているのは結局のところ確率変数X,YについてE[XY]=E[X]E[Y]なのですが、これは一般には成り立ちません。
例えばロシアンルーレットをやっていて、Xが「一人目で死亡のとき1、そうでないとき0」、Yが「二人目で死亡のとき1、そうでないとき0」という確率変数だと思いましょう。
するとXとY両方が1となることはないのですからE[XY]=0ですが、他方E[X]=E[Y]=1/6ですから*1、確かに成り立っていません。

E[XY]=E[X]E[Y]は、確率変数XとYが独立である、という仮定があるなら成立することが知られています。フォーマルにはp(X=x, Y=y)=p(X=x)p(Y=y)という条件で、直感的には「片方の確率変数が取る値を知ったとしても、もう片方の確率変数の出方が偏ったりしない」ということを意味します。例えば、先のロシアンルーレットなら「一人目が死んだ」とわかった、つまりX=1ならば二人目は絶対に安全でY=0が100%と、元のY=1が1/6、Y=0が5/6という確率分布から「偏って」しまいます。反対に「一人目が死ななかった」、つまりX=0だとわかったならば、二人目が死ぬ確率は1/5になりましたから何も知らなかったときより緊張感が増すことになります。

今回、「 $v\in S_x$ 」と「vは塗り分けxで白」は独立でしょうか*2。
これは実は独立ではありません。なぜなら、今回の問題のSの「黒く塗られた頂点を全て含む」という定義からvが塗り分けxで黒だと分かったときは、 $v\in S_x$ が100%成立してしまうからです。
ですから、当然このかけ算をわけることはできず、またそこを1/2と切り分けて先に進んでしまうことはできないのです。

ちなみに、ランダムにSを取ってきたときに(まずそれが意味不明ですが)、そこにあらわれる白黒も平均|S|/2ぐらいでしょうと仰るかたもいるかもしれませんが、それも同様の理由で意味不明です。

でもこれ結局正しいじゃん

確かに最後に得られる式は正しいのですが過程が間違っています。推論を正しく進めるには、解説2にある次の考察がカギになります:

頂点vについて、Tからvを取り除いてできる部分木たちを $T_{v1}, T_{v2}$ とします。このとき、vがSに含まれるための必要十分条件は、 $T_{vi}$ たちのうち少なくとも2つが黒く塗られた頂点を含むこと

と言っているのですが、これは大変玄人向けで正確には次のようになります:
「vが白く塗られている条件のもので、vがSに含まれるための必要十分条件は、 $T_{vi}$ たちのうち少なくとも2つが黒く塗られた頂点を含むこと」です。論理の講義を思いだしてみて、かつxを強調すればこれはこうなります:
$\begin{align} &(vは塗りかたxで白)∧(v∈S_x)\\ & \iff \\ &(vは塗りかたxで白)∧(T_{vi}たちのうち少なくとも2つが黒く塗られた頂点を含む) \end{align}$
すると、 $T_{vi}$ たちはvを含まないのでvとは関係なく、これら2つの事象は独立になります！この変形をしてはじめて先の推論を正しく進めることができます:
$\begin{align} &E_{x} [S_xの穴開き度] \\ &= \dots (←同様)\\ &= \sum_{v\in T} E_{x} [\chi(v\in S_x 、かつ、vは塗り分けxで白) ]\quad (←期待値の線形性)\\ &= \sum_{v\in T} E_{x} [\chi(T_{vi}たちのうち少なくとも2つが黒い頂点を含む、 \\ & \quad かつ、vは塗り分けxで白) ]\quad (←先の同値！)\\ &= \sum_{v\in T} E_{x} [\chi(T_{vi}たちのうち少なくとも2つが黒い頂点を含む)] E[χ(vはxで白)]\\ &\quad (↑独立性！)\\ &= \frac{1}{2}\sum_{v\in T} E_{x} [\chi(T_{vi}たちのうち少なくとも2つが黒い頂点を含む)]\\ & \quad (↑1/2の確率で白く塗られる)\\ &= \frac{1}{2}\sum_{v\in T} p_{x} [\chi(T_{vi}たちのうち少なくとも2つが黒い頂点を含む)]\\ & \quad (↑指示関数の期待値は結局確率)\\ \end{align}$
これではじめて、木に集中してものを考えることができるはずで、あとは解説どおりです(ここからはここからで木DPになれてないと苦しいのですが)。

おわりに

そういうわけで、解説のギャップ埋めみたいなことをしてみました。多分強い人はこのあたりのことが直感的にわかるのだと思うのですが、私ぐらいだと面くらいましたしひょっとしたら自力で解けた人でも「まあ大体1/2だし1/2で割っとけばいいっしょ～」という方もいたのではないかなと思います。こういうのを考えるのが競技に強くなるのに重要かどうかは知りませんが、納得いかないので考えてみました。

*1:弾倉が6発分ならですが

*2:いつのまにか確率変数の独立から事象の独立になっていますが、「その命題が成立したら1、そうでないとき0」という確率変数と同一視してください

2019-12-26

AngluinのL*アルゴリズムと機械学習(特にRNN)への応用

qiitaのほうにかきました

qiita.com

2019-12-06

ACMアカウントを使ってのO'Reilly Learning Centerへのログインができなくなったときには

ここ(https://learning.acm.org/e-learning/oreilly)にあるとおり、ACM(Association for Computational Machinery、計算機系の学会です)の会員はO'Reilly Learning Centerにアクセスする権利が特典としてあって、英語版のオライリーの本への電子アクセスの権利があります。

しかし、ある日読みたい本ができたのでアクセスしてみようとしたところ
https://twitter.com/ashiato45/status/1201797380116365312/
こんなバーが出てアクセスすることができませんでした。はじめはオライリーのほうに問いあわせたのですが「団体会員の場合はその団体のほうがあまり使ってない会員のアカウントを無効化することがあるからACMのほうに聞いて」と言われました。そこでACMのほうにreactivateをおねがいしたら無事にアクセスできるようになりました。どうも3ヶ月ログインがないアカウントは停止しているようです。

結論としては、

ACMアカウントを使ってのログインに問題が生じたら、オライリーの窓口ではなくてACMのほうに問い合わせましょう。
3ヶ月以内ぐらいの間隔でマメにO'Reillyにログインしましょう。

2019-10-25

concept latticeについて

杉山麿人先生のデータマイニングについての講義を受けていて、concept latticeのところ~~が講義の最後のほうTwitterしてたら分からなくなったので~~の理解を深めるためにぽちぽち調べたり考えたりした記録です。とはいえそんなにちゃんとは調べていないので定義とか間違ってたらごめんなさい。

定義は曖昧さがないように真面目にやっていますが、まあ例だけ拾っていけば読めると思います。

やりたいこと

データがこんな感じで(いまは8つ)与えられたとき、
f:id:sle:20191025172146p:plain:w100
X⊂{A,B,C,D}*1を含む行がいくつあるかを{A,B,C,D}の(包含で順序を入れた)ハッセ図に書き込むことにする。この数をfrequencyとよぶことにする。例えば、ABDのfrequencyは3*2。こんなかんじ:
f:id:sle:20191025172325p:plain:w300
あたりまえだが、書き込まれた数はハッセ図の上にいくにつれ小さくなっていくことになる(順序に関する反対向きの準同型)。この書き込まれた数の情報を保つようなコンパクトな表現がほしいし、またそれにまつわる数学的な構造を知りたい。

closed pattern

[定義: closed pattern]集合S(上の例だと{A,B,C,D}に関する部分集合全体のなすハッセ図とその上に書きこまれた頻度が与えられたときに、P(S)の部分集合Xが頻度nのclosed patternであるとは、Xが頻度nを持つハッセ図上のノード(その頻度が与えられたSの部分集合)の極大元集合のこと((これ別に講義で言われたことではないのだけれど定義が簡単になるので…)。適当な頻度nがあり、Xが頻度nのclosed patternのとき、単にXをclosed patternとよぶ。

例えば、頻度3を持つノードは上図でABD,AB,BD,B,Cがあるが、このうち上限をあつめると{ABD,C}になるので、頻度3のclosed patternは{ABD, C}である。上図ではclosed patternの元たちすべてが赤く記されている。

どの2つのclosed patternを取ってもそれらがdisjointであることは定義より明らか。

このclosed pattern全体とその頻度だけ覚えておけば、(closed patternに載っていないものを含む)どのノードについてもそこに書かれていた頻度を復元することができる。これは、大きい頻度nのclosed patternからすでに数が書き込まれているノードに出会うまで下がっていって、途中で出会ったすべてのノードにnを書き込んでいけばよいからである。例えば:
f:id:sle:20191025173917p:plain:w300
頻度7,5,4はすべて書き込まれているとして頻度3のノードを復元したいとする。Cから下がるともう{}なのでCに3を書き込んでCについては終了。ABDからスタートすると、AB,AD,BDが子となるが、ADには4が書き込まれているのでAB,BDが残りとなり、この2つに3を書き込む。AB,BDから同様に続ける…となる。

そういうわけで、closed patternの性質を調べてみたい。

contextとその演算

唐突に関係ない数学っぽい話になる。

[定義: context, object, attribute] 集合G,Mとその2項関係I⊂G×Mについて、(G,M,I)のことをcontextとよび、Gのことをobject、Mのことをattributeとよぶ。

例えば、*3 *4Gを男性の集合、Mを女性の集合とし、Iを「カップルになれる男性と女性とのペア全体のなす集合」とすれば、これはcontextになっている。

今回重要な例は、Gをデータのなす集合{ID1,…,ID8}とし、Mを{A,B,C,D}とし、Iを「ID gではmのビットが立っている」で定まる関係としたcontextである。例えば、ID3はAのビットが立っているので(ID3, A)∈Iである。

[定義: derivation] (G,M,I)をcontextとしたとき、A⊂Gのderivationとは{m∈M; 任意のa∈Aについて、(a,m)∈I}となるもののこと。B⊂Mのderivationとは{g∈G; 任意のb∈Bについて、(g, b)∈I}となるもののこと。
A⊂Gのderivation A'はMのsubsetだし、B⊂Mのderivation B'はGのsubsetなことに注意。反対側に行く感じ。

例えば上の男女の例で、A⊂Gを「男子サッカー部員全員」とするなら、A'⊂Gは「男子サッカー部の人なら誰とでもカップルになれる女子全体」となる。「男子サッカー部のカップルになれる人がいる女子全体」ではないことに注意する。

上のハッセ図の例なら、X={A,B}⊂G*5とするならX'は「AもBも1が立っているようなデータ全体」となり、X'={ID1, ID5, ID8}となる。反対に、Y={ID1, ID2}とするならY'は「ID1でもID2でもビットが立っているような要素全体」となり、これはAのみなのでY'={A}となる。

concept

[定義: concept] (G,M,I)をcontextとする。A⊂GとB⊂Mについて、A'=BとB'=Aがなりたつとき、(A,B)をconecptという。

まず定義についてだが、A'=BのA'⊃Bのほうは「任意のb∈Bについて、さらに任意のa∈Aについて(a,b)∈I」となり、A'⊂Bのほうは「任意のa∈Aについて(a, m)∈Iとなるようなどんなm∈Mについても、m∈Bとなる」である。反対側のB'=Aもまとめると、(A,B)がconceptとは

任意のa∈A,b∈Bについて(a,b)∈I
任意のa∈Aについて(a, m)∈Iとなるようなどんなm∈Mについても、m∈Bとなる
任意のb∈Bについて(g, b)∈Iとなるようなどんなg∈Gについても、g∈Aとなる

となる。

例えば上の男女の例なら、({男子サッカー部員全員}, {女子バレー部員全員})がconceptであるとする。上の条件を順に確認するなら

どの男子サッカー部員とどの女子バレー部員もカップルになれる
どの男子サッカー部員ともカップルになれるような女子は全員女子バレー部にいる
どの女子バレー部員ともカップルになれるような男子は全員男子サッカー部にいる

ということになる。(2)を反対向きに読んでみるなら「『こいつとカップルになれ』と言われたら絶対嫌だ、というような男子サッカー部員が一人でもいるような女子は女子バレー部員ではない」ということになる。単に男子サッカー部と女子バレー部はどのペアでもカップルになれて相性が良い(1の意味)というだけではなく、男子サッカー部も女子バレー部もそういう人たちを全員漏れ無く集めたような組織になっているという点ですごく相性が良くぴったりということになる。

上のハッセ図では、({ID1, ID5, ID8}, {A, B, D})はconceptになっている。確認すると

ID1はA,B,D全部が立っており、ID5もID8もそう。
ID1,ID5,ID8全部で立ってるビットを集めるとA,B,Dが全てで、これは{A,B,D}にちゃんと含まれている
A,B,D全部が立っているようなデータを集めるとID1,ID5,ID8が全てで、これは{ID1, ID5, ID8}にちゃんと含まれている

となり、ぴったりである。

性質として、定義からほぼあたり前だが次の一意性を確認する: (A1,B)がconceptで、(A2,B)もconceptなら、A1=A2である。(証明)(A1,B)がconceptなのでA1=B'であり、(A2,B)がconceptなのでA2=B'である。よって、A1=A2。(証明おわり)

ただし、「じゃあderivationとればいつでもconcept作れるじゃん、(B', B)はいつでもconceptじゃん」というのは嘘である。{B}'={ID1, ID5, ID8}だが、ID1,ID5,ID8で立っているビットを全部集めると{A,B,D}となり3番の性質に反する。ぴったりな相方組織が作れないような組織もあるのである。

conceptとclosed patternの関係

直前の例で出た{A,B,D}はたまたまclosed patternになっているが、実はこれは偶然ではない。また「ぴったりな相方組織が作れる」ということがclosed patternと関係している。次の関係がなりたつ:
[性質] (G,M,I)を(有限)ハッセ図のcontextとし、B⊂Mとする。(A,B)がconceptとなるA⊂Gが存在する<==>Bがclosed patternとなる。
(略証)(→)存在するとすれば上の性質からA=B'なので、(B',B)がconceptであるという意味になる。Bがclosed patternでないとしよう。Bより真に大きいビットの集合B2で、B2すべてが立っているようなデータの集合の大きさが|B'|であるものがあることになる。B2のビット全てが立っているようなデータはBのビットも全て立っているのだから、結局B2=B'ということになるが、これはB2がBより真に大きいということに矛盾する。(←)*6Bはclosed patternとする。この頻度はderivationの定義より|B'|である。(B',B)がconceptであることを示そう。片方は自明なので、B''=Bであることを示せばよい。つまり、「Bのビットが全て立っているようなデータ全てで立っているビット全体」がBと等しいことを言えばよい。このカギカッコ内の記述から、B⊂B''は明らかである。仮に等号がなりたたないとすると、B''はBより真に大きいことになる。B'''は「Bのビットが全て立っているようなデータ全てで立っているビット全体が立っているようなデータ全体」なので結局B'で、(B', B'')=(B''',B'')はconceptなのでこの証明の前半よりB''は頻度|B'|のclosed patternである。B''はBより真に大きく、頻度は同じ|B'|なのだから、これはclosed patternの極大性に反する。(証明おわり)

conecptとderivationでclosed patternを作る

concept (A,B)のBについて、B''はBより膨らみ、さらにB''''、B''''''とやってもB''と等しくなることが先の証明をヒントにするとわかり、つまりderivationを2回あてることでBを含む最小のconcept(の片割れ)、即ちclosed patternを計算することができる。これを使えば、下から順にclosed patternを作っていくことができ、closed patternの列挙ができることになる。うれしい。

参考にしたもの

杉山先生の講義:

https://mahito.nii.ac.jp/083d966012dc68108d44de2930dabbe9/Sugiyama_NII_datamining_2019_02.pdf

英語版WikipediaのFormal concept analysis:

Formal concept analysis - Wikipedia

*1:A,B,C,Dは単に名前の意味で使うかもしれないし、変数名の意味で使うかもしれないので適当に文脈で読んでください

*2:本当はデータの総数で割った値なんだけど、この記事で話をするときには特にいらない情報なので単に出現数ということにする。

*3:objectとattributeという名付けからして適当な例ではないのだろうけど数学的には

*4:そして現代的にはpoliticallyにあれなのだろうけれど、二部グラフの話をするときの定番なので…

*5:文字がかぶるのでかえました

*6:なんかいろいろグニャったのでまちがってるかも…そのうち見直しますごめん

2019-06-01

(Z/2^nZ)*の構造(オマケに高校数学風クイズ)

これは何？

金子晃先生の「応用代数講義」の命題4.26の証明がよくわからなかったし、わかったにしても構成が具体的でなくやっぱりよくわからないので、本の証明をヒントに自分でもうちょっと具体的な証明をつけなおしてみた。
最後にこれを考えてたらできた高校数学風クイズもあるよ！

示す命題

n≧3とし、 $G=\mathbb{Z}_{2^n}^*$ とする。 $G\simeq C_{2^{n-2}}\times C_2$ となる。
ここで、 $G=\mathbb{Z}_{2^n}^*$ は $\mathbb{Z}/{2^n}\mathbb{Z}$ の乗法群である。

大事な観察

3の「2の羃」乗を2進法で表記すると、次のような法則が観察される:

$3 = \texttt{11}$ ←末尾の「1」と次の「1」との間に「0」は現れない
$3^{2^1} = 9 = \texttt{1001}$ ←末尾の「1」と次の「1」との間に「0」は2個あらわれる
$3^{2^2} = (3^{2^1})^2 = 81 = \texttt{1010001}$ ←末尾の「1」と次の「1」との間に「0」は3個あらわれる
$3^{2^3} = (3^{2^2})^2 = 6561 = \texttt{1100110100001}$ ←末尾の「1」と次の「1」との間に「0」は4個あらわれる

そういうわけで、i≧1について、 $3^{2^i}$ を2進法で表記したとき、末尾の「1」と次の「1」との間に「1」は $i+1$ 個あらわれるらしい。つまり、「1」が1つずつ左にずれていっているらしい。このことはあとでちゃんと示す。

したがって、 $3, 3^{2^1}, 3^{2^2}, \dots, 3^{2^{n-3}}$ の2進法表記を下n桁(ただしn≧3)とったものを考えるとき、そのとったものたちはすべて相異なる。例えば、

n=3なら、 $3 = \texttt{11}$ の2進法表記での下3桁は「001」で(1個しかないので当たり前だけど)相異なる。
n=4なら、 $3 = \texttt{11}$ の2進法表記での下4桁は「0001」、 $3^{2^1} = \texttt{1001}$ は「1001」でこの2つはやっぱり相異なる。
n=5なら、 $3 = \texttt{11}$ の2進法表記での下5桁は「00001」、 $3^{2^1} = \texttt{1001}$ は「01001」、 $3^{2^2} = \texttt{1010001}$ は「10001」でこの3つはやっぱり相異なる。
…

となる。

証明

まず、Gは $2^n$ 未満の奇数全体からなるので、位数は $2^{n-1}$ である。
「大事な観察」と、位数が2羃でありGの部分群の位数は2羃にならざるを得ない*1ことから3の位数*2はちょうど $2^{n-2}$ である。

ところで、 $2^{n-1}-1$ か $2^{n-1}+1$ との差は2なので、このうち少なくとも一方は3の倍数ではなく、したがって3の羃でもない。その3の羃でないほうをaとよぶことにする。aは(当然 $2^n$ のmodをとって) $a^2=1$ である。
$a\not\in \langle 3 \rangle$ であり、<3>の指数は2なので、G=<3>∪ a・<3>である。

群準同型 $\varphi\colon C_{2^{n-2}}\times C_2 \to G$ を、φ(0, 1)=a, φ(1, 0)=3で定める。これが同型であることを示そう。全射は $\phi(x, y)=3^x \cdot ya$ とG=<3>∪ a・<3>より明らかである。
単射も<3>∩a・<3>=∅に注意すれば簡単である。これで同型が示された。

これでこういうクイズが作れますね

高校数学風に、こういう問題が作れますね(多分うまく誘導作れば本当に高校数学の問題になるんですけど)。

431をn(正の自然数)乗して1024で割った余りを計算すると1になったという。そのようなnのうち最小のものを求めよ。ただし、431は511×81を1024で割った余りである。

答えは上の事実を使えばもちろん簡単で、511は512=1024/2から1を引いたものでかつ3の倍数でないので、上の証明で言うところのaとして選べる。さらに81のほうは3の4乗である。
よって、上の同型で431∈ $\mathbb{Z}_{1024}^*(=G)$ を飛ばすと、(φの逆をψと書くことにして)ψ(431)=(4,1)∈ $C_{256}\times C_2$ となる。
Gの方でn回羃をとることは、 $C_{256}\times C_2$ では両方の要素にn倍することに相当するので、n×(4,1)=(0, 0)となる最小のnを考えればよく、これは明らかに256/4=64である。よって答えは64。

*1:ラグランジュの定理

*2:3の羃の生成する巡回部分群の位数

2019-05-15

Ansible/Vagrantでubuntuを起動してaptするときにdpkgのlockのエラーが出るやつへの対処

Ansible/Vagrantでubuntuを立ち上げて、そこにaptで必要なものをインストールしたい*1ということはあると思うのだが、起動直後だとよく、「dpkgのlockファイルがあって実行できない」というメッセージが出て失敗してしまうことがある。無視すれば当然後ろの命令がうまく行かない。

Googleで「ansible ubuntu dpkg」でぐぐると、結構「dpkgのロックファイルを削除する」とか「killallでdpkgを殺してしまう」というようなどう考えても行儀のいいとは思えない対処法が出てくる。実は私も以前はそれをやっていて、大方はうまくいくのだが沢山やっていると失敗するやつが必ずあらわれて、それらのイレギュラーへの手動の対処が大変で「Infrastrcuture as a codeとは…」という気分になりやってられない。

そもそもこの原因は、Ubuntuがデフォルトだと起動時に自動アップデートをかけるのが原因なので、アップデートが終わるまで待ってからこちらのしたいことをすればいいのである。
そういうわけで、wait_for fails on apt-get / aptitude lock-file in /var/lib/dpkg/lock · Issue #16593 · ansible/ansible · GitHubのようなものも試したのだが、ロックファイルがどうもこれだけとも限らないようで成功率が100%にはならなかった。いまのところ、「そもそもdpkgが起動してるかをみるのが直接的でよくない？」ということで、今はもっぱら

 while ps -A | grep dpkg; do sleep 1; done;

を先頭に挟むことにしていて、今のところは成功率100%である。何かもっと筋の良い方法、常識などあったら教えてください。

*1:例えばvagrant awsでubuntu インスタンスを立ち上げて、そのあとVagrantで操作できるように向こう側でpythonをインストールしたいとか

2018-11-23

Visual Studio 2017でOpenCV 2.4.3をビルドする

諸事情によりOpenCVのバージョン2.4.3を使いたくなったのだが、バイナリの配布が終了していたのでVisual Studio 2017 (Community)ビルドしたくなった。そのときにコケたことがあったので(未だに全ての問題が解決したわけではないが)メモしておく。

OpenCVのgithubのtags(Tags · opencv/opencv · GitHub)から2.4.3を探しzipをダウンロード(https://github.com/opencv/opencv/archive/2.4.3.zip)。
ダウンロードしたファイルを展開。
CMake(https://cmake.org/)のWindows版を起動し、2で展開したディレクトリ(私の場合「C:/Users/ashia/Downloads/opencv-2.4.3」)を「Where is the source code」に、「Where to build the binaries」にそのなかのbuildフォルダを指定する(私の場合「C:/Users/ashia/Downloads/opencv-2.4.3/build」)を指定する。buildディレクトリは存在しないが、あとで確認の上自動で作られるので問題ない。
「Configure」をクリックしてOKとかをポチポチする(多分VS2017を使ってコンパイルする設定にデフォルトでなっていると思うが、なっていなければ直す)。CMakeがそのコンピュータのビルド環境を検出してくれる。
真ん中のおおきい窓にコンパイルオプション赤いリストが表示されるので、必要な機能に応じてつけたりけしたりするはずだが、今回の私の用途ではそのままにしておいた。
「Generate」をクリックする。CMakeがそのコンピュータのビルド環境を見て指定したbuildフォルダに、OpenCVをVS2017を使ってコンパイルするために必要なファイルを揃えてくれる。
buildフォルダのなかにOpenCV.slnができているので、VS2017で開く。
そのまま「ビルド>ソリューションのビルド」を実行するが、maxやminが未定義だと怒られるので、怒られているファイルのヘッダの先頭に「#include 」を付け加える。
もう一度やるとさっきのエラーは消える。正直気持ち悪いのだが、私が今回使う機能には関係ない部分だったので無視していた。これでbuildのbinフォルダには(ビルドが成功した分の機能の)dllファイルができているし、libフォルダにはlibファイルができている。