ブログのとさか

技術的な話をしたりしなかったり

k-meansとニューラルネットと機械学習と...

もともとk-meansにDeep Forestのカスケード構造を導入したDeep k-meansみたいなものをやろうとしていましたが、あまりうまく行かなかったうえ、そこから得られる考察もあまり面白くなかったので、関連した違う話を書こうと思います。

おことわり

この記事に書いてあることはしっかりと裏を取って書いたことではありません。
解説記事というわけでもなく、考えたことのメモみたいなものです。間違い等ありましたらご指摘お願いします。

k-means

k-meansはk個のクラスタに対応するk個の代表点を定めます。データを分類する際は、そのデータと最も距離が近い代表点が属するクラスタに分類します。

ここでk=2のときを考えます。2つの代表点からの距離が等しくなる軌跡を図示すると、一つの超平面になります。この平面に対して点がどちら側にあるかどうかで属するクラスタが決定されるので、これはn次元空間において分離超平面であるといえます。

これを拡張すると、k>2のときは分離超平面が\displaystyle_ kC_2=k(k-1)/2個配置されると考えることができます。それぞれの超平面による分類結果は、代表点に対応するクラスタ、つまりクラスタiクラスタjの代表点p_ip_jによって配置される超平面の分類結果はiまたはjになるとします。すると、ある点が分類されるクラスタは、全ての超平面によってその点を分類した後、その結果の多数決を取ることによって決定できます。(選ばれるクラスタに分類される回数は常にk回になります。)

このように、k-meansはk個の代表点を用いることで_kC_2個の分離超平面を配置し、それらの分類結果をもとに最終的に属するクラスタを決定する手法であると解釈することもできます。(当然ですがこれはk-meansに限った話ではなく、幾つかの代表点を定めてそれらとの距離で分類する手法一般に言えることです。)

ニューラルネット

全結合ニューラルネットを構成する基本的な人口ニューロンについて考えます。人口ニューロンの結合をベクトルをw,バイアスをb,入力をx,活性化関数をfとすると、出力はf(wx+b)で表されます。するとwx+bは「『wを法線ベクトル,bを定数項とする分離超平面』と『x』の符号付き距離」に,|| w ||を掛けたものだと解釈することができます。詳しくは以下のPDFを見てください。

https://github.com/madoibito80/poem/blob/master/01.pdf

ニューラルネットの層はこの人口ニューロンを複数もっているので、ニューラルネットの1つの層は、複数の分離超平面による分類結果を返している事になります。さらにニューラルネットの層の出力を次の層の人口ニューロンの入力として多値分類を行うと、これはk-meansの時と同様に、複数の超平面による分類結果をもとに最終的な分類結果を決定する手法であると解釈できます。

転移学習的な(ここからポエム感が増します。)

k-meansとニューラルネットは複数の超平面を用いて分類した結果をもとに分類する手法であることがわかりましたが、この話はk-meansやニューラルネットに限らず、多値分類を行う機械学習モデル一般に言えることだと思います。(当たり前の話といえば当たり前の話です。) そう考えると、ニューラルネットの層の初期値を決定するのに、他の機械学習のモデルで得た超平面を用いる手法などがあっても良いような気がしますが、今流行ってないことを考えるとあまりうまく行かないのでしょうか? ラベル付きデータが少ないときなどに教師なしクラスタリングで得た超平面を用いたり、ニューラルネットよりも学習が速い機械学習器で得た超平面を用いたりするのはある程度有効そうな気はしなくもないですが、IMSATのような優れた教師なし学習方法が発展している今の時代には無用の長物なのかもしれません。
ただ、これに関しては後で実験するかもしれません。(Done is better than perfect.に則って実験する前にブログを書きました…)

[追記] 僕もまだちゃんと中身見ていませんが、k-meansでCNNの初期値を定めるのはうまくいくらしいです。

ニューラルネットと同等な表現

ところで、ニューラルネットでもk-meansのように点を決定する手法で分離超平面を配置することができます。(それは同時に法線ベクトルですが…)
学習するベクトルをvとして「座標vを通りvを法線ベクトルとする分離超平面」を配置すると、n次元空間においてはn個のパラメータのみによって全ての分離超平面が表現できます。このvを使ってニューラルネットを構築することも出来ます。
順伝播時には、vによって決定される分離超平面を表す法線ベクトルw=v、バイアス項b=-|| v ||^2とし、通常のニューラルネットと同様に計算します。
これで一つ学習するパラメータを減らしてニューラルネットが構築できたように見えますが、超平面が通る点、つまりバイアス項によってノルムが変化してしまうので、ニューラルネットと同等な表現力をもたせたい場合、実数kも同時に学習させて、出力をkwx+bとすれば良いです。

この表現を得ることで何か嬉しいことがあるのかと言われたら特には思いつきませんが、パラメータを1つでも減らしたい場面がもしあったら使える可能性がゼロでは無いかもしれません。その場合は活性化関数に渡す値を(wx+b)/|| w ||、つまり通常の超平面からの符号付き距離にすることが有効だと思います。(バイアス項によるノルムの変動の影響がなくすことができるため。この場合通常のニューラルネットで言うとノルムを1に常に正規化している状態と同じになり、「各超平面の重み」を表すことができなくなります。)(これに関しては実験を行おうと思います)
ただ、実数kを用いる表現では「法線ベクトルのノルムの意味」と「ベクトルと独立した実数の意味」が通常の人工ニューロンと逆になるという点は少し面白いかなとは思います。

