ABC #013 C – 節制

問題の概要

---

abc013.contest.atcoder.jp

　日の間、初期値 の満腹度を以下にさせないために、以下のような食事のいずれかを選ぶ。

内容	食費	満腹度の変動
普通の食事
質素な食事
食事抜き

　以上の条件を満たす必要最低限の食費はいくらかを求める。 また、満腹度には上限がない上、の値の範囲で以下のように部分点が設定されている。

範囲
点数	10	40	100	101

問題の考察

---

　普通の食事の日数を日、質素な食事の日数を日とする。

　この時、満腹度には上限がないため、最初の日に全ての食事を済ますと考える。 この方法では、満腹度が途中でになる状態を考えずに、食費の最小値を求めることができる。

食事の計画

解答例

---

[100点解法] に対する全探索

　各 に対して、以下の不等式が成り立つかどうかを確認する。

　しかし、この解放ではであるため、のテストケースでは時間が足りない。

[満点解法] のみの全探索

　式 (1) を以下のように式変形するとのみの探索で済むため、 で求めれる。

　また、の値が大きいとき、の値が負の値をとることがあるため、注意が必要となる。

[満点解法] 尺取り法を用いた解法

　この解法では、式 (1) をそのまま用いる。 の探索を、以下のように尺取り法を用いることで、で探索することを可能とした。

1. 最初に、普通の食事だけで乗り切る場合の最低回数を求める。これをとする。
2. 式(1)を満たさなくなるまで、を減少させる。
3. 式(1)を満たすまで、質素な食事の回数を増加させる。
4. 操作2, 3ができなくなるまで繰り返す。

　以上のソースコードは以下のGithub上にて参照可能です。 github.com

その他の解説サイト

• AtCoder Beginner Contest 013 解説 - AtCoder公式解説
• ABC013C 節制 - ry0u_ydのblog

deviseによるFacebook / Twitter 認証 -Rails奮闘記②-

本記事の紹介

---

　本記事は、私がRuby on Rail（Rails, RoR）を用いたWebアプリケーションを作る過程を示したものです。 Railsの勉強も兼ねているため、間違いなどもあった場合はご指摘いただけると大変嬉しいです！

• OS: Mac OS 10.12.6
• Ruby: 2.5.0
• Ruby on Rails: 5.1.4

　Devise を用いた基本的なユーザ認証の作成までは、過去記事を参照。

farma-11.hatenablog.com

deviseによるOAuth 認証

---

Dotenvによる環境変数の管理

　Gem: Dotenvを導入することでGitのリポジトリには含めずに外部APIの情報を環境変数として扱う。

1. Dotenvをインストール

# Gemfile
gem 'dotenv-rails', require: 'dotenv/rails-now'

$ bundle install --path vendor/bundle

2. .envファイルを作成

# .env
FB_APP_ID="[FacebookのアプリID]"
FB_APP_SECRET="[Facebookのapp secret]"
TW_APP_KEY="[TwitterのAPI key]"
TW_APP_SECRET="[TwitterのAPI secret]"

3. コンソールを起動して、呼び出せるか確認

$ bundle exec rails c
Running via Spring preloader in process 11075
Loading development environment (Rails 5.1.4)
irb(main):001:0> Dotenv.load
=> {"FB_APP_ID"=>"[FacebookのアプリID]", "FB_APP_SECRET"=>"[Facebookのapp secret]", "TW_APP_KEY"=>"[TwitterのAPI key]", "TW_APP_SECRET"=>"[TwitterのAPI secret]"}
irb(main):002:0> quit

4. .gitignoreに.envを追加

/.env

Facebook / Twitter 認証の実装

5. Gemfileの編集

# Gemfile
gem 'omniauth-facebook'
gem 'omniauth-twitter'

6. インストール

$ bundle install --path vendor/bundle

7. OAuthで取得するproviderとuidを保持するために、Userモデルにカラムを追加

$ rails g migration add_columns_to_users provider uid
$ rake db:migrate

8. Deviseにて取得したプロバイダの各キーを設定
　Dotenvにて管理されている各キーをENV['HOSTNAME']のように利用できる。

