読者です 読者をやめる 読者になる 読者になる

Rustでtreapと2-3 treeを実装してブログを書きました

Rustでtreapと2-3 treeを実装してブログを書きました。

treap: Treap on Rust - Codeforces

2-3 tree: 2-3 tree on Rust - Codeforces

(Codeforcesなので英語です)

機械学習初心者がIndeedの機械学習コンテストに参加した話

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行下に表示)もほとんど変化がないという結果になっています。
f:id:koba-e964:20170413132437p:plain

反省

もう少し勉強が必要でした。まだ原因究明ができていないので、他の人のコードを実行したりしながら勉強します。

lighttpd(ライティー)で数独サーバーを作った話

tl;dr: Apacheで数独サーバーを作った話 - koba-e964の日記の続きです。

きっかけ

前回(Apacheで数独サーバーを作った話 - koba-e964の日記)の制作途中でいただいた以下のようなコメントがきっかけで、lighttpdでも作ってみることにしました。


完成品は変わらず
https://sparkle-sudoku-solver.herokuapp.com/
にあります。

概要

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

ハマったポイント

  • 起動スクリプト(start-lighttpd.sh)を/tmp/以下において、CMDで実行しようとしたら、手元では動くもののheroku上では動かないという事態になりました。これはおそらく、docker imageのビルド時に見える/tmp/とheroku上で書き込みできる/tmp/が異なる場所を指しているためだと思われます。(herokuは一時ファイル保存のため、/tmp/以下にのみファイルの書き込みを許しています。 *1 参考: Stack Overflowの質問)
    結局起動スクリプトを/tmp/ではなく/opt/に配置することにして解決しました。
  • Dockerfileの仕様で、Dockerfileの配置してあるディレクトリの外のファイルは参照できないのですが*2、この仕様のせいでサーバーごとにディレクトリを分割することと共通のファイルを再利用することが両立できませんでした。ここではDockerfile.*という名前のファイルにdocker scriptを書き、docker-compose.ymlでサーバーごとに参照するDockerfileを変えることにしました。なおこの方法だとheroku container:pushができない(Dockerfileという名前のファイルを参照するため)ので、push用のスクリプトpush-lighttpd.shを用意することにしました。*3

今後やりたいこと

  • lighttpd版で使うLinux distributionを特に何も考えずUbuntuにしましたが、他のdistributionだとどのくらい軽量化できるのかが気になります。またApache版はDebianだったので、Debianでもやってみて公正な比較をしてみたいと思っています。
  • 前回の「今後やりたいこと」はまだできていないので、それらにも取り組みたいと思っています。

*1:heroku上のファイルシステムはephemeralなので、一度作ったテンポラリファイルがずっと残っていることを前提にプログラミングをしてはいけません。(dynoが停止または再起動するタイミングで消えます。) またファイルシステムはdynoごとに作られるので、/tmp/を介して別のdynoと通信をすることはできません。参考: 公式Herokuで一時ファイル保存 - 木木木

*2:GitHubのissueで議論がされているので、興味があったら是非読んでみてください。

*3:DockerfileをDockerfile.lighttpdへのsymbolic linkにして、herokuの目を欺くやり方です。こんな小手先の対策とりたくなかったです…

Apacheで数独サーバーを作った話

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) JavaScriptjQueryをインポートしたのですが、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サーバーに渡せばよいかわからず苦労しました。そもそも何を満たすべきだったかというと、

  1. Dockerfile内のCMD文の直前までは、$PORTに依存せずにビルド可能である
  2. CMD文で実行されるファイルは、$PORTを受け取って$PORT番で指定されたポートをlistenすることができる

の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

今後やりたいこと

  • いずれ画像認識の機能もつけることを目標にしています。数独パズルの盤面を撮影した写真を読み込めるようにする機能をつけたいと思っています。
  • パフォーマンスの測定をまだ実装していないので、測定機能をつけようと思っています。また、minisatのconflictやpropagationの回数で数独パズルの難易度を測れそうなので、これらのパラメータも表示するようにしたいです。
  • 数独はCNFへの変換が比較的容易なので、今後はカックロなどの、よりCNFへの変換が難しい問題のWebソルバーを作ることも目標です。

