経営企画室の見原です。フォルシアは先日、京都大学と「ダイナミックプライシングについての共同研究開始」を発表する記者会見を都内で開催しました。会場には、たくさんの報道陣にお集まりいただき、発表した内容については新聞、ネットメディアなど多数の媒体で大きく取り上げていただくことができました。今回はその舞台裏をご紹介します。 プレス発表の基本の「き」 記者会見の準備といえば、発表スライドの作成、お招きするメディアの方々へのご連絡、当日のタイムスケジュール策定、会場・司会進行役の選定、小道具の用意......など、たくさんすべきことがありますが、一番忘れてはいけない準備は、「プレスリリースの作成」です。プレスリリースとは、報道機関に向けて自社の情報を発信する文書。今回の場合は、会見当日に会場で報道陣に配布するほか、同日にプレス発表として自社のコーポレートサイトやプレスリリース配信サイトで掲載する目的で作成します。 当然のことながら、広報担当者の私自身も内容を理解していないと文書を作成できないので、今回の研究の話が出始めた頃から、関係者が集まる打ち合わせにはなるべく顔を出すようにしていました。最初の頃は他のメンバーが話している内容が理解できずに、初歩的な質問をして周囲に心配の眼差しを向けられることや（気のせい？）、わからない用語はこっそりとGoogle先生に聞くこともありました。しかし、何度も話を聞いたり調べたりしていくうちに、少しずつ理解を深めていきました。 （何度も修正を重ねて完成したプレスリリースは こちら ） バックパネルが会見に間に合わない プレスリリースの準備は順調に進んでいったのですが、会見の本番直前まで私たち広報メンバーをもやもやさせていたのは、登壇者の後ろに立てかける「京都大学」と「FORCIA」のロゴを印字した大きいパネル。皆さんも記者会見の映像や写真でご覧になったことがあるかと思いますが、あのパネルって案外サイズが大きいので自分たちで作るのは難しいし、専門の制作会社に依頼しても時間がかかるんです。 実は、今回の会見の開催が確定したのは本番まであと数日......！というタイミング。案の定、どの制作会社さんでも「間に合わないから無理」と断られ続けました。こうなったらもう自作するしかないか......と半ばあきらめモード。それでも、ダメもとで駆け込んだ某大手印刷会社さんに、イレギュラーな対応をしてもらい、ギリギリ何とか制作してもらえることになりました！ とはいえ、どう頑張っても仕上がりは本番前日の夜とのこと。当日まで完成物を見られないため、きちんと仕上がっているか、また、何らかの事情で間に合わなかったらどうしようかと、ずっとヒヤヒヤしていました。が、当日、会見本番1時間半くらい前に立派なパネルが会場に届いて、ひとまずホッ。会見本番でも大活躍でした（パチパチ）。 天気も味方し、盛況だった記者会見 ぐずついた天気が続いていた東京でしたが、関係者の誰かが「晴れ男 or 女」なのか、会見当日は朝から気持ちの良い快晴でした。会見の会場は都内にある京都大学の産学連携本部。私たち広報メンバーのほかに、強力な助っ人社員たちに受付・案内や、会場設営、記録係などを担当してもらって準備は万端です。 冒頭にもお伝えしたとおり、当日は本当に多くの報道陣の方々にご来場いただき、無事に記者会見を開くことができました。会見では、京都大学の梅野教授と弊社の代表屋代、経営企画室長洲巻、エンジニア兼研究員の新谷が登壇し、本共同研究についてお話ししました。 白熱の質疑応答 会見終盤には質疑応答の時間を設けていたのですが、予想以上にたくさんの質問をいただいたおかげで大盛り上がり！なるべくまんべんなく記者の方々からの質問に回答できるように予定していた時間を大幅に拡大しました。このことからもダイナミックプライシング自体が世間的にも注目されている値付けの手法なのだということを実感したのと同時に、京都大学とフォルシアが行う共同研究のテーマにも興味をもっていただけたのではないかと手応えも感じています。 そんな白熱した質疑応答タイムで、報道関係者の方々から実際にいただいた質問の一部をご紹介します。 何年後に実装するのか？スケジュール感は？ 「人によって提示する価格が変わる」という価格変動はすでに行われているのか？ 「人によって提示する価格が変わるのは不公平だ」という考えなど、社会的にはダイナミックプライシングに反発もあると思うが、心理的な部分についてはどう思うか？ ダイナミックプライシングの新しいモデルを実装した場合のサービス供給側へのメリット、ユーザー側へのメリットをそれぞれ整理して説明すると？ 上記はほんの一部ですが、これらの回答と、プレスリリースと会見で発表した情報、そして、別途取材していただいた内容から、ご覧のような記事を書いていただきました！ ■日経xTECH（18/9/28） フォルシアと京大がダイナミックプライシングの共同研究、公正な値付け目指す https://tech.nikkeibp.co.jp/atcl/nxt/news/18/02829/ ■CNET Japan（18/9/28） 需給バランス不整合の解消に向け、最適価格設定を研究--フォルシアと京都大学 https://japan.cnet.com/article/35126288/ ■日本経済新聞電子版（18/10/1） 「ダイナミック値付け」共同研究フォルシア・京大 https://www.nikkei.com/article/DGXMZO35947710R01C18A0XY0000/ ■ITmedia（#SHIFT）（18/10/3） サービスは変動価格が当たり前に？フォルシアと京都大学が共同研究 http://www.itmedia.co.jp/business/articles/1810/03/news043.html ■日経産業新聞（18/10/4） レジャー価格需給で変動情報検索システムのフォルシア https://webreprint.nikkei.co. jp/r/LinkView.aspx?c= 7E63B54D37E34D24A04647D3F2A2A2 FC 記事を読むと、熱い質疑の端々が結晶となって織り込まれていることがよくわかりますね。 具体的にどのような研究を行うのか。その詳細については近日中に研究員の新谷より記事にしてもらう予定です。ご興味がある方は、そちらの記事もぜひ楽しみにしていてください！