# config/initializers/devise.rb
# （省略）
  # ==> OmniAuth
  # Add a new OmniAuth provider. Check the wiki for more information on setting
  # up on your models and hooks.
  # config.omniauth :github, 'APP_ID', 'APP_SECRET', scope: 'user,public_repo'
  config.omniauth :facebook, ENV['FB_APP_ID'], ENV['FB_APP_SECRET']
  config.omniauth :twitter, ENV['TW_APP_KEY'], ENV['TW_APP_SECRET']
# （省略）

9. Userモデルにモジュールを追加

# app/models/user.rb
class User < ApplicationRecord
  # Include default devise modules. Others available are:
  # :confirmable, :lockable, :timeoutable and :omniauthable
  devise :database_authenticatable, :registerable,
         :recoverable, :rememberable, :trackable, :validatable, :omniauthable
  # （省略）
}

10. Userモデルにfindメソッドを実装

# app/models/user.rb
class User < ApplicationRecord
  # （省略）
  def self.find_for_oauth(auth)
    user = User.where(uid: auth.uid, provider: auth.provider).first

    unless user
      user = User.create(
        uid:      auth.uid,
        provider: auth.provider,
        email:    User.dummy_email(auth),
        password: Devise.friendly_token[0, 20]
      )
    end

    user
  end

  private

  def self.dummy_email(auth)
    "#{auth.uid}-#{auth.provider}@example.com"
  end
end

11. ディレクトリを作成

$ mkdir app/controllers/users

12. Userコントローラにコールバック処理を実装

# app/controllers/users/omniauth_callbacks_controller.rb
class Users::OmniauthCallbacksController < Devise::OmniauthCallbacksController
  def facebook
    callback_from :facebook
  end

  def twitter
    callback_from :twitter
  end

  private

  def callback_from(provider)
    provider = provider.to_s

    @user = User.find_for_oauth(request.env['omniauth.auth'])

    if @user.persisted?
      flash[:notice] = I18n.t('devise.omniauth_callbacks.success', kind: provider.capitalize)
      sign_in_and_redirect @user, event: :authentication
    else
      session["devise.#{provider}_data"] = request.env['omniauth.auth']
      redirect_to new_user_registration_url
    end
  end
end

13. ルーティング処理

# config/routes.rb
Rails.application.routes.draw do
  devise_for :users, controllers: { omniauth_callbacks: 'users/omniauth_callbacks' }

  # （省略）
end

まとめ

---

　本記事は、以下の記事を参考にまとめました。

• RailsにDotenvを導入！環境変数を管理しよう！ #rubybg
• Devise+OmniAuthでユーザ認証を実装する - qiita(@kami_zh)

deviseを用いたユーザ認証作成 -Rails奮闘記①-

本記事の概要

---

　本記事は、私がRuby on Rail（Rails, RoR）を用いたWebアプリケーションを作る過程を示したものです。 Railsの勉強も兼ねているため、間違いなどもあった場合はご指摘いただけると大変嬉しいです！

• OS: Mac OS 10.12.6
• Ruby: 2.5.0
• Ruby on Rails: 5.1.4

Devise を用いた基本的なユーザ認証の作成まで

---

Railsプロジェクトを作成する

1. Githubの準備

$ git clone https://github.com/[Githubのユーザ名]/[プロジェクト名].git
$ cd [プロジェクト名]

2. Gemfileという雛形ファイルが作成

$ bundle init

3. Gemfileに書き込む

gem "rails","5.1.4"

4. ルートディレクトリ下のvendor/bundleディレクトリにインストール

$ bundle install --path vendor/bundle

5. Rails プロジェクトを作成する

$ bundle exec rails new .

deviseの初期設定

6. deviseをインストール

# Gemfile
gem 'devise'

$ bundle install --path vendor/bundle

7. deviseの設定ファイルを生成
　config/initializers/devise.rb と config/locales/devise.en.yml ができる

$ rails g devise:install
$ bundle exec rails g devise:install
Running via Spring preloader in process 84346
      create  config/initializers/devise.rb
      create  config/locales/devise.en.yml