また少し違う話ですが、人口ニューロンでは分離超平面からの符号付き距離を求めているところを、点からの距離にしても学習できるんじゃないかなと思っています。(もちろん式としては違うものが出てきます。また活性化関数も通常のものは使えなくなります。)
結局実験してみないとわからないので、後日試してみたいと思います。

所感

勢いで書いて数式書くのもサボったら非常に読みにくくなってしまいまいました。(追記: とりあえず数式は直しました)
k-meansもニューラルネットも50年以上前に発表されたものなので、今回書いたことはとうの昔に指摘されていることだろうなあとは思っています。

AtCoderのプログラミング入門教材 AtCoder Programming Guide for Beginners の宣伝

この記事はCompetitive Programming Advent Calendar 2016 12/10の記事です。

AtCoderのコンテンツとして、プログラミング入門の教材を作ることになりました。
AtCoder Programming Guide for Beginners」みたいな名前でやっていこうと思っています。

AtCoderのコンテンツなので、当然オンラインジャッジを最大元活用した内容にしていきます。
一応「競技プログラミングのためのプログラミング入門」ではなく、「オンラインジャッジを活用したプログラミング入門」です。 とはいえ、この教材で学び、ACの快感を知ってしまった人は競技プログラミングの世界に自然に入っていけるでしょうし、競技プログラミングの人口増加に繋がるかもしれません。

逐次公開しつつ、みなさんからの意見を受けてフィードバックしながらより良いものを作っていきたいと思っています。
進捗を報告したり、意見を受け付けたりするためのTwitterアカウントを作成したので、気軽にリプライやDMを送って下さい。よろしくお願いします!

内容

この教材の到達目標は「プログラミング初学者が様々なアルゴリズムを記述するために必要なプログラミング言語の文法知識を身に付ける」ことです。
言語はC++を採用します。

オンラインジャッジを活用したプログラミング入門なので、各項目について問題とジャッジを用意します。

まずは、「最速」でプログラムを書けるようになるため、最低限の文法知識を扱います。
AtCoder Biginner ContestのA問題とB問題のほぼ全てと、一部のC問題を解けるようにします。
その後は、アルゴリズムを記述するのに役立つ言語機能や、それまで「おまじない」的扱いを受けていた文法について説明します。

ただし、C++の言語仕様に詳しくなること自体は目的としていないため、詳細な文法の解説はしません。
また、保守性の高いプログラムの書き方や、高度なアルゴリズムとデータ構造等も扱いません。

現状の目次は以下のようなものを考えています。あくまで暫定なので、内容は順番は変化する可能性が高いです。

基礎

  • 導入
  • 出力
  • 四則演算
  • 変数(1)
  • 入力
  • if文
  • 条件演算子
  • bool型
  • 変数(2)
  • while文
  • for文
  • 文字列
  • 配列
  • STL(1)(関数のみ紹介)
  • 関数
  • 数値型とビット演算

繰り返し処理の応用

計算量

  • 計算量について

C++

以上の項目の他に↓のようなページがあったら良いかなぁと思っていますが、労力が余っていれば...くらいに思っています。

  • C++基本文法チートシート(基礎文法最速マスターみたいなもの)
  • プログラムの書き方について(インデント等)
  • 典型コンパイルエラー/バグ集

ちなみに、ポインタを扱うかどうか迷っています。平衡二分探索木とかを実装したかったら必要になるんですが、うーん...

対象者のより詳細な前提知識としては、基本的には中学二年生開始時程度の数学、英語知識を最低限求めるくらいのものにしようと思っています。
PCの知識は、アプリケーションのインストールと見ながらタイピングくらいはできるくらいを想定するつもりです。
説明が冗長になりすぎない範囲でできるだけハードルを下げたいと思っているので、実際には中学1年生でもわかるくらいの書き方になっていると思います。
中高の部活動から大学生以上まで広く使われる教材になったら良いなあと思っています。

明日のCompetitive Programming Advent Calendar 2016はmatsu7874さんの記事とhotpepsiさんの「バグ」です。

以下はおまけです。


プログラミング入門とオンラインジャッジ

オンラインジャッジを用いたプログラミング入門は非常に効率的だと思います。

プログラミングはプログラムを書かないと覚えられません。しかし、一般的な入門書でプログラミングを覚えようとすると、入門書に書いてあるコードを写経するだけで終えてしまう人が多いです。
また、ソフトウェア制作を通じたプログラミング入門も、GUI周りのAPIを覚えること等とプログラミング言語の文法を覚えることが混在してしまい、 プログラミング言語そのものの知識を身に付ける方法としてあまり効率的でない面があります。

それに対し、オンラインジャッジを用いたプログラミング入門では、学んだ文法を使う問題を解くことによって、より確実に知識を定着させることができます。
プログラミング言語以外で覚えなければならない要素もほとんどありません。

さらに、ACしていくことはかなりモチベーションに繋がります。入門書にも例題がついていることはありますが、基本自己採点になってしまいますし、答えが載っていないことすらあります。 オンラインジャッジでは、コンパイルと出力の確認だけとはいえ、ある程度確実な採点を行えますし、オンラインジャッジに「AC」と出るのは自己採点よりも強い快感があると思います。

一通り文法を学び、教材で用意した問題を解き終わった後も、他の問題を解いたり、開催されているコンテストに参加することによって、プログラムを書く能力を上げていくことができます。 「プログラミングに興味はあるけど、作りたいものがあるわけではない」という人は案外多く、そういった人たちにとってこのことは重要だと思います。

