2018-12-24

CADDi 2018 for Beginners に参加しました

こんにちは、ぺたこ(@peta727)です

タイトル通り、「CADDi 2018 for Beginners 」に参加しました。とりあえず、結果は以下のように悲惨な感じです

atcoder.jp

ただ、C問題に関しては大枠の考え方としてはあっており、うまく実装できなかったことが悔しいです。

🤔https://t.co/4Juya8NJqf
— 呪文づまりのぺたこ (@peta727) 2018年12月22日

本日、再度解き直して TLE にならないコードが書けました。

とりあえず、緑コーダーを目指して頑張っていこうと思います。

以下に、TLEを回避できた素因数分解のPHPのコードを載せておきます。

function getPrimeFactors($N) {
    $result = [];

    for($i = 2; $i * $i <= $N; $i++) {
        if ($N % $i == 0) {
            while($N % $i == 0) {
                $result[$i]++;
                $N /= $i;
            }
        }
    }
    if ($N > 1) {
        $result[$N]++;
        $N /= $N;
    }
    return $result;
}

2018-10-26

macOS Mojaveにしてvagrantが動かなくなったときにした対応

こんにちは、ぺたこ(@peta727)です

9月後半にリリースされた macOS Mojave ですが、そろそろ1ヶ月立ちますのでMacBook Proをアップデートしました

アップデートが終わったあと、一部の開発で利用している vagrant が動かなくなっていたので対応しました

対応したこと

Oracle VM VirtualBox を5.2にアップデート
Vagrant を 2.2.0 にアップデート

具体的な手順

VirtualBox のアップデート

Oracle VM VirtualBox より VirtualBox(5.2) をダウンロード

dmgファイルよりインストール

vagrant up を実行

❯ vagrant up
==>  Provider 'virtualbox' not found. We'll automatically install it now...
     The installation process will start below. Human interaction may be
     required at some points. If you're uncomfortable with automatically
     installing this provider, you can safely Ctrl-C this process and install
     it manually.
==>  Downloading VirtualBox 5.0.10...
     This may not be the latest version of VirtualBox, but it is a version
     that is known to work well. Over time, we'll update the version that
     is installed.
The download was interrupted by an external signal. It did not
complete.

どうやら、インストールしたVirtualBoxを認識していないみたいです

原因を調べるために、 vagrant status を実行してみます

❯ vagrant status
The provider 'virtualbox' that was requested to back the machine
'default' is reporting that it isn't usable on this system. The
reason is shown below:

Vagrant has detected that you have a version of VirtualBox installed
that is not supported by this version of Vagrant. Please install one of
the supported versions listed below to use Vagrant:

4.0, 4.1, 4.2, 4.3, 5.0

A Vagrant update may also be available that adds support for the version
you specified. Please check www.vagrantup.com/downloads.html to download
the latest version.

Vagrantが古いため、VirtualBoxのバージョン5.0以下にしか対応していないようです

Vagrantのアップデート

www.vagrantup.com より Vagrant(2.2.0) をダウンロード

dmgファイルよりインストール

vagrant up を実行

❯ vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Clearing any previously set forwarded ports...
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
    default: Adapter 2: hostonly
==> default: Forwarding ports...
    default: 22 (guest) => 2222 (host) (adapter 1)
==> default: Running 'pre-boot' VM customizations...
...

無事起動できました

2017-06-14

一方向ハッシュ関数についてまとめ

ハッシュ関数とは

ハッシュ関数とは、ある入力に対してそのデータを代表するデータを出力する関数のことである。

ハッシュ関数の安全性

ハッシュ関数には、以下の3つの安全性要件がある。

原像計算困難性
衝突計算困難性
第二原像計算困難性

原像計算困難性

原像計算困難性とは、与えられたハッシュ値からそのハッシュ値を出力する入力を求めることが困難である性質を言う。

衝突計算困難性

消灯計算困難性とは、同じハッシュ値を出力する入力を求めることが困難であることを言う。

第二原像計算困難性

第二原像計算困難性とは、与えられた入力と同じハッシュ値を出力する別の入力を求めることが困難であることを言う。

一方向ハッシュ関数

ハッシュ関数のうち、原像計算困難性を満たすものを一方向ハッシュ関数という。

具体的には、一方向性関数をfとするとき xからf(x) を多項式時間で求められ f(x)からx を多項式時間で求められないことである。

一方向ハッシュ関数に用いられるアルゴリズムの種類

MD5

Message Digest Algorythm 5のことで、出力128bitのハッシュアルゴリズムとなっている。現在は、安全でないアルゴリズムで使用は推奨されていない。

SHA-1

Secure Hash Algorithmの一種で、SHA-1には脆弱性が存在しているため使用にすることは推奨されていない。

SHA-2

Secure Hash Algorithmの一種で、SHA-1に脆弱性が発見されたため現在はこちらを使用することが推奨されている。SHA-2は鍵長により以下のような種類がある。

SHA-224
SHA-256
SHA-384
SHA-512

ソルト

一方向性ハッシュ関数では、同じ文字列の入力に対して同じハッシュ値を出力する。しかし、ユーザ名などが同じ複数のユーザのパスワードを保存したい場合がある。この時使用するのが「ソルト」で、ハッシュ化を行う前に対象文字列にランダムな文字列を追加する。こうすることによって、同一文字列のハッシュ化時の衝突を防ぐことができる。

2017-06-12

ElasticsearchでMySQLのLIKE検索ぽいものを実現

はじめに

Elasticsearchを使って全文検索システムを作る機会がありました。そのとき、MySQLの %HOGE% と同様の検索をすることが必要な場面がありハマってました。色々試行錯誤して実現した結果を、自分と同じようなことを行いたい人がいるかもしれないのでメモとして残しておきます。 Elasticsearch & 検索システム初心者なので間違ったことなどあったら、教えてほしいです。

環境

Amazon Elasticsearch Service (ver 2.3)

注意

Amazon Elasticsearch Service と Elastic社のElasticsearch は別物です。
あくまでLIKE検索もどきである完全に同じ検索が行えるわけではありません。
困ったときはElastic社のリファレンスを見てください。リファレンス

検索の仕方

N-gram analyzer と match_phrase を用いて検索します。

{
    " query" : {
        "match_phrase" : {"field_name" : "keyword" }
    }
}

N-gramのfiledを作る方法は、他の記事などで詳しく解説されているので省きます。このように、 N-gram と match_phrase を組み合わせるとLIKE検索もどきが実現できます。