===============================================================================

Some setup you must do manually if you haven't yet:

  1. Ensure you have defined default url options in your environments files. Here
     is an example of default_url_options appropriate for a development environment
     in config/environments/development.rb:

       config.action_mailer.default_url_options = { host: 'localhost', port: 3000 }

     In production, :host should be set to the actual host of your application.

  2. Ensure you have defined root_url to *something* in your config/routes.rb.
     For example:

       root to: "home#index"

  3. Ensure you have flash messages in app/views/layouts/application.html.erb.
     For example:

       <p class="notice"><%= notice %></p>
       <p class="alert"><%= alert %></p>

  4. You can copy Devise views (for customization) to your app by running:

       rails g devise:views

===============================================================================

8. deviseのメール送信時のホスト名を指定

# config/environments/development.rb
Rails.application.configure do
  ...
  # mailer setting
  config.action_mailer.default_url_options = { host: 'localhost', port: 3000 }
end

9. 実際のControllerやViewを作成 　ここでは、Homeコントローラーと、indexページとshowページを追加した。

$ rails g controller Home index show

10. ログアウト時などのリダイレクト先として、root_urlの指定する

# config/routes.rb
Rails.application.routes.draw do
  root to: "home#index"
end

11. エラーメッセージ（flashメッセージ）の表示領域の設定

<!-- app/views/layouts/application.html.erb -->
<!DOCTYPE html>
<html> 
  <!--（省略）-->
 <body>
  <p class="notice"><%= notice %></p>
  <p class="alert"><%= alert %></p>

  <%= yield %>

 </body> 
</html>

12. deviseのモデルを作成

$ rails g devise User
      invoke  active_record
      create    db/migrate/[yyyymmddhhmmss]_devise_create_users.rb
      create    app/models/user.rb
      invoke    test_unit
      create      test/models/user_test.rb
      create      test/fixtures/users.yml
      insert    app/models/user.rb
       route  devise_for :users

13. マイグレートを実施 　マイグレーションとは、SQLを書くことなくRubyでデータベース内にテーブルを作成すること。

$ rake db:migrate

14. Homeのshow画面へのアクセス制限を追加
　ステップ13までは、ログインしていない状態でshow画面 | http://localhost:3000/home/showにアクセス可能となってしまっている。

# app/controllers/home_controller.rb
class HomeController < ApplicationController
  # ユーザがログインしていないと"show"にアクセスできない
  before_action :authenticate_user!, only: :show

  def index
  end
  # （省略）
end

usernameで認証できるようにする

15. テーブルにusernameを追加

$ rails g migration add_username_to_users username:string

16. indexの追加と一意制約を追加

# db/migrate/[yyyymmddhhmmss]_add_username_to_users.rb
class AddUsernameToUsers < ActiveRecord::Migration[5.1]
  def change
    add_column :users, :username, :string
    add_index :users, :username, unique: true
  end
end

17. マイグレートを実施

$ rake db:migrate

18. 認証キーをusernameへ

# config/initializers/devise.rb

# （省略）
# ==> Configuration for any authentication mechanism
  # Configure which keys are used when authenticating a user. The default is
  # just :email. You can configure it to use [:username, :subdomain], so for
  # authenticating a user, both parameters are required. Remember that those
  # parameters are used only when authenticating and not when retrieving from
  # session. If you need permissions, you should implement that in a before filter.
  # You can also supply a hash where the value is a boolean determining whether
  # or not authentication should be aborted when the value is not present.
  # config.authentication_keys = [:email]
  config.authentication_keys = [:username]
# （省略）

19. UserモデルにValidateを追加
　usernameには、以下のバリデーションを追加した。

• usernameが大文字小文字の区別をせずにuniqueであること
• 文字数が4 - 20文字であること
• usernameは半角英数字であること

