問題:
No.551 夏休みの思い出(2) - yukicoder
想定解は
https://yukicoder.me/problems/no/551/editorial
だが、原始根を無視してmod_sqrtを使って解いた。
mod_sqrtは(多分)O(log(p)^2)-timeで解けると思う。
gist.github.com
問題:
No.551 夏休みの思い出(2) - yukicoder
想定解は
https://yukicoder.me/problems/no/551/editorial
だが、原始根を無視してmod_sqrtを使って解いた。
mod_sqrtは(多分)O(log(p)^2)-timeで解けると思う。
gist.github.com
Rustでtreapと2-3 treeを実装してブログを書きました。
treap: Treap on Rust - Codeforces
2-3 tree: 2-3 tree on Rust - Codeforces
(Codeforcesなので英語です)
Hackerrankの
Indeed Machine Learning CodeSprintに参加しました。
SVMで分類しようと試みましたが、結果は芳しくありませんでした。(175.33/1000点!w)
この得点は、最初すべてのrowに対して"2-4-years-experience-needed"を返す実装を投げたことによって達成されました。そのあと色々試しましたが、これを超える性能を出すことはできませんでした。
Job descriptionを何らかの方法でベクトルにして、12種類のタグそれぞれに対して、そのタグがつくかつかないかの2値分類をSVMでやろうと思いました。
文章のベクトル化は、単純に記号を除去し、大文字をすべて小文字にして、単語の頻度を計算することで行いました。
ソース:
gist.github.com
さんざん(説明文を変えてもほとんど線形変換の後のベクトルに差が出ず、全て同じ値に分類された)
以下のスクリーンショットでは、800個ごとに分類結果を表示していますが、class (タグのありなしを+1/-1で表した分類結果)は全て同じで、Ax+b (ソース158行目)の値(classの1行下に表示)もほとんど変化がないという結果になっています。
もう少し勉強が必要でした。まだ原因究明ができていないので、他の人のコードを実行したりしながら勉強します。
tl;dr: Apacheで数独サーバーを作った話 - koba-e964の日記の続きです。
前回(Apacheで数独サーバーを作った話 - koba-e964の日記)の制作途中でいただいた以下のようなコメントがきっかけで、lighttpdでも作ってみることにしました。
— しえる@cf16::002 (@cielavenir) 2017年3月10日
http://koba-e964.hatenablog.com/entry/2017/03/11/033819:title:前回でApache 2.4を使っていたところを、代わりにlighttpd (バージョンは現在apt-getで手に入る1.4.33)を使って作りました。
これにより、完成品のDocker imageの大きさが628MB (Apache版) -> 356MB(lighttpd版)になり、大幅に軽量化できました。
https://sparkle-sudoku-solver.herokuapp.com/から遊べます。
バージョン情報:
root@87a939323768:/# lighttpd -v
lighttpd/1.4.33 (ssl) - a light and fast webserver
Build-Date: Jan 28 2014 17:26:04
root@87a939323768:/# date
Sun Mar 12 15:19:00 UTC 2017
imageのサイズ:
$ docker images sparklenumberplace_lighttpd
REPOSITORY TAG IMAGE ID CREATED SIZE
sparklenumberplace_lighttpd latest 5f5683b70260 10 hours ago 356 MB
$ docker images sparklenumberplace_web
REPOSITORY TAG IMAGE ID CREATED SIZE
sparklenumberplace_web latest 797b93561b96 23 hours ago 628 MB
記事執筆時点でのソース:
GitHub - koba-e964/sparkle-number-place at a30029f7cfc4897b9fbcc2eaa26f52356512ca5e
*1:heroku上のファイルシステムはephemeralなので、一度作ったテンポラリファイルがずっと残っていることを前提にプログラミングをしてはいけません。(dynoが停止または再起動するタイミングで消えます。) またファイルシステムはdynoごとに作られるので、/tmp/を介して別のdynoと通信をすることはできません。参考: 公式、Herokuで一時ファイル保存 - 木木木
*2:GitHubのissueで議論がされているので、興味があったら是非読んでみてください。
*3:DockerfileをDockerfile.lighttpdへのsymbolic linkにして、herokuの目を欺くやり方です。こんな小手先の対策とりたくなかったです…
tl;dr: Apache + Dockerでサーバーを作ってherokuにdeployしました。ソルバーは
https://sparkle-sudoku-solver.herokuapp.com/
にあります。
数独パズルを解く、Web上で動くソルバーを作りました。(https://sparkle-sudoku-solver.herokuapp.com/)
0から9までの数字を9行に81個空白区切りで並べたものを与えると、それを数独パズルとみなして、可能な解を一つ返します。*1
この記事を書いた時点でのソースはここにあります。
ソルバーは以前書いてあったものを流用しました。数独のパズルを受け取ってCNFの論理式に変換し、minisatに投げて結果(充足する真偽値割り当て)を受け取り、そこから解となる盤面を計算します。今回はナイーブな実装を行ったので、どんな場合でも729変数、3240節のCNFになります。ソースはgen-cnf.rbです。
追記(3/11 12:21): SATソルバーについてはProgramming on SATというわかりやすい記事があります。
サーバーはApache 2.4を使用しました。Docker imageをここから取得して、その上にrubyとminisatをインストールしてサーバーを起動します。Dockerfile
最小のコストでCGIサーバーを動かすことを目標にしてソフトウェアを選びました。*2これより簡単な方法でサーバーを作る方法をご存知の方は、教えていただけるとありがたく思います。
最終的に作ったdocker imageをherokuにデプロイすることでheroku上でサーバーが動くようになります。heroku container:pushを実行した時の出力は次のようになります(ソースより前のバージョンのpushなので、ソースとの整合性はありません):
$ heroku container:push
Sending build context to Docker daemon 186.4 kB
Step 1/13 : FROM httpd:2.4
---> f316d5949bb0
Step 2/13 : ENV MINISAT_VERSION 2.2.0
---> Using cache
---> 8b96b7e5836c
Step 3/13 : RUN apt-get update && apt-get install -y curl g++ gem make ruby yum zlib1g-dev
---> Using cache
---> 01c356dcace4
Step 4/13 : RUN curl -L http://minisat.se/downloads/minisat-${MINISAT_VERSION}.tar.gz >/tmp/minisat-${MINISAT_VERSION}.tar.gz && cd /tmp && tar zxf minisat-${MINISAT_VERSION}.tar.gz
---> Using cache
---> 420f926984f1
Step 5/13 : RUN cd /tmp/minisat && export MROOT=`pwd` && cd core && make rs && cd .. && cd simp && make rs && cd .. && cp -p core/minisat_static /usr/local/bin/minisat22_core && cp -p simp/minisat_static /usr/local/bin/minisat22_simp
---> Using cache
---> 66a7d907bc81
Step 6/13 : RUN cd /usr/local/bin && ln -s minisat22_core minisat
---> Using cache
---> 3e81832a1ba6
Step 7/13 : RUN sed -ri 's/#LoadModule cgid_module/LoadModule cgid_module/g; s/Options Indexes FollowSymLinks/Options Indexes FollowSymLinks ExecCGI/g; s/#AddHandler cgi-script .cgi/AddHandler cgi-script .rb .pl .cgi/g' /usr/local/apache2/conf/httpd.conf
---> Using cache
---> 93ac06565e51
Step 8/13 : EXPOSE 80 80
---> Using cache
---> 31dea6708dd8
Step 9/13 : COPY files/gen-cnf.rb /usr/local/apache2/htdocs/gen-cnf.rb
---> 89a66d1a6689
Removing intermediate container dc206958f995
Step 10/13 : RUN chmod a+x /usr/local/apache2/htdocs/gen-cnf.rb
---> Running in 7dd0626c9d96
---> 1064c2ac079f
Removing intermediate container 7dd0626c9d96
Step 11/13 : COPY files/handler.rb /usr/local/apache2/htdocs/handler.rb
---> 46c1ed0f2dda
Removing intermediate container fb6381e4e384
Step 12/13 : RUN chmod a+x /usr/local/apache2/htdocs/handler.rb
---> Running in ca1a7fa67491
---> 7af09916047e
Removing intermediate container ca1a7fa67491
Step 13/13 : COPY files/index.html /usr/local/apache2/htdocs/index.html
---> 1e7a71852b93
Removing intermediate container f93929edeec6
Successfully built 1e7a71852b93
The push refers to a repository [registry.heroku.com/sparkle-sudoku-solver/web]
68422698f5cc: Pushed
af543c01d744: Pushed
5cfa10e2d863: Pushed
81cafbc89c7a: Pushed
d7ffb6f22450: Pushed
38625d3b26b6: Pushed
3aba0ea84b6e: Pushed
5f0c09555780: Pushed
e39e2811255e: Pushed
9ce897855b2e: Pushed
e62aea9889eb: Pushed
efe6d8194a9f: Pushed
d4d164dfebb6: Pushed
cd0e01770f2a: Pushed
9feccb840a3a: Pushed
c86b3fdc78cf: Pushed
d17d48b2382a: Pushed
latest: digest: sha256:8a060a2ceba13a4db2fe25106025dcdbcc8c3b9133fe65515979f223d5c48de2 size: 3867
試行錯誤を繰り返していたので、ハマったポイントは無数にあるのですが、その中でも知識があれば大幅に時間を短縮できたポイントを挙げます。
(1) JavaScriptでjQueryをインポートしたのですが、herokuはhttpsでページを提供しているのにjQueryのライブラリをhttpで参照していて、
Mixed Content: The page at 'https://sparkle-sudoku-solver.herokuapp.com/' was loaded over HTTPS, but requested an insecure script 'http://ajax.googleapis.com/ajax/libs/jquery/1.8.1/jquery.min.js'. This request has been blocked; the content must be served over HTTPS.
というエラーが発生していましたが、なかなか気づけませんでした(サーバーの不具合だと思っていました)。参考: teratailの質問
(2) herokuの仕様で、開くポートは80番ではなく、heroku側で動的に決定され環境変数$PORTに渡されるのですが、これをどうやってApacheサーバーに渡せばよいかわからず苦労しました。そもそも何を満たすべきだったかというと、
の2点を満たす必要がありました。これを満たすために、httpd.confの設定はDockerfileの内部では行わず、最後にCMD文で実行されるスクリプト(start-server.sh)でhttpd.confの設定を行う、という形にしました。この形にすると、ローカルでのテストもやりやすくなります。(docker-compose.ymlの中でenvironment: PORT=80と設定すれば良いため)
参考: Container Registry and Runtime | Heroku Dev Center (公式ドキュメント)
(3) Dockerfileの設定について
途中まで、Dockerfileにいきなりコマンドを書いてトライ&エラーを繰り返す、というやり方で開発していたのですが、これは非効率的でした。試行錯誤する場合は、ベースイメージを起動して内部でシェルを起動し、その中で試行錯誤を繰り返すほうが効率的です。参考: 効率的に安全な Dockerfile を作るには - Qiita
この記事は、Competitive Programming Advent Calendar 2016 - Adventarの15日目の記事です。
去年(2015年)の12月ごろ、「セグメント木が任意のモノイドに対して使えるという(当たり前のことが)明示的に書かれた日本語の記事がないなぁ」と思い、「(当時)来年のAdvent Calendarあたりに書こうか」と思ったので書きました。その後調べてみましたが、どうやらこの1年(2015年12月-2016年12月)で割と書かれたようでした。(この記事の意味とは…)
前述のように多数の記事がこの1年間で出たので、この記事は主にそれらへのリンクを貼り、場合によってコードを紹介することにします。
集合M、Mの要素eとその上の二項演算*があり、*が
が成立する場合、(M, e, *)はモノイドであるという。
モノイド(M, e, *)に対して、セグメント木というデータ構造で、Mの元からなる配列を表現できる。このデータ構造は構築がO(n)ででき、1要素の更新と区間に対する*の演算(区間和*2 )がO(log(n) )でできる。(nは配列の長さ)
詳しくはここをみてください:
qiita.com
qiita.com
(先頭からの累積和を計算するだけなら可換モノイド(= アーベル群 - 逆元 = モノイド + 可換律)でよい)
セグメント木と同じく構築O(n)、1要素の更新と区間和がO(log(n))でできる。
アーベル群の上の累積和を使う問題: 蟻本をみてください。その他自分が解いた問題の中で:
C: データ構造 - AtCoder Regular Contest 033 | AtCoder
C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder
No.449 ゆきこーだーの雨と雪 (4) - yukicoder
データ構造と代数(後編) · tomcatowl's blogに詳しく書いてあるので、参照されたい。
バグっているのしかないので掲載できません…(>_<)
集合Aとその上の二項演算/\があり、それが
を満たす場合、(A, /\)は交叉半束であるという。
交叉半束については、SparseTableというデータ構造をつかって、構築O(n * log(n)), 区間クエリO(1)で計算ができる。(更新は無理)
割と内容が被っている+丁寧な記事。みなさん読むべし。
tomcatowl.github.io
tomcatowl.github.io
(2016/12/16 16:50追記)
翌日は古寺いろは@競プロ応援アカウントさんのAtCoderに毎回参加したくなる仕組みと、@ainu7さんの記事です。
時系列順に書いていきます。
11:10頃到着した。知り合いが結構いた。
本戦は3時間(12:30 - 15:30)であった。4完(A,B,C,D)2半(E,H)の計2,700点(54位)でパーカーを取得した。以下簡単に時系列順にコンテストの進め方を書く:
11/28追記: 提出一覧
11/28追記: 終了後に高校で同期だったyurahunaに遭遇した。高校の同期であったことはこの時初めて知った。東京に来た地元の人間は相当稀なので嬉しかった。
今年の夕食はケータリングだった。*4
自由時間は割と暇を持て余しがちだった。将棋AIのトークを聞きに行って、そのあと学科同期の人たち*5で集まってボドゲで遊んだ。
Exhibition直前に太鼓の達人をminus3thetaと一緒にやった。曲は知らなかったのでminusに選んでもらった(マリオワールドのむずかしいだった)。一応合格できたが疲労で死ぬかと思った。minusがうまかった*6。
強い人が強いことをやっているなぁという印象だった。色々思うところがあり*7、それとなく聞き流しながら一人でfinalの復習をやっていた。
チームリレーの顔合わせ、自己紹介をやった。私たちはTeam Dで、海外勢はFatalEagleで、日本勢はHuziwara, kobae964, siotouto, ei1333, beet, dolicas, zeptometer, ioryz, haradukaの9人だった。
英語の練習をするためにFatalEagleに話しかけようとするも、緊張のあまりろくに話せないという事態になってしまった。
イベントが終わって全員帰宅かホテルに向かうという形になった。今年はホテルがバラバラなようで、ホテルへのバスは出ず自分で歩いていかなければならなかった。*8
3回戦まで行くも敗退。
筋力: 17ptくらいしかとれなかった。前屈+10cm, ジャンプ36cm*11, 握力36kgf, 背筋120kgf。
LT: chokudaiがハンドスプリングをやっていて強かった。
まず、11問の問題に対して10人のメンバーなので、2問解く人間を決めなければならなかった。スタッフの方から「チーム内でチーム内順位3位以下の人」が2問解くという説明を受けたので、チーム内順位3位の私が2問解くことにした。
次に、10人のメンバーを3つのクラスタに分け、それぞれのクラスタに問題を割り当てた。*12 割り当ては以下の通り:
チーム内全員の動きを把握していたわけではないので、細かい動きは分からないが、私たちのチームは非常によく戦い、2位になった。
私の動きは以下の通り:
11/28追記: スコアボード
私がIを通してチームが2位になった直後、カメラマンがインタビューに来た。なぜか私が感想を聞かれることになったが、緊張のあまり(日本語なのに!!)ろくに聞き取れず返答もままならない、という醜態を晒すことになった。
テンションが上がりまくっていて、極度の疲労状態になり、足腰もガタガタという状態が全完後1時間くらい続いた。FatalEagleが他の(全完した)チームの人と話したいと言ってきたので、スタッフの人に尋ねてみた。*17 またFatalEagleに「この"3y3s"の意味わかる?」と聞いたら、「"eyes"のことで、問題番号の"I"とかけているのでは」という答えをもらった。*18
1位のチーム(50分程度で全完した)が表彰されているのを見てすごいなぁと思っていたら、2位のチームも表彰される*19ということになって、足腰ガタガタのまま壇上に上がった。Best Collaborator Awardのマグカップをもらったが、手が痺れて落とす危険性が高かったので後ろの人に持ってもらった。もしかしたらまたインタビューされるかもしれないと思って何を言うか少しだけ考えたが、その予感は的中してしまい、感想を言うことになってしまった。qnighyへの対抗意識からせっかくの機会なので英語で以下のようなスピーチをした(文法的にヤバい場所は赤で、可能な改善点は青でハイライトしている):
EVERY ONE of our team worked very well*20, and our team worked quite well together*21. I couldn't be prouder to*22 compete and enjoy with every other people*23 in this*24 team.
翻訳:
「チームメイトのどの一人も全力で戦ってくれ、私たちのチームは共に非常によく戦いました。同じチームで共に戦い楽しめえたことを、この上なく誇りに思います。」 #CODE_FESTIVAL
— こば(競プロのプロを目指す) (@kobae964) November 27, 2016
(通訳の方、駄文で本当に失礼しました…。)
そのあとはいよいよ足腰がやばくなって来たので座ったりした。
上に書いた通りである。
学科同期とセイクで優勝した
11/28追記: そのあと汐留駅のイルミネーションを見た。雨だったのが残念だが、こういうところに恋人と行くとロマンティックなんだろうなぁなどということをぼんやりと考えていた。
とても楽しかった。特に問題を早く解くことは苦手なので、朝プロは良い練習になった。また英語で話すのも苦手*25なので、練習の機会としても絶好の機会であった。
関係者の皆さん、本当にありがとうございました!!!
*1:[現在の移動の数]に加えて、[今まで見た頂点の数] -> [今まで見た頂点の数][番号最大の頂点から戻れる頂点番号の最小値] -> [今まで見た頂点の数][頂点1に戻る道のある頂点の番号の最大値] という順番で考察した。最後のは正解
*2:自分の実装力の低さ、Gと戯れていたことに対する後悔などで精神がズタボロになっていた。
*3:事前に順位表を見てqnighyがE,Fを通していたのは知っていたので、Fを通して勝ちたいと思ったが、間に合わなかった。
*4:去年はチケットと自分の好きな食事を交換する形式だった。遅く行っても(選ばなければ)食事は残っているだろうと思って遅めに行ったら、そもそも食事が残っていなくて辛い思いをした。
*5:kw_udon, zptmtr,minus3theta
*6:確か200,000 < 私のスコア < 230,000 < 270,000 < minusのスコアだったと記憶している
*7:この時点ではまだfinalの結果が思わしくなかったことについての傷が癒えていなかった。
*8:一概に悪いとも言えなくて、ホテルから会場に向かうのにバスを使う必要がなく、寝坊してもある程度はカバーできる。
*9:ceil(x/2) / pはエスパーしようと思えばできる。
*10:あとで周囲に聞いたら、期待値の線型性などを使うと簡単に答えが導出できるということが分かった。
*11:モヤシなので体力がなく、とくにジャンプ力が弱い
*12:去年の私のチームのやり方と同じである。
*13:11/28追記:よく考えて見ると、少し詰まって5分くらいかかったので、「即」ではなかった。
*14:3行ごとに1行全て埋める + 周囲を埋める
*15:n=2kのケースはn=kのケースに帰着できる。11/28追記:zeptometerらが思いついた気がするが、記憶がはっきりしない(すみません…)。
*16:n=4の時はad-hocにつくる。
*17:OKだが、解法を話すのはやめてほしいということだった。
*18:実はこれは某音ゲー由来だということを、帰宅してから知った。
*19:Best Collaborator Award
*20:考え直したらhardの方がそれっぽい
*21:acting as oneなどという表現も使いたい
*22:proud to Vは〇〇できる(現在)ことを誇りに思うので、"prouder to have competed and enjoyed"の方が良さそう、だけど話している間にそんなことを考えるのは無理
*23:all the other membersなどがよい
*24:ourの方がよいかなぁ
*25:他人より苦手とは言ってない、残念ながらこれでもかなりマシな方らしい