アルゴリズム忘備録

競技プログラミングとかデータ分析とか

Yukicoder 777 再帰的ケーキ

No.777 再帰的ケーキ - yukicoder

 

たまに目にする2次元LISなやつです。

まずシーケンスa[i]に対して、a[i_1] < a[i_2] < ... < a[i_k] となるような部分列の長さはLIS等の典型アルゴリズムで簡単に求められます。ここで、更に別のシーケンス b[i] も追加してb[i_1] < b[i_2] < ... < b[i_k] となるようにする、というお話です。

 

これは典型手段として下記のようにやるみたいです。

  1. b[i] を座標圧縮し、bx[i] (0<= bx[i] <= n-1) とする。(後にこの要素をインデックスとするRMQを用いるため)
  2. (a[i], bx[i]) という要素の列をa[i] 昇順、bx[i] 降順でソートする(これをすることにより、a[i] = a[i + 1] の場合のめんどくさいコーナーケースがなくなります。実験するとすぐわかります)
  3. 各(a[i], bx[i]) に対して、初期値0の数列dp[i] に対するRMQを用いて、[0, bx[i]) のdpmax を計算し、 d[i] = max(d[i], dpmax + 1) と更新する。
  4. d[i] には最後の要素がbx[i]であるような最大の部分列の長さが入っている

これは要はDP+セグメント木による高速化を行っています。本来の遷移式は下記のとおりです。

dp[i番目まで処理][最後のbx] = max{dp[i-1][j] | j = 0..bx-1} + 1

単純に遷移を書くとO(N^2)ですが、maxはSegmentTreeでやることでO(N log(N))まで計算量が落ちています。

 

Yukicoderの方ではちょっとだけひねってあってあるケーキを追加する場合に1増えるのではなく、c[i]増えるという式になっています。ただ遷移式自体はほぼ変わらず以下のとおりです。

dp[i番目まで処理][最後のbx] = max{dp[i-1][j] | j = 0..bx-1} + c[i]

こうすることにより、答えは max{dp[n][j] | j = 0...n-1} となります。計算量はO(N log(N))。

Solidity on Ethereum Virutual Machine でアルゴリズムを書く

Solidityとはなんぞやという話なんですが、このあたり見てもらえばわかるかなと。つまりは仮想通貨で有名なEthereum上で今の言葉で言うならDAppsを作成するための言語です。

Solidity — Solidity 0.4.24 documentation

 

ちなみにこれ、独自言語ではあるのですが次のような構造をとっています。

  1. Solidity(高級言語)でコード作成
  2. EVM(Ethereum Virtual Machine)バイトコードコンパイルして生成
  3. EVM上でGasを消費しながら起動、リミットに来たら停止

まあ要はVMなわけで、Ethereum上のスマートコントラクトはこのEVMバイトコードで動いているわけですね。一応こういう独自VMの開発はやめて、ブラウザのWeb Assemblyにエコシステムに乗っかるためにLLVM使うなどの変更は検討されているみたいです。

 

さて、EVMバイトコードは単純なプログラムをカウンタ+そのカウンタに応じたGas消費という特徴を持ったチューリングマシン仕様なので、VMの実装も何種類かあります。例えば本物のEthereumで可動しているevmとかいうコマンド(ethereumをapt installすると同時にインストールされるかと思います)はJITを兼ね備えた高級VMです。

一方で、Solidityの主要な開発環境の一つであるRemix-IDEにも簡単なエミュレータが搭載されており、こっちは未確認ですがその動作速度等から単純なバイトコードインタプリタではないかと予想しています。

Remix - Solidity IDE

 

さて、これらの上でアルゴリズムを書くとどのぐらいの性能が要求されるのか少し実験してみました。すると、単純なバブルソートの場合なんとRemix-IDEインタプリタVMだと要素数15程度のソートで固まってしまいました。なんてこったい。要素数15ぐらいだと下手にマージソートとか書いても定数倍で逆に遅くなるんじゃないか・・・という疑念はあるものの一応書いてみましたがそれでもGas消費量は半分ぐらいにはなるようです。

 

というわけでやっぱりネイティブのコードで動くようなアルゴリズムをEVM上で動かすのはやめたほうがいいですね…。一応本家EVM上で動作させると要素数100程度まではまぁ動くのですがGas消費量が半端ありません。正直自分でアルゴを書くよりは組み込み関数でなんとかできるならしたほうが良いと思います。

 

一応知見というかSolidity書くなら次のようなところに注意するとよいようです。

  • memory型で処理し、最後にstorage型に代入する。
  • 組み込みの関数を使えるなら使う。例えば乱数ならXor Shiftを自分で実装するのではなく、未来のHashを使う、など。
  • 再帰は実際の計算量はともかく、Gas消費量としては意外と軽いのではという疑惑(再帰版のマージソートが意外と軽かったため)
  • 基本の整数が256bitとかいう恐ろしいサイズのため心理的にとても遅い感じがする。
  • 関数の修飾子pure view や、変数の修飾子memory storage等が一般的な言語からすると若干戸惑う(でもすぐなれる)
  • バージョンが0.1違うと別言語 ←ココ重要
  • 配列がサイズ指定だったり途中まで可変長だったり若干わかりにくい