# app/models/user.rb
class User < ApplicationRecord
  # Include default devise modules. Others available are:
  # :confirmable, :lockable, :timeoutable and :omniauthable
  devise :database_authenticatable, :registerable,
         :recoverable, :rememberable, :trackable, :validatable

  # usernameのバリデーション
  validates :username,
    uniqueness: { case_sensitive: :false },
    length: { minimum: 4, maximum: 20 },
    format: { with: /\A[a-z0-9]+\z/, message: "ユーザー名は半角英数字です"}
end

20. ログイン画面のemailをusernameの入力フィールドに変更

<!-- app/views/devise/sessions/new.html.erb -->
<h2>Log in</h2>

<%= form_for(resource, as: resource_name, url: session_path(resource_name)) do |f| %>
  <div class="field">
    <%= f.label :username %><br />
    <%= f.text_field :username, autofocus: true %>
  </div>

  <!--（省略）-->
<% end %>

<%= render "devise/shared/links" %>

21. サインアップ画面もusernameの入力フィールドに対応

<!-- app/views/devise/registrations/new.html.erb -->
<h2>Sign up</h2>

<%= form_for(resource, as: resource_name, url: registration_path(resource_name)) do |f| %>
  <%= devise_error_messages! %>

  <div>
    <%= f.label :username %><br />
    <%= f.text_field :username, autofocus: true %>
  </div>

  <!--（省略）-->
<% end %>

<%= render "devise/shared/links" %>

22. プロフィール変更画面もusernameの入力フィールドに対応

<!-- app/views/devise/registrations/edit.html.erb -->
<h2>Edit <%= resource_name.to_s.humanize %></h2>

<%= form_for(resource, as: resource_name, url: registration_path(resource_name), html: { method: :put }) do |f| %>
  <%= devise_error_messages! %>

  <div>
    <%= f.label :username %><br />
    <%= f.text_field :username, autofocus: true %>
  </div>

  <!--（省略）-->
<% end %>

23. app/controllers/application_controller.rbの追記 Publifyでユーザー登録するとCan't be blankエラーの対応

# app/controllers/application_controller.rb
class ApplicationController < ActionController::Base
  # Prevent CSRF attacks by raising an exception.
  # For APIs, you may want to use :null_session instead.
  protect_from_forgery with: :exception

  # deviceのコントローラーのときに、下記のメソッドを呼ぶ
  before_action :configure_permitted_parameters, if: :devise_controller?

  protected

  def configure_permitted_parameters
    added_attrs = [:username, :email, :password, :password_confirmation, :remember_me]
    devise_parameter_sanitizer.permit :sign_up, keys: added_attrs
    devise_parameter_sanitizer.permit :account_update, keys: added_attrs
  end
end

まとめ

---

　本記事は、以下の記事を参考にまとめました。

• Railsのログイン認証gemのDeviseのインストール方法 - Rails Webook
• Railsのログイン認証gemのDeviseのカスタマイズ方法 - Rails Webook
• [Rails] deviseの使い方（rails5版）
• Railsのgem「devise」を用いてユーザーログイン機能を実装
• Publifyでユーザー登録するとCan't be blankエラーの対応

UVa #11995 I Can Guess the Data Structure!

問題の概要

---

問題文: UVa Online Judge #11995 - I Can Guess the Data Structure!

　個の命令文が入力として与えられる。 以下のデータ構造のうち、どのデータ構造に大した命令文であったか出力するもの。

• Stack
• Queue
• Priority queue

　また、一つに限定できない場合はnot sure、どのデータ構造でもない場合はimpossibleを出力する。

解答例

---

　単にC++にあるstack、queue、priority queueにコマンドと同じ操作をさせて同じ挙動を取るかどうかで判断するだけで良い。 しかし、データが挿入されていない状態で、データを参照・削除をする場合の処理を忘れないように気をつける。

　以上のソースコードは以下のGithub上にて参照可能です。 github.com

データ構造について

---

スタック（Stack）

概要

　スタックが可能な操作は以下の通りである。

• Push: 新たなデータを追加する操作
• Pop: 最も最近に追加されたデータを取り出す操作

C++ におけるstd::stackの使い方