こんにちは！技術本部・インターンシップ企画チームの川口です。梅雨があっという間に明け、いよいよ夏がやってきますね。夏といえば...いろいろ思い浮かぶものはありますが、学生の皆様の中ではインターンをしたいと考えている方も多いのではないでしょうか？フォルシアでは、自分の研究や経験を活かして活躍したいエンジニア志望の学生の皆様に向けた、ワクワクするようなインターンシップをご用意しました！（もちろん有給です！） 概要は下記リンクをご覧ください。（現在は終了しております） FORCIA Summer Internship 2018 Rust、Alexa... フォルシアならではの選べる８コース 検索アプリケーション開発コース 検索高速化コース Rust検索エンジン開発コース Alexa Skill開発コース Google Hotel Ads配信最適化コース データ分析コース データクレンジングコース UI/UXコース ８コースも用意しているインターンシップなんて、なかなか無いのではないでしょうか...！プログラミングの経験がある方や情報系の研究をされている方のみならず、理数系の知識・経験がある方等に幅広く来ていただく為に、これらのコースをご用意しました。 ここではいくつかのコースをご紹介します。 ① 検索アプリケーション開発コース スタンダードなコースとしてご用意しました。フォルシアではエンジニアの大半が検索アプリケーションの開発を行っており、その業務に実際に携われるコースです。担当するアプリケーションに関して、仕様の検討から新規機能の実装までを行います。大手旅行会社様やMRO業界、福利厚生業界の多くが導入している検索プラットフォーム「Spook」に込められたエンジニアのこだわりを実際に感じ取ることができるコースです。 ③ Rust検索エンジン開発コース フォルシアでは新しい検索エンジン開発を日々行っております。そのうちの一つでは、Rustという現在ではまだ商用利用が少ないプログラミング言語を使用しています。このコースではそんなプログラミング言語のニューウェーブ（！）、Rustを使って爆速検索エンジンを開発できます。 ④Alexa Skill開発コース 最近話題のスマートスピーカー。フォルシアではAlexaでの検索Skillの開発も行っています。スマートスピーカーの開発はとにかく奥が深い...！以前にも 当ブログで紹介していますが 、webアプリなどと比較して、画面がないスマートスピーカーでは、スマートスピーカーではアウトプットの情報量が圧倒的に少ないため、ユーザーの求める検索結果をピンポイントで返す必要があります。このような音声UIの研究をしてみたい方、ぜひ④Alexa Skill開発コースへご応募ください！ ８コース、どれに応募しようか悩ましい、という方は、ぜひその旨をエントリーシートに記載してください。研究内容や経験を考慮し、ご案内することもできます。 メンターはフォルシアトップレベルのエンジニア 優秀なインターン生には優秀なメンターを...と、メンターは社内でもトップクラスのエンジニアに依頼しました。 例えば、⑦データクレンジングコース のメンターはチーフエンジニアの光山さんにお願いしました。光山さんは東京大学大学院理学系研究科を卒業し、新卒６年目。大型案件の荒波を何度も乗り越える中で、顧客の持つ元データについて研究を重ねてきました。Spookでは、ユーザーが本当に使いやすい検索プラットフォームを提供するべく開発を行っておりますが、検索結果に表示するのはあくまで元のデータ。ユーザーが検索結果に納得感を持つためには、元のデータの精度や量、整合性が必要となります。このコースでは、機械学習を駆使して元データの研究を行っていただきます。光山さんは「機械学習を始めとした最先端の技術でビジネスの課題解決をする醍醐味を、優秀な学生の皆さんにぜひ味わって頂きたいです。」と、メンターの依頼を快く引き受けてくださいました。当ブログでは、タフで優しい光山さんの インタビュー記事 を掲載していますので、ぜひ併せてご覧ください。 もちろん、メンター以外のエンジニアも適宜インターン生をサポートします！Slackで困っていることを書き込むと、皆で優しくフォローしてくれるような雰囲気です。 伝えたいのは技術だけじゃない インターンシップでは、フォルシアの技術以外にもお伝えしたいことがたくさんあります。速さ・プロダクトへのこだわりや、ユーザーへの思いやり、技術力を用いたビジネス等、エンジニアが持つべき "エンジニアリング技術以外の技術" をフォルシアのエンジニアから直接学べる機会にしたいと思います。 また、インターンシップ期間中は社員とのランチ会などの交流の場を設けます。どんな人が働いているのか？どんな仕事内容なのか？福利厚生はどうやって使っているのか？など、気になるポイントについてどんどんお聞きください！フォルシア社員の持つ雰囲気に惹かれて入社を決めた社員も多く、社員との交流を通じて実際にその雰囲気を感じていただければいいなと考えています。 自分の強みを活かしたい学生の皆様をお待ちしております フォルシアの次世代のパワーとなるようなインターン生を募集しています。 下記のリンクの中の応募フォームより、ご自身の研究内容・経験・興味等をぜひアピールしてください！ FORCIA Summer Internship 2018 （現在は募集を終了しております） インターンシップ企画チーム・社員一同、皆様のご応募、お待ちしております！