*1:解が存在しない場合の挙動は未定義です。いずれ直したい…

*2:最初はnginxとか使おうとしてたんですがCGIを動かすのが大変すぎて数時間溶かしたのでやめました。

データ構造と代数構造

この記事は、Competitive Programming Advent Calendar 2016 - Adventarの15日目の記事です。

この記事について

去年(2015年)の12月ごろ、「セグメント木が任意のモノイドに対して使えるという(当たり前のことが)明示的に書かれた日本語の記事がないなぁ」と思い、「(当時)来年のAdvent Calendarあたりに書こうか」と思ったので書きました。その後調べてみましたが、どうやらこの1年(2015年12月-2016年12月)で割と書かれたようでした。(この記事の意味とは…)
前述のように多数の記事がこの1年間で出たので、この記事は主にそれらへのリンクを貼り、場合によってコードを紹介することにします。

データ構造と代数構造

セグメント木 <=> モノイド

集合M、Mの要素eとその上の二項演算*があり、*が

  • e * x = x * e = x *1
  • x * (y * z) = (x * y) * z

が成立する場合、(M, e, *)はモノイドであるという。
モノイド(M, e, *)に対して、セグメント木というデータ構造で、Mの元からなる配列を表現できる。このデータ構造は構築がO(n)ででき、1要素の更新と区間に対する*の演算(区間*2 )がO(log(n) )でできる。(nは配列の長さ)
詳しくはここをみてください:
qiita.com
qiita.com

BIT <=> アーベル群

(先頭からの累積和を計算するだけなら可換モノイド(= アーベル群 - 逆元 = モノイド + 可換律)でよい)
セグメント木と同じく構築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に詳しく書いてあるので、参照されたい。

サンプルコード

バグっているのしかないので掲載できません…(>_<)

SparseTable <=> 交叉半束(meet-semilattice)

集合Aとその上の二項演算/\があり、それが

  • idempotency (べき等律) a /\ a = a
  • commutativity (可換律) a /\ b = b /\ a
  • associativity (結合律) a /\ (b /\ c) = (a /\ b) /\ c

を満たす場合、(A, /\)は交叉半束であるという。

交叉半束については、SparseTableというデータ構造をつかって、構築O(n * log(n)), 区間クエリO(1)で計算ができる。(更新は無理)

ダイクストラ法 <=> closed semiring (若干おまけ)

ダイクストラ法がsemiring (R ∪ {∞}, min, +, ∞, 0) *3のsemiring構造の上で成り立っているアルゴリズムであることはよく知られている。これを一般化し、closed semiringというクラスに含まれる任意のsemiringで似たようなことができるらしい。("closed"というのは、ダイクストラ法の中で要請される色々な要請を満たす取り扱いやすい性質のことである。) 詳しくは(Mohri, 2002)を参照されたい。

参考

割と内容が被っている+丁寧な記事。みなさん読むべし。
tomcatowl.github.io
tomcatowl.github.io

(2016/12/16 16:50追記)
翌日は古寺いろは@競プロ応援アカウントさんのAtCoderに毎回参加したくなる仕組みと、@ainu7さんの記事です。

*1:2016/12/15 1:39修正:e -> x,単純な誤り

*2:本来は可換でない演算に「和」という表現を使うのは望ましくないのですが、以下で紹介するBITにおける語法と整合させるため「区間和」と呼んでいます

*3:このsemiringにはTropical Semiringという名前が付いている。

CODE FESTIVAL 2016 参加記

時系列順に書いていきます。

1日目

到着

11:10頃到着した。知り合いが結構いた。

本戦