　C++ では、Pushはpush()にて、Popはtop() / pop()にて実現できる。

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> st;
    
    for(int i = 0; i < 10; i++){
        st.push(i);  //スタック st に i を追加する
    }
    
    while(!st.empty()){
        cout << st.top() << " ";  // stの末尾要素を参照（出力）
        st.pop();  // stの末尾要素を削除
    }
}

　入力が0, 1, 2, 3, 4, 5, 6, 7, 8, 9の順に対して、出力は9 8 7 6 5 4 3 2 1 0となる。

キュー（Queue）

概要

　キューが可能な操作は以下の通りである。

• Enqueue: 新たなデータを追加する操作
• Dequeue: 最初に追加されたデータを取り出す操作

C++ におけるstd::queueの使い方

　C++ では、Enqueueはpush()にて、Dequeueはfront() / pop()にて実現できる。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    
    for(int i = 0; i < 10; i++){
        q.push(i); //キュー q に i を追加する
    }
    
    while(!q.empty()){
        cout << q.front() << " ";  // qの先頭要素を参照（出力）
        q.pop(); // qの先頭要素を削除
    }
}

　入力が0, 1, 2, 3, 4, 5, 6, 7, 8, 9の順に対して、出力は0 1 2 3 4 5 6 7 8 9となる。

優先度付きキュー（Priority queue; 順位キュー）

概要

　優先度付きキューが可能な操作は以下の通りである。

• 新たなデータを追加する操作
• 優先度が高いデータ（昇順 / 降順）を取り出す操作

C++ におけるstd::priority_queueの使い方

　C++ では、データの挿入はpush()にて、データの参照 / 削除はtop() / pop()にて実現できる。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    int inputs[10] = {0, 5, 4, 9, 2, 1, 3, 7, 8, 6};
    
    for(int i = 0; i < 10; i++){
        pq.push(inputs[i]);
    }
    
    while(!pq.empty()){
        cout << pq.top() << " "; // pqの優先度の一番高い要素を参照（出力）
        pq.pop(); // pqの優先度の一番高い要素を削除
    }
}

　入力が0, 5, 4, 9, 2, 1, 3, 7, 8, 6の順に対して、出力は9 8 7 6 5 4 3 2 1 0となる。

IJCAI2016: "Identifying Key Observers to Find Popular Information in Advance"

本記事・論文について

---

　本記事では以下の論文の概略を示しつつ、論文読解のための知識をまとめる。

論文: Konishi, Takuya, et al. "Identifying Key Observers to Find Popular Information in Advance." IJCAI. 2016.

※ IJCAI（International Joint Conference on Artificial Intelligence; 国際人工知能会議）: 人工知能学会分野でトップの学術会議

論文の内容

---

論文の概要

　本論文の目的は、観測者を経由して将来流行しそうなアイテムを前もって検出をすることである。 観測者（Observers）とは、流行する前から将来人気が出るアイテムを見つけられるユーザである。 観測者をお気に入りリストに入れることで、ユーザは流行するアイテムを見つけることができる。

　アプローチは以下のようになる。

1. アイテムが流行するかどうかを判別する分類器を、他の人より先にアイテムを採用したユーザ集合を入力として設計する。
2. 機械学習による特徴量選択を行うことで効率的な観測者を特定する。

流行するアイテムの早期検出の有効性

　消費者の購買行動について分類を行なっているイノベータ理論*1 がある。その中で、流行には敏感で自ら情報収集し判断を行う購買行動をとる Early Adaptors は、オピニオンリーダーとして他の消費者層に大きな影響を及ぼすとされる。

　流行するアイテムの早期検出に対して、以下のような利点の例がある。

• 企業のマーケティング戦略を効果的にできる*2。
• 他の研究チームより先に将来流行する研究分野を特定できる。
• おいしいレストランを有名になる前に知ることができる。

　理論的には Early Adopters の存在は証明されているが、対象となる分野によって異なり、特定することは困難とされる。

観測者を経由した流行アイテムの早期検知

　本論文では、流行アイテムのEarly Adoptersを観測者（Observers）としている。 観測者を経由することで、

• ユーザ推薦への応用に対して簡単にカスタマイズすることが可能
• エキスパートの行動から知識を獲得できる