技術本部の龍島です。最近Microsoftが GitHubを買収するというニュース が世間を騒がせていますね。GitHubがMicrosoft傘下に入った後も今までの中立的な立場が保たれるかが注目されるところです。 そんな中、GitHubの競合サービスであるGitLabに 注目が集まっています 。フォルシアでもソースコード管理にGitLabを利用しているので、今日はGitLabの始め方やフォルシアでの運用についてご紹介したいと思います。 GitLabとは GitLabとはGitリポジトリホスティングをするソフトウェアでGitレポジトリの管理はもちろんのこと、Issue、Wiki、Merge Request(GitHubで言うPull Request)などの機能が備えられています。機能としてはGitHubと遜色なく、特にCI周りはGitLabの方が力を入れており、GitHubより優位で機能が豊富です。 また、GitHubは GitHub.com でクラウドサービスとしての提供が基本で、オンプレミスで動かすには有償のGitHub Enterpriseを利用する必要があります。GitLabは GitLab.com のようにクラウドサービスもありながら、オンプレミスかつ無償でプライベートな環境に構築することも可能なのが大きな魅力の一つです。 フォルシアでもGitLabをオンプレミスで利用しており、IssueやMerge Request、CI機能を利用した開発を進めています。 GitLabをはじめる オンプレミスでGitLab Community Editionを始めてみましょう。 公式ページのガイド が詳しいのでこちらに則って入れていくのが良いです。（dockerでの構築方法などもあります。） CentOS6系を例としたものがこちら。 # http, sshアクセスの許可 sudo yum install -y curl policycoreutils-python openssh-server cronie sudo lokkit -s http -s ssh # 必要なパッケージのインストール sudo yum install postfix sudo service postfix start sudo chkconfig postfix on # gitlabのインストール curl https://packages.gitlab.com/install/repositories/gitlab/gitlab-ee/script.rpm.sh | sudo bash sudo yum -y install gitlab-ce これで最低限の準備は完了です。インストールしたサーバにブラウザでアクセスするとルートユーザの設定画面へ遷移するはずです。 /etc/gitlab/gitlab.rb に設定ファイルがあるので、色々といじってみると良いでしょう。数行で簡単にGitLabが始められますね。 フォルシアでのGitLab運用 フォルシアではGitLabを Vagrant で管理されたVM上で動作させています。Vagrantの設定ファイル(Vagrantfile)にはプロビジョニングスクリプトを指定できるので、GitLabを構築するためのスクリプトを用意しておき、 vagrant up するだけでGitLabの環境が作成されるようにしています。 Vagrantfile, provision.sh(プロビジョニング用スクリプト)は下記のようなイメージです。 Vagrantfile Vagrant.configure(2) do |config| config.vm.box = "bento/centos-6.7" config.vm.hostname = "gitlab" #providerはlibvirtを利用 config.vm.provider "libvirt" do |libvirt| libvirt.storage_pool_name = "STORAGEPOOLNAME" libvirt.management_network_name = "NETWORKNAME" libvirt.management_network_address = "NETWORKADDRESS" libvirt.storage :file, :size => "40G" libvirt.memory = "8192" libvirt.cpus = "4" end config.vm.provision :shell, :path => "provision.sh" end provision.sh #!/bin/bash # GitLabのインストール yum install -y postfix cronie service postfix start chkconfig postfix on curl -s https://packages.gitlab.com/install/repositories/gitlab/gitlab-ce/script.rpm.sh | sudo bash yum install -y gitlab-ce-9.2.7-ce.0.el6.x86_64 # install versionは固定 # GitLabの設定の適用 cp /vagrant/files/gitlab.rb /etc/gitlab/ gitlab-ctl reconfigure 公式のガイドから不要な部分は削っています。Vagrantfileのあるディレクトリに設定ファイル files/gitlab.rb を事前に用意しておき、自動で予め決めた設定が反映されるようにしています。 運用Tips フォルシアでのGitLab運用のTipsを少しご紹介します。 マシンスペック 上記のVagrantfileにスペックが記載されていますが、CPU4コア、メモリ8GBで運用しています。利用人数は100人に満たない程度なので 推奨されるマシンスペック よりは余裕を持ったスペックとなっていますが、バックグラウンドジョブが多いことや利用のサクサク感を重視したいことからこの割当となっています。 ユーザ認証 フォルシアでは各個人のマシンやファイルサーバのユーザ認証にLDAPを利用しています。GitLabでも数行程度の設定で LDAPが利用できる ため、GitLabのために新たにユーザ管理の仕組みなどを作る必要はありませんでした。 バックアップ GitLabは設定ファイル gitlab.rb と バックアップファイル だけあれば復元することができます。GitLab.comでは2017年に 本番データベースを喪失してしまう なんて事件がありましたが、適切にバックアップを取得し保管しておけば有事の際も問題はありません。VagrantでVMを作り直し、バックアップファイルを適用すればものの15分程度で復旧が可能です。 簡単に環境を復元できることはアップデートの検証の際にも役立ちます。URLを変えて別のVMでGitLabのミラーサーバを立ち上げ、そこでアップデートを実施し問題ないかの検証を手軽に行うことができます。 手軽にオンプレミスで始められるのはGitLabの大きな魅力です。オンプレミスだとトラブル時の対応にコストが...と思われがちですが、数年運用してきた中で大きなトラブルが起きたことはなく、安定して稼働しています。現在GitHubを利用されている方もこの機会にGitLabの利用を検討されてはいかがでしょうか？