本戦は3時間(12:30 - 15:30)であった。4完(A,B,C,D)2半(E,H)の計2,700点(54位)でパーカーを取得した。以下簡単に時系列順にコンテストの進め方を書く:

  • 0h00m - 0h30m (12:30 - 13:00)
    A,B,C,D問題を解いた。(+1500)
  • 0h30m - 1h00m (13:00 - 13:30)
    最初の15分でEの部分点を通し(+500)、残り15分で満点解法を考えていた。それでもわからなかったので後回しにして、別の解ける問題を探すことにした。
  • 1h00m - 1h40m (13:30 - 14:10)
    Hを考察し、部分点を手に入れた(+700)。
  • 1h40m - 2h10m (14:10 - 14:40)
    Gが解けそうだったので解こうとした。自明な解法(queueに枝を突っ込んでKruskal)をやってみたがTLEなどで落ちたので断念した。
  • 2h10m - 3h00m (14:40 - 15:30)
    Eの満点やFを解こうとした。Fの考察について、dpでやりそうだということは分かったが、indexについてかなり長い時間試行錯誤*1を繰り返したので、時間がかなり取られてしまった。正解が分かった時点では残り時間が10分程度しかなく、そこからバグなく実装することができなかったため、Fは正解できずに終わった。*2 *3

11/28追記: 提出一覧f:id:koba-e964:20161128130513j:plain

11/28追記: 終了後に高校で同期だったyurahunaに遭遇した。高校の同期であったことはこの時初めて知った。東京に来た地元の人間は相当稀なので嬉しかった。

夕食・自由時間

今年の夕食はケータリングだった。*4

自由時間は割と暇を持て余しがちだった。将棋AIのトークを聞きに行って、そのあと学科同期の人たち*5で集まってボドゲで遊んだ。

Exhibition直前に太鼓の達人をminus3thetaと一緒にやった。曲は知らなかったのでminusに選んでもらった(マリオワールドのむずかしいだった)。一応合格できたが疲労で死ぬかと思った。minusがうまかった*6

Exhibition

強い人が強いことをやっているなぁという印象だった。色々思うところがあり*7、それとなく聞き流しながら一人でfinalの復習をやっていた。

Team Relay (Introduction)

チームリレーの顔合わせ、自己紹介をやった。私たちはTeam Dで、海外勢はFatalEagleで、日本勢はHuziwara, kobae964, siotouto, ei1333, beet, dolicas, zeptometer, ioryz, haradukaの9人だった。
英語の練習をするためにFatalEagleに話しかけようとするも、緊張のあまりろくに話せないという事態になってしまった。

宿泊

イベントが終わって全員帰宅かホテルに向かうという形になった。今年はホテルがバラバラなようで、ホテルへのバスは出ず自分で歩いていかなければならなかった。*8

2日目

朝プロ (Elimination Tournament)

3回戦まで行くも敗退。

  • 1回目 (group11)
    A 500, B 100の計600点で通過。
  • 2回目 (group11 + group12 -> group06)
    A 700, B 200の計900点で通過。Aはよくわからなかったがサンプルケースからエスパーして通った*9ので一人で爆笑していた。*10
  • 3回目 (group05 + group06 -> group3)
    A 200, B 400の計600点で脱落。通過したかったらAは700点取る必要があった。

また自由時間

筋力: 17ptくらいしかとれなかった。前屈+10cm, ジャンプ36cm*11, 握力36kgf, 背筋120kgf。
LT: chokudaiがハンドスプリングをやっていて強かった。

Team Relay

作戦タイム

まず、11問の問題に対して10人のメンバーなので、2問解く人間を決めなければならなかった。スタッフの方から「チーム内でチーム内順位3位以下の人」が2問解くという説明を受けたので、チーム内順位3位の私が2問解くことにした。
次に、10人のメンバーを3つのクラスタに分け、それぞれのクラスタに問題を割り当てた。*12 割り当ては以下の通り:

  • A,B,C,D,E
    dolicas, zeptometer, ioryz, haraduka, kobae964
  • F,G,H
    siotouto, ei1333, beet
  • I,J,K
    FatalEagle, Huziwara, kobae964
本番