正直システムプログラミングっぽいことをするなら十分なのかもしれないですが、アルゴリズムをゴリゴリ書くにはちょっとあれですね…WASM版でなんとかなるとよいのですが。

DISCOコンテスト2019 予選 D - チップ・ストーリー ~黄金編~

beta.atcoder.jp

 

あるNに対して、Nをb進数で表した時の桁の和をa[b]とおく。a[2]~a[30]までが与えられるので、Nとしてあり得る数として10^12以下のものを求める問題です。

 

受験数学とかでNが9の倍数かどうかの判定として各桁の和で判定できる、という知識は有名かと思います。一般にNをb進数で表したとき、N = a[b] mod b-1 となります。これは実際にb^nで展開して両者引いて見るとすぐに分かります。

 

そのため、中国剰余定理を使ってすべてのbに対して N= a[b] mod b-1 の条件を満たす数を1個生成すると(これをXとおきます)、条件を満たす数はある数Yが存在してX + Y*LCM(2, 3, ..., 30) となります。

 

LCM(2,3,...,30)=2329089562800<10^12 であるため、10^12以下のものを1個見つけたらそれしか答えの候補はありません。見つけたらその数についてa[2]~a[30]の条件を満たすか確認し、OKなら出力します。計算量は無視できるサイズです。

 

中国剰余定理を知ってるかどうかで参加者の出来が別れたみたいです。

スライド最小値

蟻本を見ているとあまり知らないアルゴリズムが結構あったりするので、ちゃんと読み返しています。というわけでスライド最小値のメモ。

 

長さNの数列 a[i] に対して、長さkの連続部分列 {a[i], a[i + 1],... , a[i + k - 1]} の最小値を b[i] とします。この b[i] を 0 <= i <= n-k を満たすすべての i についてO(N)で計算できるテクがあります。

 

通常区間最小を高速に求めるにはSegment Tree等を使ってO(Nlog(N)) になります。ただ、Segment Treeは定数倍が遅いので高度な計算が必要ない場合は次のスライド最小値を使うほうが早いです。

 

まずDeque(Qとする)を用意します。このQに対し、a[i]を次のようにpushします。

1. Q の末尾からみていって、a[Qの末尾の要素] < a[i] となるまで Q の末尾をpopする

2. Qにi (値のa[i]ではなく、インデックスのi) をpush する

3. Qの先頭の要素 == i - k ならば先頭の要素を削除する

 

このQの要素をQ[i] とおくと、直感的に言えば、a[i]の長さKの連続部分列の中の単調増加(連続とは限らない)部分列のインデックスが入っている感じです。正確には次のようなQueueになっています

 

1. Q[0] < Q[1] < ... < Q[Qの最後]

2. a[Q[0]] < a[Q[1]] < ... < a[Q[Qの最後]]

3. Qの長さはK以下

 

そのため、今見ている区間でのb[i]はQ[0]で取得できます。Qの削除は追加した数N以上には発生しないため、計算量はO(N)となります。

円周率チャレンジ

円周率チャレンジ

 

平方根を取る or 2を足すを繰り返してπ=3.1415...に近い値を生成してくださいというゲームです。上位はスコアinfがでていますが、これはdouble型の最大値を超えてしまったためのようです。

 

戦略としてはTwitterでも一部言われていますが半分全列挙という手法を使うのが良いのかなと思います。最短手数がランキングからわかっているのでそれをnとおくと、x=0 から始めて2を足す or 平方根を取る という操作をn/2回繰り返した状態を生成します。次にx=πから始めて2を引く or 二乗する という逆操作をn/2繰り返した状態を生成します。そして、両者をつなげて最適解を探索します。ただし、両者の状態はdouble型のため実際には完全には一致しません。そのため、二分探索やしゃくとりなどの方法により最も近いところかその次辺りまでを試して最適なものを発見します。

 

計算量はO(2^(n/2))であり、n=53 ということがわかっているので、空間計算量、処理計算量ともにO(1億)といったところです。競技プログラミングの一般的な制限2秒 1024MB では計算は難しいですが、制限時間等があるわけではないので効率的なコードがかければ無理ではない範囲かと思います。

 

※ネタバレはどうかなとは思うのですが、ネット上ではすでにこのぐらいのネタが書いてある かつ コードを載せているわけではないのでまぁいいかなと。

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

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

 

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

 

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

 

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

crypto.watch.impress.co.jp

 

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

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

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

 

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

 

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

 

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

 

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

 

 

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

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

 

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

 

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

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

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