オンラインジャッジを活用した日本語のプログラミング入門教材は、僕の知る限り現状AOJ系のものだけです。この資料はAOJの資料とはまた違った価値を提供していきたいです。

教材作成者について

教材の構成等は「経験上」という曖昧な感覚から決めているため、どういう経験をしてきたのか、自分語りをしておきます。

僕は中高時代コンピュータ部の部長を務めていました。
部長として部員のレベルを上げるため、中1~高1くらいの人に対し、プログラミングをよく教えていました。対象者の前提知識が中学生程度なのは、このこととも関係しています。
プログラミングの入門教材を作るのは実は二度目で、中学3年生の時に部活の仲間とC#の入門教材を作ったことがあります。
コンピュータ部の宣伝として、コンピュータ部外の人にプログラミング講座を開催したりもしていたので、今までプログラミングを教えた人数は多分50人~100人(超大雑把)くらいでしょうか。
今回の教材ではそこでの経験を活かしていきたいと思っています。

競技プログラミング経験としては、JOI春合宿の出場経験があり、大学生になってから引き続きICPCに出場しています。
アルゴリズムを記述するのに役立つ言語機能」は実際の所、競技プログラミングで使われる言語機能のことですが、今まで見てきた競プロのソースでよく見る or 便利だと思ったものを扱っていきたいと思っています。

書いてる途中の感想

基礎のところは半分くらい書き上がってますが、やっぱ読みやすい文章書くのは難しいなあと感じています。 文章書くのが遅いので、この教材作成経験を通じて速くしていきたいですね。(まぁよく見ると文章量は大したこと無く、説明のほとんどがサンプルコードみたいなことが多いですが...)
「あ、これも説明しないといけないんだった」みたいなことが頻発し、一章書き上がったら一章増えるみたいなことが起きていて、自分たちが普段書いているプログラムも意外と多くの知識の元で作られているんんだなぁというのを実感します。

教材を作るにあたって、本屋や図書館で色々とプログラミングの入門書を眺めているんですが、質の高い本もある一方、びっくりするような(遠回し)構成の入門書が結構多くてなんだかなぁと思うことがあります。160ページとかではじめてif文が出てきたJavaの入門書(初学者向けっぽいタイトルをしている)には流石に驚きました...
全体的な傾向として、入門書の書き方は意外と難解だと感じました。この教材ではできるだけ易しく説明することでも一般的な入門書との差別化を図っていきたいと考えています。

グラニ インターン体験記

インターン体験記

8/15~9/2の間、株式会社グラニにエンジニアとしてインターンに行っていました。
少し(だいぶ)遅れましたが、簡単にどんな感じだったのかまとめておきたいと思います。

(以下の話でおかしな点があった場合、僕の解釈間違いです。念のため。)

ラニ

f:id:tosaka2:20160927050151p:plainラニはモバイル端末向けゲーム開発会社です。
スローガンの一つとして「using CSharp;」を掲げており、C#Visual Studioを主軸において開発を行っています。
.NET 界隈ではMS MVPでUniRxの作者である@neueccさんがCTOを務めていることでも有名だと思います。

インターンの経緯

もともと夏休みはこれといった予定がなく、せっかくなのでアルバイトかインターンをしようかなあと思っていました。
どういった会社にするかは少し迷いましたが、最近開発のモチベーションが落ちてきていて良くないなあと思っていたこともあり、モチベーションを上げるためにも開発業務が行える会社でアルバイトかインターンをしようと決めました。

僕はC#が好きなので、C#をメインで使っており、開発者のレベルが高い会社で本格的な開発現場を体験したいと思いました。 最近ではC#統一を掲げている会社にも幾つか候補がありますが、以前から名前を知っているグラニに一番にお願いすることにしました。

ただ、グラニの公式サイトを探してもインターンとアルバイトの申し込みページが見つからなかったので、neueccさんにDMを送ってお願いすることにしました。 しかし、DMを送る直前になって「公式サイトに無いということは募集してないということなのでは...」「自分程度の技術力で申し込むのは迷惑なのでは...」といった不安にかられ、とても緊張して送信ボタンを押したのを覚えています。女の子に告白するときくらい緊張しました(?)。

実際には募集ページはちゃんと存在していて、僕が見つからなかっただけのようでした。(DMの返信で教えていただきました。「新卒採用」ボタンをクリックした先のページにあったようです。 募集職種一覧) ただ、今までグラニはエンジニアのアルバイトやインターンを受け入れたことが無かったので、社内での「エンジニアのインターン」という存在の知名度も低かったようです。 (あと実は筑波大学にもインターンの募集をかけていたらしいのですが、僕は全く知りませんでした...)

その後応募ページから応募して後日の面接を行い、日付、だいたいの内容、待遇などを相談し、グラニインターンすることが決定しました。

職場の環境

オフィスは六本木ヒルズ 森タワーの15階にあり、ビルの入口付近に設置されているゲートに社員証(画像)をかざして中に入る形でした。
15階が全てグラニのフロアというわけではないので、15階に上がった後またグラニの中に入る際に社員証をかざさないと入場できません。 お手洗いはグラニの外にあるので、社員証の携帯が必須なのですが、一度社員証を机に忘れ、NEW GAME!1話の青葉みたいになるところでした。

PCは3面ディスプレイでメモリ32GBのものが一台貸し与えられました。
椅子も高級そうな感じで、一日そこで作業してても疲れにくかったように感じました。インターンのお給料でまともな椅子を買おうかなと真面目に検討中です。