チーム内全員の動きを把握していたわけではないので、細かい動きは分からないが、私たちのチームは非常によく戦い、2位になった。
私の動きは以下の通り:

  • 最初
    Eを読んで即*13解法を思いつき、haradukaがAを解き終わった直後に実装してEを通した(07m04s)。
  • 中盤
    Iをやることにして、簡単な解法を思いついたので行ったものの、コーディングスペースで間違いに気づき、WAをもらった(nが奇数の時にしかうまくいかない解法だった)。11/28追記: FatalEagleがJ問題の解法を思いつき、そのアイデア*14の素晴らしさに感服した。またHuziwaraFatalEagleがK問題を頑張って考察していたが、私はこの手の問題が苦手で全く貢献できなかった。
  • 後半
    他の人のアイデア*15を使って、n=2のときはダメで、それ以外のnについて具体的に解を構成する方法を見出した。*16 焦っている中でのdfs解法なので実装に手こずりそうだった(し実際にWAも3回出した)が、Huziwaraによる的確なデバッグにより見事AC(71m27s)して2位になった。

11/28追記: スコアボードf:id:koba-e964:20161128130145j:plain

インタビュー

私がIを通してチームが2位になった直後、カメラマンがインタビューに来た。なぜか私が感想を聞かれることになったが、緊張のあまり(日本語なのに!!)ろくに聞き取れず返答もままならない、という醜態を晒すことになった。

aftermath

テンションが上がりまくっていて、極度の疲労状態になり、足腰もガタガタという状態が全完後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.

翻訳:

(通訳の方、駄文で本当に失礼しました…。)
そのあとはいよいよ足腰がやばくなって来たので座ったりした。

Team Relay 総括

上に書いた通りである。

帰路

学科同期とセイクで優勝した
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:他人より苦手とは言ってない、残念ながらこれでもかなりマシな方らしい

CODE THANKS FESTIVAL 2014(A日程) 参加記

当時(2014/12/7)に書いたまま下書きに残っていたので、今更&未完成気味ですが一応公開しておきます。

---------------------------
2014/12/7のCODE THANKS FESTIVAL 2014 A日程に参加してきました。

問題の感想

A カメツル算

4 * a + 2 * b。 やるだけ。

B バッジ

機械A, B, Cを生産能力の高い順に並べ替えて順番に使うだけ…なんですが、割と「並べ替える」ところではまる人がいた印象があります。
自前で条件分岐を使いまくって並べ替えを行うと時間がかかりまくってバグの原因にもなるので、必ず標準ライブラリのソートを使いましょう。
(C++なら<algorithm>をインクルードして

int a[3];
/*a に値を入れる */
std::sort(a, a+3); /* a[0]から小さい順になる */
std::reverse(a, a+3); /* a[0]から大きい順になる */

でできます。
)

C コンテスト

やるだけ。1-indexedであることに注意しましょう。

D 定期券

やるだけですが普通にやると条件分岐が面倒です。解説でもあったように共通部分を引くと良いでしょう。

E 儀式

i番目だけをやり忘れた時の結果を計算することを考えます。いちいち(n-1)回シミュレーションをやると時間がかかるので、操作が可換(どの順でやっても結果が同じ)であることを利用して、最終結果にi番目の操作の逆の操作を行いましょう。

F 順位表

参加者を頂点としたグラフに「順位の低い方から高い方へ向く辺を設ける」ということをすべての大小関係に対して行います。そのようにしてできた有向グラフにおいて、1から辺をたどって到達できる頂点数を数えればよいです。詳しくは解説を参照。

G 通勤電車と気分

部分点解法(n <= 10)は各乗客に対して2パターンをどちらも試せばできます(O(2^n)-時間)。この部分点解法を狙うときは、例えばn>=15のときにexit(1);などを行うと良いでしょう。
満点解法を書くには空き座席のパターンをつかむ必要があります。席に誰かが座っている状態を1、そうでない状態を0をするときに、余中の状態は
111...11101010101...0100000
というようになることを利用します。

H 模様替え

感想

本選2日目に予定が入ってしまい参加できなくて残念だったのですが、今回この様な機会をいただくことができてありがたく思っています。
B日程には(すでに予定が入っているので)参加しません。