技術本部の龍島です。本日は、今話題のスマートスピーカーについて。昨年より日本でも普及が進み、最近ではAmazon、Google、LINEなどのテレビCMでも目にすることが多くなりましたね。皆さん、実際に使ってみたことはありますか？ フォルシアではAmazon Alexaを利用したスキルの開発に取り組んでいます（ JTB宿泊検索スキル ）。様々な検索サイトの構築を行ってきたフォルシアが、VUI（Voice User Interface）での検索システムを構築するに当たり、感じたことや直面した音声特有の問題をご紹介したいと思います。 画面（GUI）と音声（VUI）の違い まず、従来までのPCやスマホの画面を通じたインターフェース（GUI）での検索とAlexaなどのVUIの違いを考えてみましょう。 ユーザの自由度 従来までのGUIでは、画面の設計でユーザの行動を制限することができました。ラジオボタンやプルダウンを置いておけばユーザはどれかを選んでくれますし、日付選択カレンダーを置いておけば日付を選択してくれます。しかしVUIでは「日付を教えて下さい」と言ってもユーザがなんと答えるかはわかりません。ちゃんと日付を答えてくれるかもしれませんし、「日付は決めないで探したい」「やっぱりやめる」「最初に戻って」などと言われるかもしれません。作り手が期待する以外の発話をユーザがした際の対応を考えていく必要があります。ユーザ行動の自由度の高さはVUIの大きな特徴と言えるでしょう。 情報量 アウトプットの情報量もGUIとVUIの大きな違いです。GUIでは文字で大量の情報を画面に表示することが可能で、伝えたい情報は文字の色や大きさを変えたり、画像を用いたりすることでユーザに効率的に届ける事ができました。必要でないかもしれない情報もとりあえず画面に載せておくことで、ユーザに情報を取捨選択させるということも可能です。しかしアウトプットが音声のVUIでは提供できる情報量は限られています。長々しい商品説明文をユーザは聞いていられないので、ユーザの求める情報をピンポイントで簡潔に届ける必要があります。 ユーザの慣れ 見落としがちなのがユーザがそのインターフェースにどれだけ慣れているかです。GUIは既に多くの人が利用することに慣れており、意図する動作をさせるためにどうしたら良いかを知っています。例えば、ブラウザで前のページに戻りたければ左上の矢印を自然と押しますし、画面の下の方を見たければマウスホイールを回したり画面を上にスワイプしたりします。これは多くのブラウザが左上に戻るボタンがあり、画面を下にスクロールしていくUIにユーザが慣れているからです。しかし多くの人にとってVUIは初めての経験で、「今の発話をキャンセルしたい」や「終了させたい」「違うアプリを開きたい」と思った時にどうしたら良いかわからずユーザが迷ってしまうことがありえます。VUIがまだ出始めて間もないUIというのが原因ですが、適切にヘルプを出すなどしてユーザが迷子になってしまわないように設計していく必要があります。 GUIとVUIの課題の違い GUIとVUIの違いは「文字」と「音声」の違いと考えることができます。地名を例にとって文字が音声に変わるとどういった問題が起こるのか考えてみましょう。 同音異漢字問題（仙台と川内） 宮城県の仙台（せんだい）と鹿児島県の川内（せんだい）のように同じ読みで漢字が異なる地名に起こる問題です。音声情報だけではこれら2つを区別することができませんので、現状ではユーザに「宮城県、鹿児島県、どちらのせんだいですか？」と聞くことになります。文字であれば2つを区別することができるので、音声特有の問題と言えるでしょう。 異音同漢字問題（清水と清水） 静岡県の清水（しみず）と京都府の清水（きよみず）のように異なる読みで漢字が同じ地名に起こる問題です。文字では区別できないですが、音声では区別することが可能です。しかし、現状のAlexaにおいてはAlexa内で音声を漢字に変換して連携される仕組みとなっているためスキル側に連携される情報は漢字のみとなり、2つを区別することができません。今後、読み情報が連携されるようになることで解消できる可能性があります。 同音同漢字問題（草津と草津） 群馬県の草津（くさつ）と滋賀県の草津（くさつ）のように同じ読み、同じ漢字の地名に起こる問題です。当然ですがこれらを文字、音声から区別することは不可能です。ユーザにどちらの草津かを聞き返す必要が出てきます。 しかし、この問題に限らず上記3つの問題全てに言えることですが、前後の文脈を読むことでこの問題は解消できる可能性があります。例えば「杜の都せんだい」といえば宮城県の仙台を指しているでしょうし、湯畑を調べた後に「くさつ」と言えば群馬県の草津を指している可能性が高いでしょう。キーワードの周辺から情報を集めることで、ユーザの意図するキーワードを推測することはこれから可能になっていくと思われます。 VUIのこれから VUIのカギはインプット、アウトプット共に扱える情報が少ないことにあると思います。ユーザが求めるものはコンシェルジュのような、ひとこと言えば文脈を読んで欲しい情報を簡潔に返してくれるようなものでしょう。それを実現するためにはユーザの発話以上の情報が必要です。例えばそのユーザが以前ダイビングについて調べていた、という情報を事前に得られていれば、「この夏の良い旅行先教えて」とだけ言われた時に「沖縄はいかがでしょう？」と、よりユーザが欲しがるレコメンドができます。ユーザからのインプットが少なくなってしまう以上、発話以外のユーザ情報をいかに集め、簡潔かつ有益な情報をユーザに返すかがこれからのVUIでは重要になってくるでしょう。