また、最高だったのがフリードリンクです。(「自由ソフトウェア(free software)」ではなく「ドリンク飲み放題(free drink)」と考えて下さい)(伝わりにくいネタ
レッドブルからヨーグルトジュース、オレンジジュース、コーラ、お茶、ココア、コーヒー、炭酸水、牛乳その他諸々があり最高でした。コーヒとココアに関しては↓みたいな感じの自販機が2種類置いてあって、無料で使えました。(適当にググってきたのでまんまこれではないかも)

さらに、朝ごはんの支給もありました。始業時間30分前(午前10時)から社員の方がトーストを焼いてくれるので、毎日美味しくいただいてました。トーストの他にはコーンフレークやバナナ、ゆで卵等もありました。

バイル端末ゲーム開発業界はブラックなところも多かったりするという話を以前聞いたことがありましたが、グラニは全くそんなことはなく、社員が働きやすい環境を整えることに非常に気を使っているように感じました。
職場環境を整える他にも、(僕はインターン生なので関係ありませんでしたが)福利厚生が充実していて、「オシャレ手当」というので申請すると服代が一定額支給されたり、職場近くに住む場合は家賃手当が出たりするそうです。そのため、六本木ヒルズから徒歩10分~15分くらいの距離に住んでいる方が多くいるようでした。

やったこと

本来ここがメインなような気もしますが、書けないことが多いので短めです。
当然使用言語はC#です。HTML/JS/SQL等も多少いじりはしました。グラニというと最近はUnityという感じもしますが、僕は基本的にASP.NET MVC 5上での開発を行っていました。僕はWeb方面がかなり弱点だなあと思っていたので、いい経験になりました。 また、実装完了後に仕様が変わるという「エンジニアの洗礼」も受けることができ、感動しました。(非常に妥当な変更で、作業量もそれほど多くなかったので負の感情等はないです。念のため。)

開発そのもの以外では、社内で「.NETのクラスライブラリ設計」輪読会が行われており、それに参加させていただきました。5,6人の少人数で対象の本の特定の章を事前に読んでおき、書いてある内容について、主にneueccさんがそれに対するコメントをした後、他の参加者も自分の考えを述べるというような形式でした。
主な目的は「設計思想の共有」でした。あるフレームワーク上でプログラムを書くとき、そのフレームワークの思想に沿ってプログラムを書くことによって、より自然で使いやすい形になります。また、プログラムの設計に関しては様々な思想がありますが、少なくとも同じプロジェクトのチーム内ではその思想が統一されているべきです。 そこで、この会では.NETというフレームワークがどのような思想で設計されているのかに加え、社内フレームワークの思想についても、現状のプロジェクトの失敗と成功の例もあげながら語られていました。
対象の章は大した量ではありませんでしたが、2時間~3時間くらいかけてじっくり行われました。 特に印象に残っているのが、「三種の神器」の話です。(以下の話はまとめたもので、実際はより掘り下げた話がありました。)

  • IntelliSensability インテリセンスを使いやすくする
  • Navigatability(多分違う命名をされてましたが忘れました...) コードナビゲーションを大事に。F12や「参照」などから、定義元に飛びやすくする。
  • Stacktraceability スタックトレースで呼び出し元を探しやすくする

C#はその言語仕様からしてVisualStudioを始めとしたリッチな開発環境での開発しやすさを考えられています。.NET Frameworkに関しても同様です。そのため、上記のようなC#特有のことにも気を配ると、「実際に扱いやすい」プログラムを書くことができます。
上の話も含め、普段適当にネットの記事を見ていてもあまり触れられていない話を多く聞くことができたので、本当に勉強になりました。

他にも、株式会社一休さんとのミーティングに参加させていただいたり、「Team Geek」から、「HRT」の講義をしていただきました。HRTとは、

  • Humility (謙虚)
  • Respect (尊敬)
  • Trust (信頼)

の略です。グラニではこのHRTを常に意識し、コミュニケーションを円滑に行おうという運動が社内全体であるようです。(詳しくは書籍「Team Geek」で)

ちなみに、上で触れている「.NETのクラスライブラリ設計」と「Team Geek」の書籍をインターン最終日にいただきました。圧倒的感謝...!? (ちなみに .NETの本は現在廃盤なので物理書籍の方は結構レアものです。)
(画像)

感想

3週間を通して、本当に勉強になりました。「開発者のレベルが高い会社で本格的な開発現場を体験」という目的も果たすことができました。
ラニの皆様、そして色々と面倒を見てくださったして下さった@xin9leさんへの感謝の気持ちでいっぱいです。本当にありがとうございました。

おまけ お昼ごはん

お昼ごはんはグラニの皆様のご厚意で六本木の様々なところに連れて行っていただきました。せっかくなので紹介したいと思います。

1日目 トリュフハンバーガー
ちなみに一緒に来た他の方はステーキを食べており、「六本木のエンジニアは昼からステーキを食べるのか...」と衝撃を受けました。 (実際は普段ははなまるうどんを食べているそうです) f:id:tosaka2:20160927042744j:plain

2日目 焼肉
社内チャットサービスでC#を動かすことが出来るので、C#で抽選するプログラムを書いた結果焼肉になりました。 f:id:tosaka2:20160927045350j:plain

3日目 寿司
f:id:tosaka2:20160927045354j:plain

4日目 ニョッキ
写真撮り忘れました。

5日目 ササミかつ
ものすごくサクサクで感動しました。 f:id:tosaka2:20160927045356j:plain

6日目 ペヤング ソース焼きそば
台風だったので... 社内コンビニで買いました(会社が半額以上負担してくれる。商品が置いてあってコインを入れて持ってく形式。)

7日目 会社弁当
社内で弁当が販売されています。500円でした。

8日目 ラーメン+親子丼
f:id:tosaka2:20160927045358j:plain

9日目 とんかつ
f:id:tosaka2:20160927045359j:plain

10日目 おうどん+とろたく丼
つるとんたんってお店で変わったうどんがたくさんあります。(自分は比較的普通のうどんをたのみました)。あと容器がすごくでかいです。
f:id:tosaka2:20160927045401j:plain

11日目 ラーメン
普段食べてるラーメンよりだいぶ美味しかったです。
f:id:tosaka2:20160927045403j:plain

12日目 天ぷら
f:id:tosaka2:20160927045405j:plain

13日目 うどん
写真を撮り忘れたので食べログからの借り物です。
これもかなり美味しかったのでまた食べたいです。
f:id:tosaka2:20160927045406j:plain

14日目 ビュッフェ
f:id:tosaka2:20160927045408j:plain

15日目 ピザ
f:id:tosaka2:20160927045410j:plain

美味しいものを食べすぎた副作用か、インターンの期間が終わった後から平気で高いものを食べようとしてハッとなることがあります。怖い怖い...

ちなみに、お昼休みは主にスマブラWiiUで遊んでました。(一度ポーカーにも誘っていただきました。) インターンのときに使ってたもの以外のキャラも多少使えるようになったのでまた勝負したいです。

ICPC予選参加記

ICPC(国際大学対抗プログラミングコンテスト) 2016 国内予選にチームprinding–purantei–として参加し、予選を通過しました。ヤッター!

さて、prinding-purantei-のチーム編成は、僕(1年)、中国人留学生(1年)、先輩(2年)となっていました。
ICPC予選出場経験のある先輩と、中国のJOI(Jじゃないけど)に参加していた留学生という頼りがいのある二人と組むことができ、いいチームで出られたと思います。

予選本番では
A: 僕, B:先輩, C:僕, D:留学生
の問題をそれぞれ通しました。

D問題は留学生がバグらせて少し時間がかかっていたので、僕も実装をしようとしてパソコンを交代してもらったりもした(ICPCでは1チーム1台のPCしか使えません)のですが、最終的に彼のプログラムでACしました。
彼がプログラムをバグらせ続けて通せないという最悪のケースが起こらないように、と考えての行動でしたが、結果論では僕が余計なことをしなければもっと早くACできたわけで、どうするのが正解だったのかなあと思いました。
プログラムを再実装すること以外にも、彼のコードを印刷してバグ探しをしたり、ペアプログラミングをしたりすることもできたので、もしかしたらそちらのほうが良かったのかもしれません。

順位としては 全体49位 学内2位 で予選敗退ラインだったのですが、選抜ルール手順3のワイルドカード枠で予選を通過しました。(順位表

手順3で選ばれるチームはアジア予選のホスト校から選ばれることが多いらしく、 僕が所属するチームは今年のホスト校である筑波大学内の(手順2までの)不通過チームのうち順位が最も高いチームだったため選ばれたのだと思います。筑波大学でよかった~~~
ちなみに、他の手順3での通過チームには、6位の東京大学のチームと48位の神奈川工科大学のチーム、56位の金沢高専のチームが選ばれたようです。

ホスト校枠で通ってしまったので、4完して同じくらいの順位だったのに予選落ちしてしまった他大学の友人のチームには少し申し訳ない気もしますが、彼らの悔しさも背負って(?)10月のアジア地区予選に向けて精進したいと思います。

SuperCon 2016 予選問題をCSPソルバーで解く

SuperCon 2016 参加者の皆さん予選お疲れ様でした。予選通過するといいですね。 僕は高校生で無くなってしまったので本戦への参加権はありませんが、予選問題を読んだところCSPソルバーでさくっと解けそうだったのでやってみました。

※この記事はしっかりとした解説記事ではなく、紹介程度のものです。

CSPソルバーとは

CSPソルバーとは、問題の制約を決まった形式のテキストに変換し、そのファイルをCSPソルバーに渡して上げると、内部で「いい感じ」に問題を解いてくれるというツールです。予選参加者のみなさんは頑張って探索を最適化していったと思いますが、CSPソルバーを使うと簡単なテキストファイルを生成するだけでそれなりに高速に問題を解いてくれます。(とは言ってもみなさんのガチガチにチューニングしたプログラムの方がだいぶ速いと思います。)

CSPソルバーで虫喰い魔方陣を解く

百聞は一見にしかず。CSPソルバーについての詳しい説明は横において、今回の問題を解く様子を見てみましょう。CSPソルバーにはSugarを使います。
とはいっても、魔方陣の解法については自分が書くことはあまりなく、「CSPソルバー 魔方陣」で検索すると

http://bach.istc.kobe-u.ac.jp/sugar/puzzles/sugar-puzzles.pdf

というスライドのPDFが引っ掛かり、このスライドにある3×3魔方陣のCSPファイルと同じように6×6用のCSPファイルを生成するだけで解くことができます。

具体的には以下のようになります。

;それぞれの魔方陣のマスに入る数をx_i_jという変数で表す
(int x_0_0 1 36);整数変数 x_0_0 の宣言。範囲は 1 <= x_0_0 <= 36 となる。
(int x_0_1 1 36)
(int x_0_2 1 36)
(int x_0_3 1 36)
(int x_0_4 1 36)
(int x_0_5 1 36)
(int x_1_0 1 36)
(int x_1_1 1 36)
(int x_1_2 1 36)
(int x_1_3 1 36)
(int x_1_4 1 36)
(int x_1_5 1 36)
(int x_2_0 1 36)
(int x_2_1 1 36)
(int x_2_2 1 36)
(int x_2_3 1 36)
(int x_2_4 1 36)
(int x_2_5 1 36)
(int x_3_0 1 36)
(int x_3_1 1 36)
(int x_3_2 1 36)
(int x_3_3 1 36)
(int x_3_4 1 36)
(int x_3_5 1 36)
(int x_4_0 1 36)
(int x_4_1 1 36)
(int x_4_2 1 36)
(int x_4_3 1 36)
(int x_4_4 1 36)
(int x_4_5 1 36)
(int x_5_0 1 36)
(int x_5_1 1 36)
(int x_5_2 1 36)
(int x_5_3 1 36)
(int x_5_4 1 36)
(int x_5_5 1 36)

; すべての変数は互いに違う数を取る
(alldifferent x_0_0 x_0_1 x_0_2 x_0_3 x_0_4 x_0_5 x_1_0 x_1_1 x_1_2 x_1_3 x_1_4 x_1_5 x_2_0 x_2_1 x_2_2 x_2_3 x_2_4 x_2_5 x_3_0 x_3_1 x_3_2 x_3_3 x_3_4 x_3_5 x_4_0 x_4_1 x_4_2 x_4_3 x_4_4 x_4_5 x_5_0 x_5_1 x_5_2 x_5_3 x_5_4 x_5_5)

;縦、横、対角線のマスに入る数の和が111になる(ポーランド記法で書く)
(= 111 (+ x_0_5 (+ x_0_4 (+ x_0_3 (+ x_0_2 (+ x_0_1 x_0_0))))))
(= 111 (+ x_1_5 (+ x_1_4 (+ x_1_3 (+ x_1_2 (+ x_1_1 x_1_0))))))
(= 111 (+ x_2_5 (+ x_2_4 (+ x_2_3 (+ x_2_2 (+ x_2_1 x_2_0))))))
(= 111 (+ x_3_5 (+ x_3_4 (+ x_3_3 (+ x_3_2 (+ x_3_1 x_3_0))))))
(= 111 (+ x_4_5 (+ x_4_4 (+ x_4_3 (+ x_4_2 (+ x_4_1 x_4_0))))))
(= 111 (+ x_5_5 (+ x_5_4 (+ x_5_3 (+ x_5_2 (+ x_5_1 x_5_0))))))
(= 111 (+ x_5_0 (+ x_4_0 (+ x_3_0 (+ x_2_0 (+ x_1_0 x_0_0))))))
(= 111 (+ x_5_1 (+ x_4_1 (+ x_3_1 (+ x_2_1 (+ x_1_1 x_0_1))))))
(= 111 (+ x_5_2 (+ x_4_2 (+ x_3_2 (+ x_2_2 (+ x_1_2 x_0_2))))))
(= 111 (+ x_5_3 (+ x_4_3 (+ x_3_3 (+ x_2_3 (+ x_1_3 x_0_3))))))
(= 111 (+ x_5_4 (+ x_4_4 (+ x_3_4 (+ x_2_4 (+ x_1_4 x_0_4))))))
(= 111 (+ x_5_5 (+ x_4_5 (+ x_3_5 (+ x_2_5 (+ x_1_5 x_0_5))))))
(= 111 (+ x_5_5 (+ x_4_4 (+ x_3_3 (+ x_2_2 (+ x_1_1 x_0_0))))))
(= 111 (+ x_5_0 (+ x_4_1 (+ x_3_2 (+ x_2_3 (+ x_1_4 x_0_5))))))

ただし、このCSPファイルはすべての魔方陣のマスが開いている状態の制約を表しているので、既に埋まっている場所は制約として追記して上げる必要があります。 例えば次の魔方陣の場合、

18 13 35
20 33 19 7
2 32 10 9
30 3 15
29 4 26 28
5 31 16

以下の様に制約を追記します。

(= x_0_1 18)
(= x_0_3 13)
(= x_0_4 35)
(= x_1_1 20)
(= x_1_2 33)
(= x_1_3 19)
(= x_1_4 7)
(= x_2_1 2)
(= x_2_2 32)
(= x_2_4 10)
(= x_2_5 9)
(= x_3_0 30)
(= x_3_3 3)
(= x_3_5 15)
(= x_4_1 29)
(= x_4_2 4)
(= x_4_4 26)
(= x_4_5 28)
(= x_5_2 5)
(= x_5_3 31)
(= x_5_4 16)

あとはこのファイルを適当な名前(ここではmahou.cspとします)で保存し、sugarに渡すだけです。

% sugar mahou.csp
s SATISFIABLE
a x_0_0 6
a x_0_1 18
a x_0_2 25
a x_0_3 13
a x_0_4 35
a x_0_5 14
a x_1_0 11
a x_1_1 20
a x_1_2 33
a x_1_3 19
a x_1_4 7
a x_1_5 21
a x_2_0 36
a x_2_1 2
a x_2_2 32
a x_2_3 22
a x_2_4 10
a x_2_5 9
a x_3_0 30
a x_3_1 34
a x_3_2 12
a x_3_3 3
a x_3_4 17
a x_3_5 15
a x_4_0 1
a x_4_1 29
a x_4_2 4
a x_4_3 23
a x_4_4 26
a x_4_5 28
a x_5_0 27
a x_5_1 8
a x_5_2 5
a x_5_3 31
a x_5_4 16
a x_5_5 24
a

この通りに埋めると

6 18 25 13 35 14
11 20 33 19 7 21
36 2 32 22 10 9
30 34 12 3 17 15
1 29 4 23 26 28
27 8 5 31 16 24

となり、確かに解けていることが分かります。(すごい!)

実行時間をtimeコマンドで計測すると

real 0.94
user 0.46
sys 0.47

となりました。まぁまぁですかね。実行環境はVirtualBox上のUbuntu(メモリ1GB、CPU Core i7-6650U 2.20GHz)、内部で使用しているSATソルバーはMinisatです。
最悪ケースでどうなるかは自分も確かめてないので試してみてください。

このように、CSPソルバーを使うと問題の解が簡単に得られます。もちろん魔方陣以外にも様々な問題を解くことができます。
SuperConのような単一のソースファイルを提出するコンテストではこれをそのまま回答コードとして流用するのは難しいですが、覚えておくとテストケース生成の際などに役立つかもしれません。

参考

ひとりごと

本当は魔方陣のルールをdirect encodingとorder encodingで表すプログラムをそれぞれ書いて比較するっていうテーマにして、Sugarはついでで紹介するだけみたいなブログ記事にする予定だったけど、ちょっと時間が取れ無さそうだったのでとりあえずSugarの紹介だけすることにしました...
あと本当はWindows上でSugarを動作させたかったけど、うまく行かなかったので後回し中。でも大体原因がわかった(と思う)ので、もしできたらそれについてのブログも書くかも...?
SuperCon、現役としてもう一回やりたかったなあ。

SRM 677 Div1 Easy DoubleOrOneEasy

https://community.topcoder.com/stat?c=problem_statement&pm=14101&rd=16627

問題概要

整数a, b, newA, newBが与えられる。 (a, b)に対しそれぞれ同時に+1または*2する操作を繰り返して(newA, newB)に変える時の、操作の最少回数を求める。(変えられないなら-1)

ゆるふわな解法

+1を2回することは*2を1回することと等しいので、一番最初に*2をする前以外で+1を2回以上するのは無駄だよね。 という話から、最初に+1する回数をx、*2をする回数をnとすると、操作は(a * 2^n) + (x * 2^n) + (1or0 * 2^(n-1)) + ... + (1or0 * 2^1) + (1or0 * 2^0)みたいな式で表せることがわかる。
(x * 2^n) + (1or0 * 2^(n-1)) + ... + (1or0 * 2^1) + (1or0 * 2^0)をkとおくと、a * 2^n + k == newA && b * 2^n + k == newBとなる時のnが答えの操作で*2する回数になる。 このnはたかだかlog(newA)<30程度なので1から順に試せばOK。
ちなみに(1or0 * 2^(n-1))以降の1or0の並びはnewA - (a * 2^n) + (x * 2^n)を2進数で表した時と等しくなるので、この部分で+1した回数はpopcountで求められて嬉しい。
計算量O(log(newA))

コード

INT_MAXのところを始めINF(= 1 << 29)にしていて落ちたりした。不注意...
そもそもa==bの時以外はremA==remBになったらすぐreturnしてもいいんだけどね。

#include "bits/stdc++.h"
using namespace std;

const int INF = 1 << 29;

//VSでコーディングしてるので拝借してきました http://www.nminoru.jp/~nminoru/programming/bitcount.html
int popcount(int bits)
{
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}

class DoubleOrOneEasy
{
public:
    int minimalSteps(int a, int b, int newA, int newB)
    {
        int kake = 1;
        int ksum = 0;
        int ans = INT_MAX;
        while (a * kake <= newA && b * kake <= newB)
        {
            int remA = newA - a * kake;
            int remB = newB - b * kake;
            if (remA == remB)
            {
                int tmp = ksum + remA / kake + popcount(remA % kake);
                ans = min(ans, tmp);
            }

            kake *= 2;
            ksum++;
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

解いた問題をブログに上げるというのを初めてやってみたところ、意外と書くのが面倒で解説はもはや分からせる気も厳密に書く気もない感じになってしまった。
この問題はなんとなく競プロしようと思って最近の問題から適当に選んだけど、久しぶりに(自分にとって)やるだけじゃない問題を解いた気がする。
SRM Div1の問題を提出したのは初めてかもしれない。TopCoderCodeforcesは今までほとんどやって来なかったのでどんどんやっていきたいなあ。

(操作ミスで記事を消してしまったため再投稿です)

優秀な同世代の仲間を見つけよう

この記事について

中高生プログラマ Advent Calendar 2015 6日目です。
どうも皆さん。とさか2です。高校3年生をやっています。
「中高生プログラマ」という肩書の中では一応年長者(このアドベントカレンダーでは高専4,5年生の方も参加していますが)なので、今までの経験から、まだまだ中高生をやっていられる優秀で有望な皆さんに向けて伝えたい的な記事です。あまり技術的な話はしません。

自己紹介

この企画は学生間の交流を兼ねてるらしいので、自己紹介をします。
一番得意な言語はC#です。開発と競技プログラミングをしてます。コンピュータ部の部長を務めていたりもしました。CTFはあまりやってませんが、scryptosで準メンバー的に何回か参加してました。
他の分野だとゲームAI・機械学習ヒューリスティックアルゴリズムの勉強をしたりコード書いたりしています。
CombGigでは一応運営側として参加してたので、そこで会ったことがある人もいるかもしれません。
twitter@nanTosaka2です。( 諸事情あって鍵がかかっています。もう少ししたら外すかも。 鍵外しました)

本題

皆さん御存知の通り、一口に「プログラミング」と言っても様々な用途があります。
それに伴い、プログラマのコミュニティも用途ごとに形成されています。特に最も人口が多い「ソフトウェア開発」に関しては、使用言語やフレームワークなどでそれなりに強くコミュニティが分断されています。
それ以外の要素として、所属組織や住んでいる地域によって分けられることを考えると、各々が所属するコミュニティは必然的に小さくなります。

さらに、開発コミュニティは平均年齢が高く、中高生が同世代と同じコミュニティで出会うというのはなかなか難しいように感じます。
結果として、同世代の中で自分が一番優秀なのではないかという気がしてくるのがよくあるパターンです。
それはそれで幸せな生き方だとは思います。しかし、技術力を上げるという観点から見ても、「自分が一番優秀だ」というのが思い込みだった場合、早めにそれに気付いた方が良いでしょう。
勘違いをしていなくても、優秀な同世代の仲間がいたほうがモチベーションが上がると思います。さらに言えば、将来的に有用な人脈になるかもしれません。

というわけで、ここでは優秀な同世代の仲間と出会う方法について書いていきたいと思います。

1.twitter

すべてはtwitterのアカウント作成から始まります。 以下で紹介する方法で出会った人と繋がりを保つにはtwitterが一番です。 また、ある程度繋がりが広くなってくるとtwitterを通じて新しく知り合うことも出てきます。 アカウントを持っていない人は絶対に作りましょう。

2.セキュリティ・キャンプ

セキュリティ・キャンプは、合宿形式の情報セキュリティ技術に関する勉強会です。
大学生以下対象なので、一度に大量の同世代の人々と出会うことが出来ます。参加者は、セキュリティに詳しくない人でも、別のコンピュータ技術分野には精通している人であることが多いので、そのつもりで交流すると良いでしょう。
参加のためには選考を通る必要がありますが、それさえ通れば交通費含め全額無料で参加できるので最高です。 夏に一度ある全国大会以外にも、地方大会が行われているそうなので、地方の方はまずそちらに参加してみてもいいでしょう。

3.競技プログラミングの大会への参加

競技プログラミングは、「アルゴリズム」の設計と実装の能力を競うプログラミングを使った「競技」です。与えられた問題を解くプログラムを作成し、提出すると機械的に採点され、それの結果に応じて順位が付きます。
プログラミングコンテストと呼ばれることもありますが、アプリケーションを作成して提出するもの(U22プログラミングコンテストなど)とは全くの別物です。
順位がつくので強さがはっきりと分かります。初めたばかりの頃は上位陣の圧倒的な実力に驚かされるでしょう。

一応書いておくと、これはソフトウェア開発とは非常に異なるものなので、プログラマだからといって競技プログラミングが出来なければいけないわけでは決してありません。
しかし、プログラミングと深い関わりを持ちながらも、開発ではあまり触れることのない「アルゴリズム」を身をもって体験できるので、一度くらい取り組んで見るのが良いと思います。練習を重ねると実装速度が上がるので、開発にも役立ちます。あと単純に面白いです。

中高生向けの大会では以下の三つが有名です。 以下の全ての大会では競技時間とは別に懇親会等の時間が設けられているので、勝ち上がったら存分に交流することが出来ます。
1. 日本情報オリンピック
2. パソコン甲子園 プログラミング部門
3. SuperCon

日本情報オリンピックは予選で勝ち上がると関東にある会場に集められ本戦を行い、そこで20位以内に入ると代表選考合宿に参加できます。さらにそこで3位以内になると、日本代表として、海外で行われる国際情報オリンピックに参加できます。ここでかかる交通費や宿泊費等は全て無料です。最高。
パソコン甲子園の本戦は会津大学で行われます。勝つとガッツリ賞金をもらえます。
SuperConの本戦は大阪大学東京工業大学で行われます。この本戦は独特で、 スーパーコンピュータ上で行います。スパコンプログラミングは通常のプログラミングと異なる部分が結構多いので、結構面白いです。
ちなみに、以上の三つで結果を残せば大学受験で有利になったりもします。参加しない手はないな!

中高生向けの大会以外でも、様々なコンテストが開催されています。国内だとAtCoderが有名です。社長は@chokudaiさんです。
基本オンラインですし、参加費も無料なので気軽に参加してみましょう。

「競技プログラミングをしている」というだけで結構簡単に繋がりが広げられると思うので、おすすめです。

4.JOI夏季セミナー

夏期セミナーは先述の情報オリンピックを開催している団体が開いている合宿です。書類選考はありますが、競技プログラミングが出来なくても参加できます。
情報科学に関連する本を読んで演習(実装)したり講義を聞いたりします。これは参加者も扱う内容もレベルが高いです。
僕は日程が合わず一度も参加できなかったのでものすごく後悔しています。皆さんは後悔の無いようぜひ参加してください。

5.中高生向け勉強会

中高生向けの勉強会に参加するか、皆さんの手で開催してください。様々な人と交流できます。
CombConfCombGig・Comb Meetup等の前例があります。
開催のノウハウは@mt_caretに相談すれば喜んで教えてくれると思います。お気軽にどうぞ。
僕はもう中高生では無くなりますが、次の開催者が現れることを期待しています。


以上です。
これらのイベントに参加する際は、名刺を用意しておくのが一般的なので、作っておきましょう。twitterのハンドルを書くのを忘れずに!