2018-11-07

「ブロックチェーンという言葉に騙されないために」を読もう。

最近会社のSNSに競プロ関係の記事は書いていたので更新は止まっていたのですが、こっちも再開しようかなと。というわけでいもす研の「ブロックチェーンという言葉にだまされないために」の紹介です。

https://imoz.jp/note/blockchain.html 「ブロックチェーンという言葉にだまされないために」

2016年に書かれた内容ですが、今のブロックチェーン界隈の人はまず一読すべきものだと考えています。(余談ですがこの著者は競プロで有名な人だったりします)

この記事を書こうと思ったのはFacebookに貼ってあった次のネタを見たためです。

crypto.watch.impress.co.jp

上のネタは今の日本企業におけるブロックチェーンの適用に関わる問題の典型例といってもよいものです。(海外企業でも同様のことがあるかもしれませんが、よく調べてはいません。) ブロックチェーンでなにかビジネスを考えるときに、そもそもブロックチェーンで何を解決するのか、と問うと以下の2点が挙げられることが多いです。

トレーサビリティ
改ざん防止

例えばImpress Watchの記事でいうと「オープンバッジに盛り込むデータが改ざんされては困るので、そうした視点でブロックチェーンの利用が見込める」という発言に現れています。

しかし、いもす研の記事でも触れられていますが、そもそもブロックチェーンで改ざんが困難になるというのはブロックチェーンの主要な特徴ではなくどちらかというと電子署名によるものです。また、トレーサビリティについてもそれが主要な目的ではありません。ブロックチェーン、特にパブリックブロックチェーンが解決する技術的課題は「信頼できないノード間での合意形成」になります。これが必要でないシチュエーションに無理にブロックチェーンを適用しようとしても結局分散DB等の既存技術のほうがよっぽどマシなのですが、そのあたりの認識が薄く上っ面の特徴だけが独り歩きしている印象があります。

また、プライベートブロックチェーンについてはそもそも「信頼できないノード間」というのは有名無実化されており、いもす研の引用をしますが、プライベートブロックチェーンとして有名なHyperledgerなどでは「中央管理者がいないことを定義にしているのにもかかわらず、結局実用には中央管理者のいる構造が必要であるとしている点に問題があります。」という状況です。

というわけでブロックチェーンについてはインセンティブモデルや合意形成などのいろいろな概念を理解した上で適切な利用法を決めることが重要なのですが、そういう基礎概念を無視して上っ面の特徴だけでビジネス適用する例がかなり多いので気をつけたいところです。

ブロックチェーン関係のまとも、かつお手軽に読める記事は実はあまりなく、お手軽なところは上っ面の特徴を列挙してるだけだったり、ちゃんと書いてるところはしっかり書きすぎて一読するには辛いものが多かったりするのですが、いもす研の記事はかなり良く出来てるので必読かと思いました。

2017-10-21

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

code-festival-2017-qualb.contest.atcoder.jp

グラフが与えられる。辺をちょうど3回通ってたどり着ける2点間に新たに辺を引く、という操作をできるだけしたい。ただし、既に辺がある場合は引くことができない。最大で何回操作ができるか？

グラフが二部グラフでないとき、頂点間の経路は操作を繰り返していくことで、すべての2点間で3回通って辿り着ける。そのため、完全グラフの辺の数から既に引かれている辺の数を引けばよい。

グラフが二部グラフの場合、最大で完全二部グラフにしかならない(偶奇を考えればよい)。そのため、完全二部グラフの辺の数から現在引かれている辺の数を引けば良い。

計算量は二部グラフの判定が支配項でO(N)。

2017-10-05

CS Academy Round 51 - Tree Coloring

csacademy.com

ツリーと色数kが与えられる。この時、あるノードに対して、そのノードから距離1のノードと、距離2のノード両方と色が異なるように頂点を彩色したい。彩色の仕方は何通りあるか。

あるノードに着目する時、距離1または距離2のノードがすべて異なるということなので、そのノードの隣接ノードの集合を考える。するとその隣接ノード＋今見ているノードの集合について、これらは全て距離2以下であるため、その集合の数をmと置くと彩色数は k * (k - 1) * .. * (k - m + 1) となる。ここから次の隣接ノードに移る。すると、同じように考えられるが、既にカウント済みのノードがあるため、そのカウント済みのノードをlとおくと、それらのノードの色は既にカウント済みであり、かつ全て色が異なる。したがって今見ている集合の彩色数は (k - l) * (k - l - 1) * .. * (k - m + 1) となる。

これらをdfsで辿っていき、子ノードの彩色数の積に今見ているノードの彩色数の積、という値を返してどんどん根まで計算すると答え。O(N)。

2017-10-05

CS Academy Round 51 - Manhattan Distances

csacademy.com

整数d1, d2, d3が与えられる。2次元格子点座標の3点であって、各点のマンハッタン距離がd1, d2, d3のいずれかになるような3点を構成せよ。できない場合は-1を出力せよ。

マンハッタン距離は距離と名付けてあるだけあって、距離公理を満たす。その為、三角不等式の成立条件が構成できる第一条件である。次に格子点座標にある場合、それらのマンハッタン距離はその三点を囲う最小の長方形の周囲の長さに等しくなる。(図を書いてみるとすぐわかる。そのため、d1＋d2＋d3が偶数であることも必要であり、かつ十分である。

そこで、単純な例として、長方形の一片が構成する3点のうちの2点でかつd1～d3の中で最大のもの(例えばd1とする)であり、その片方が原点であるようなものを考える。すると(0, 0), (0, d1) と座標が決まる。すると、残りの1点は((d2 + d3 - d1) / 2, (d2 + d1 - d3) / 2)などとなる。O(1)。