技術本部の松本です。フォルシアでは、2019年新卒の学生を対象に、ワークショップや会社説明会を実施しています。エンジニア志望者向けのワークショップでは、膨大かつ複雑なデータから高速に最適解を導く独自の「高速検索技術」を、プログラミングの実践を交えながら学べるプログラムを用意しています。 本日は特別に、4月24日（火）に青山で開催したエンジニアワークショップで出題した問題を解説します。 問題 Level1 Level2 Level3 まとめ 今後のワークショップのご案内 問題 それでは、実際に出題した問題を見ていきましょう。 問題文 N人の身長 h_i とQ個の質問クエリが与えられます。 各質問クエリは、 (h_min_j, h_max_j) の2要素で構成されます。 このとき、それぞれのクエリについて h_min_j <= h_i <= h_max_j を満たす人数を答えなさい。 ※身長、クエリはすべて整数である。 入力 入力は標準入力から以下の形式で与えられる。（「←」以降は注釈です） N Q ← このあと身長のデータがN個、次いでクエリがQ個入力される h_1 ← 1番目の身長 ︙ h_N ← N番目の身長 h_min_1 h_max_1 ← 1番目のクエリ ︙ h_min_Q h_max_Q 出力 各クエリに対して答えとなる値を整数で出力せよ。 Sample Input 0 3 1 4 9 5 3 5 Sample Output 0 2 Explanation 0 3人の身長 4,9,5 とクエリ (3, 5) が与えられます。身長が3以上5以下の人は1番目(4)と3番目(5)の2人です。したがってクエリ (3, 5) に対して出力すべき値は2です。 Sample Input 1 5 2 2 3 4 4 4 1 1 4 4 Sample Output 1 0 3 Explanation 1 身長が1以上1以下の人は0人です。身長が4以上4以下の人は3人です。 Sample Input 2 6 2 10 2 5 6 10 8 6 7 1 9 Sample Output 2 1 4 Explanation 2 身長が6以上7以下の人は1人です。身長が1以上9以下の人は4人です。 Level 1 上記の問題設定に具体的な制約（入力の値域）を与えて、各レベルの問題を見ていきたいと思います。まず非常に値の小さい問題を考えます。 制約(Level1) 1 <= N <= 10 1 <= Q <= 10 1 <= h_i <= 10 1 <= h_min_j <= h_max_j <= 10 この問題を解決する単純なプログラムを実装します。 全員の身長を配列に格納し、 各質問について各人の身長が範囲内に収まっているかを判定し、 条件に当てはまる人数を答えます。 下記がPython3の実装例です。 Python:Level1実装例 N, Q = map(int, input().split()) P = [] for i in range(N): h = int(input()) P.append(h) # 各質問ごとに for i in range(Q): h_min, h_max = map(int, input().split()) count = 0 # 各人の身長を判定する for p in P: if h_min <= p <= h_max: count += 1 print(count) 上記アルゴリズムの計算量はQ回のループ(8行目)の中にN回のループ(13行目)が入っているため O(QN) になります。手元の環境で実行してみると0.1秒以下で出力が返ってきます。 Level2 制約(Level2) 1 <= N <= 10,000 = 10**4 1 <= Q <= 10,000 = 10**4 1 <= h_i <= 10,000 = 10**4 1 <= h_min_j <= h_max_j <= 10,000 = 10**4 Level2ではそれぞれの値が1000倍になります。Level1で実装したプログラムでは、答えを出すまでに約8秒の時間が必要になります。 Level1で実装したプログラムのどこに時間がかかっているかを考えましょう。2重ループによって合計 Q * N 回も身長の比較が行われています。 実際に自分がこの作業を行うとしたらと考えてみると、身長が明らかに範囲から外れている人には何度も質問しないでしょう。 質問ごとに各人の身長を判定するアルゴリズムは "毎回「全員」の身長を確かめる必要がある" 点が非効率です。 それでは、どうすれば "「全員」に対しての判定" を避けられるかを考えてみましょう。 〈Level2のポイント〉 数えるのではなく、計算する。 上限以下の人数から下限に満たない人数を引くことで条件を満たす人数を計算することができます。 学校の大掃除で「12番から16番の5人は窓拭き！」のようなシーンがありませんでしたか？ 事前にソートしておく。 ソートされているというのは強い性質で、昇順にソートされていて、i番目の人が下限未満の場合、i-1番目以下の人も下限未満であることが明らかです。 これらのポイントをふまえると、問題は次のように言い換えられます。 〈問題の言い換え〉 ソートされた配列から下限未満の最後の人、上限以下の最後の人を見つけたい。 ここで、注意したい点があります。前から順番に見ていくと、探している人が配列の後ろの方にいた場合、結局ほぼすべての人の身長を確認することになります。 もっと効率良く計算するために、何人かをピックアップして質問をしたいと思います。 基本情報技術者試験を勉強している人や情報系の人なら聞いたことがあるかもしれませんが、 "真ん中の人から聞いて解の存在空間を半分にする" という考え方があります。 これは "二分探索" と呼ばれる探索アルゴリズムの一つで、今回の問題設定と相性が良いため、二分探索を使ってみましょう。 二分探索を使用して「ソートされた配列からある値T以上の最初の人のインデックス」を探します。 P を身長が昇順にソートされた配列、配列 P 中で身長 T 以上の最初の人のインデックスを探すとして説明を進めます。 P[lb] < T <= P[ub] (※)を満たすように lb, ub を初期化します。この条件を保ちながら更新することが二分探索のポイントです。 m = (lb+ub)//2 (平均の小数点以下切捨)として P[m] < T ⇒ lb = m , T <= P[m] ⇒ ub = m と解の存在範囲を更新します。 lb+1 == ub が成り立つとき、(※)の条件から ub こそが「ある値T以上の最初の人のインデックス」であることが分かります。 例として下記の入力が与えられたとき、身長がh_min=3以上の最初の人のインデックスを求めます。 N = 12 H = {1, 2, 2, 4, 4, 5, 6, 6, 7, 7, 7, 10} h_min=3, h_max=6 P[0]=1 < T=3 であることを確認した上で、 lb=0, ub=len(P)=12 で初期化します。※配列中にT以上の値がない場合はPの要素数(=12)を返します。 m = (lb+ub)//2=(0+11)//2=5 となります。 P[m]=P[5]=6 >= T=3 なので ub = m=5 に更新します。 m = (lb+ub)//2=(0+5)//2=2 となります。 P[m]=P[2]=2 < T=3 なので lb = m=2 に更新します。 m = (lb+ub)//2=(2+5)//2=3 となります。 P[m]=P[3]=4 >= T=3 なので ub = m=3 に更新します。 lb+1 == ub が成り立ち、「身長がh_min=3以上の最初の人のインデックス」は ub=3 であることが分かります。 処理の流れが分かったところで、実装をしてみます。 Python:Level2実装例 """ ソートして二分探索 """ import bisect N, Q = map(int, input().split(" ")) P = [] for i in range(N): h = int(input()) P.append(h) # O( N*logN ) P.sort() # O( Q*logN ) for i in range(Q): h_min, h_max = map(int, input().split()) count = 0 lower = bisect.bisect_left(P, h_min) upper = bisect.bisect_left(P, h_max + 1) print(upper - lower) 標準ライブラリを使っている二分探索部分を書き下すとこうなります。 """ 二分探索 """ def bisect_left(array, target): if target <= array[0]: return 0 lb = 0 ub = len(array) while lb + 1 < ub: m = (lb + ub) // 2 if target <= array[m]: ub = m else: lb = m return ub 予めソートする手間はかかるものの、1回ソートしておくだけで、Q回のクエリ処理にかかる時間を大幅に短縮することが出来ます。事前にN人の身長をソートする計算量が O(NlogN) 、Q個のクエリそれぞれに対して、二部探索を行う計算量がO(QlogN)で、合計の計算量は O(NlogN) + O(QlogN) になります。 Level3 Level3では制約を更に10倍にした問題を考えます。 制約(Level3) 1 <= N <= 100,000 = 10**5 1 <= Q <= 100,000 = 10**5 1 <= h_i <= 100,000 = 10**5 1 <= h_min_j <= h_max_j <= 100,000 = 10**5 Level2でも高速に検索できてはいますが、まだ無駄な部分があります。1回のクエリを処理するときに2回の二分探索を実行し、前後の境界となる人を探す作業をしています。今回の問題設定では具体的な人を特定する必要はなく、人数だけに着目すれば十分です。情報の持ち方を変えて、各身長ごとに何人いるかを持ってみましょう。 人数だけを配列に持った場合、クエリに対する処理は「下限から上限までの各身長ごとの人数の和」として表現することができます。ここでも注意が必要ですが、クエリごとに下限から上限までを足していったのでは、 O(QH) の計算量になり、身長の幅が大きい場合に改善がされません。 情報の持ち方を更に一工夫して、身長i以下の合計人数をi番目の要素として持つような配列を考えましょう。これは O(N+H) で準備できます。Level2と同じ具体例を使って説明します。 初めに身長の値域分の配列を確保しておき、各人の身長を読み込んだら、対応する値を+1します。この処理は加算N回で O(N) です。次に P[i] = P[i] + P[i-1] として P[i] が身長i以下の人数を表すようにデータを持ちます。この処理は身長の上限まで足す必要があるため、加算H_MAX回が必要で O(H_MAX) です。 この配列上で、上限と下限の引き算を行うことで、範囲に含まれる人数を答えることが可能です。事前に人数を足して持っておくことで、クエリに対しては１回の引き算( O(1) )でレスポンスする事ができます。この手法を累積和といいます。 Level3のポイントを考えてみましょう。 〈Level3のポイント〉 身長情報の持ち方を変える 毎回の探索さえ必要ない 引き算1回で計算すべし Python:Level3実装例 """ 累積和 """ H_MAX = 10**5 N, Q = map(int, input().split(" ")) P = [] lower_count = [0] * (H_MAX + 1) # 身長i以下の人数をlower_count[i]に格納する。 for i in range(N): h = int(input()) lower_count[h] += 1 # O( H_MAX ) for i in range(H_MAX): lower_count[i + 1] += lower_count[i] # O( Q ) for i in range(Q): h_min, h_max = map(int, input().split()) upper = lower_count[h_max] lower = lower_count[h_min - 1] print(upper - lower) # 人数が分かっているので引き算だけで答えがわかる。 計算量は O(N) + O(H) + O(Q) になります。毎回の探索が必要ないため、高速に処理をすることが出来ます。 まとめ 今回のワークショップでは、制約の大きさに合わせてアルゴリズムの改善と考え方を紹介しました。 データ数が少ないなら、実装が簡単な全探索。 データ数が多い場合はソートしておいて二分探索。（前処理） データ数だけが必要になる場合、データ数だけ数えておいて、引き算する累積和の手法が使える。（データの持ち方を変える） つい先日も社内slackで「O(N)をO(logN)に改善しました！」という話題が上がっていました。計算量を考えながらアルゴリズムの改善をすることに面白さを感じた方、一緒に働けるのを楽しみにしています！ 今後のワークショップのご案内 実際のワークショップでは参加者の皆さんが、Level1で問題を理解して、Level2の実装に取り組むという様子でした。競技プログラミングに慣れている方は、Level2までは瞬殺、Level3にチャレンジしていましたよ。 今後もフォルシアでは、ワークショップの開催を予定しています。エンジニアとしての知見を広げたい方フォルシアのことを知りたい方、ぜひご応募お待ちしております！ ワークショップの日程、お申し込みは こちら