観測者の選択の例（本論文から引用）

　一方で、 以下のような課題がある。

• 膨大なユーザの中から観測者として適切なユーザを選び出すことは困難
• 既存研究 *3では、ユーザ間のネットワークが仮定されているため、電子商取引などのサービスに適用できない

　本論文では、機械学習を用いた特徴量選択を行うことで効率的に観測者を特定することを試みている。 ユーザが選んだアイテムとタイムスタンプといったイベントデータのみの利用で、観測者の予測が可能になる。

　具体的な提案手法や評価実験等は、本論文や解説スライド（日本語）を参考にしてください。

論文読解の参考となる知識

---

（標準）シグモイド関数を用いた線形分類

　（標準）シグモイド関数（Sigmoid function）はロジステック回帰に用いられたり、NN（Neural Network）における活性化関数といてよく用いられる。

　シグモイド関数は以下のような性質を持つ。

1. となり、値を確率としてみることも多い。
2. であり、点 に対して点対称となる。
3. 微分可能である。（）

　シグモイド関数を用いた2値分類をする際は、基本的には以下のようになる。

シグモイド関数を用いた2値分類

　以下は、シグモイド関数の描画のためのPythonのソースコードである。

import numpy as np
import matplotlib.pylab as plt

def sigmoid(x):
    return 1 / (1 + np.exp(-x))

x = np.arange(-5.0, 5.0, 0.1) # -5.0から5.0まで0.1刻みで生成
y = sigmoid(x)

plt.plot(x, y) 
plt.show()

• シグモイド関数 - 機械学習の Python との出会い - Toshihiro Kamishima
• 活性化関数のまとめ（ステップ、シグモイド、ReLU、ソフトマックス、恒等関数）- qiita
• ロジスティック関数とシグモイド関数 - 北野坂備忘録

ワイブル分布（Weibull Distribution）*4

　信頼性データのモデル化に最も一般的に使用される連続確率分布である。製品の寿命予測などに用いられることが多い。

　パラメータに対して、のとき指数分布、のときレイリー分布となる。

ワイブル分布の形状

　以下は、ワイブル分布の描画のためのPythonのソースコードである。

import numpy as np
import matplotlib.pylab as plt

def weibullDistribution(z, th, k):
    return np.where(
        z < 0, 0, # z < 0 のとき0をとる
        (k/th) * ((z/th)**(k-1)) * np.exp(-(z/th)**k)
        )

x = np.arange(0.0, 6.0, 0.1) # 0.0から6.0まで0.1刻みで生成
y11 = weibullDistribution(x, 1, 1)
y23 = weibullDistribution(x, 2, 3)

plt.plot(x, y11, label="W(1, 1)")
plt.plot(x, y23, label="W(2, 3)")
plt.legend()
plt.show()

• 平林 浩一: 疲労や破壊現象とワイブル分布, 2002-08-08
• ワイブル分布 - 理論関連事項
• 信頼性分析におけるワイブル分布- Minitab

その他の関数について

ヒンジ関数（Hinge function）

　SVM（Support Vector Machine）の誤差関数として知られる関数。 境界面そのものは際どいため、マージンを持たせる。

符号関数（Sign function）

　実数の符号に対して、-1、0、または1のいずれかを返す関数。

論文を読んだ感想

---

　観測者を経由した流行アイテムの予測は、実際のサービスに対しても適用が十分可能なものであると感じた。 また、本記事に取り上げている論文の内容はイノベータ理論にも関連があると感じ、記事に追加している。

*1:Rogers, Everett M. Diffusion of innovations. Simon and Schuster, 2010.

*2:Yu, Sheng, and Subhash Kak. "A survey of prediction using social media." arXiv preprint arXiv:1203.1647 (2012).

*3:Trusov, Michael, Anand V. Bodapati, and Randolph E. Bucklin. "Determining influential users in internet social networks." Journal of Marketing Research 47.4 (2010): 643-658.

*4:Weibull, Waloddi. "Wide applicability." Journal of applied mechanics 103.730 (1951): 293-297.