恋声の声質変換と同じことを macOS でやるメモ
tl;dr
GarageBand の VocalTransformer でピッチとフォルマントを調整する。Pitch +12, Formant +3 が恋声の M -> F 標準設定だと思う。
discord などにつなぐには Soundflower を使う。
ICFPC 2018: Team manarimo
昨日までの3日間、例年通り ICFP Programming Contest にいつものチームで出た。今年のチーム名は manarimo。
公式サイト: ICFP Programming Contest 2018
成果物 (github)
今年はメンバーの1人である osa_k がアメリカで出稼ぎ労働者をしていることから、日本の5人と osa_k は Goole Hangouts で会話しながら作業していた。
-n日目
チーム結成
昨年に引き続き同じ6人チーム。
osa_k, y3eadgbe, kawatea, mkut, yuusti, pepsin_amylase
会場選定
去年は越後湯沢のスキー客向けリゾートマンションを airbnb で確保したけど周辺施設がなにもない上にインターネットが貧弱*1で、温泉以外はいまいちだった。この経験を踏まえ、今年は利便性が高いところがいいという話をしていた。
y3eadgbe が社会性を発揮してオフィスマネージャーと交渉し、コンテスト期間中に勤務先の一番大きい会議室が独占的に使用できることとなった。
-1日目, 0日目
勤務先でハッカソンが行われたので睡眠調整を兼ねて徹夜。ハッカソンに飽きたチームメンバーと一緒にクソなぞなぞを解いていた。
72問目を解いているときに、誰かが答えを思い浮かばず「マナリモって藻、存在しそうじゃない？」と苦し紛れに言ったのを聞いたぼくが即興ででたらめな設定*2を付け加えたところ結構ウケて、あとでチーム名として採用することとなった。
1日目
チームメイトが問題を読んでいる間に回答の提出方法を読んで submit.py を実装。公式の dfltTracersL.zip をそのまま提出してテストしようとするも、コンテスト開始3時間までは提出できずに怒られたりした。
submit.py のテストを済ませたあと、生成した回答などを管理する web アプリを立てることにした。
ナナチ
熟慮の末今年の ICFPC ではメイドインアビスからツール名を取ることにし、管理アプリをナナチと命名。2015年に書いた響のコードをコピペして必要な改修を加えていった*3。
energy の計算をやっている公式ツールの再利用を試みたがブラウザから剥がすのは難しそうだった（ICFPC2018あるある）ので、公式ツールを手で実行させたときに得た結果を JavaScript で抜き出してナナチに生やしたエンドポイントを通じて MySQL に突っ込むという仕組みを考案し、osa_k と分業してこれを実装した。
ナナチに登録したデータがすぐに反映されないという問題が発生。どうも MySQL の Isolation Level が REPEATABLE READ であることに起因しているっぽく、いたるところで commit して強引に解決するなどした。
2日目, 3日目
Lightning が終了したので一旦帰って寝た。休んでいる間に既存の Trace を後処理で改善するというアイデアを得たのでこれをやることにした。
ミーティ
既存のファイルはすべてバイナリの .nbt ファイルで保存していたので、後処理器に食わせるためにチーム内で使用しているアセンブラフォーマットに戻すツールを書いた。ミーティと命名。これは他にも壊れた nbt ファイルを生成した他のソルバーのデバッグに役立った。
ナナチ炎上
Lightning が終わった頃からナナチが頻繁に死ぬようになる。osa_k が jenkins を使ってすべての問題に対してソルバーをぶん回してナナチに提出する機能を作ったのだが、これを使うと何問か提出したところでナナチが止まってしまう。
一応再起動すると治るので、死ぬたびに再起動で生き返らせていた。こっちの名前をミーティにしておけばよかったと少し後悔する。
osa_k を消耗させることにより、コネクションプールを使ってないことやらナナチのプロセス数が足りないことやらどうも nbt ファイルをバイナリブロブとして突っ込んでいることやらが怪しいのではないかとなり、治してもらった。
ウェブアプリの負荷耐性を上げるという事実上の ISUCON をすることになったのでちょっと面白かった。これは2015年のチームの反省会の話題に出た（らしい）のだけど、ICFPC で使うインフラは意外と負荷がかかるので、動けばいいという気持ちでやるのはあんまりよくないっぽい。
ボンドルド
後処理器その1にボンドルドと命名。命令を1つ前のwaitと交換するのを貪欲に繰り返し、すべてがwaitだけになったターンをスキップすることで圧縮を図る。だいたい数%から10%ほどの energy 節約効果があった。
yuusti のハローワークや mkut のスプラシューターコラボ、kawatea のシヴァと組み合わせてハロワボンドルド・スシコラボンドルド・シヴァ神ボンドルドというソルバーにするなどしてチームの成果物に組み込まれた。
プルシュカ
ボンドルドは一定の成功を収めたものの、生成された出力を見ると順番を入れ替えられないばかりに長々と待たされている状況があることに気がついた。
そこで、本当に入れ替えてはいけない依存関係と同時に実行しなければならない依存関係を解析して DAG を生成し、ここから適切に命令列をつまんでいくという賢しらかつ ICFP っぽい手法を考案した。プルシュカと命名。
入力の命令列は harmonics やら volatile check が正しいという仮定を置くと、だいたい以下のような依存関係に気をつければいい気がしてくる:
同時実行制約
- グループで実行する命令: GFILL, GVOID, FUSIONP, FUSIONS
- 同時に実行される FILL / VOID
順序制約
- 別のターンに実行された FILL / VOID はその順序を保つ
- 同じボットの中では移動系 (SMOVE / LMOVE) と場所に依存した効果を持つ命令の間ではその順序を保つ（場所依存命令の場所を変化させないため）
- すべての命令はそのボットを生成した FISSION より後
- すべての命令は FUSIONS / HALT より先
FILL / VOID の同時・順序制約は harmonics チェックをサボるために入れた雑な条件。これを実装してボンドルドを過去にするぜ、と息巻くも実行すると途中でエリア外に出る命令を実行しようとしたり、実行できる命令がなくなったりしていまう不具合に遭遇した。
エリア外に入れるやつはどうも移動命令の順番を入れ替えるのが悪いっぽく、同じボット内での移動命令どうしに順序制約を入れると治ったが、最初の目論見である移動の大胆な最適化が予想以上に難しいことを示しており動揺した。
実行できる命令がなくなってしまうのは、よく調べてみるとどうもデッドロックらしいことが明らかになった。例えば、2つのボットがお互いの場所へ移動しようとする SMOVE 命令を構えている場合、どちらかを先に実行することはできない。分散処理の有名問題を踏み抜いてしまい、ICFPC らしさと絶望を感じた。
どちらかを邪魔にならない場所にどかすよう命令を追加するという雑な方法で回避するアルゴリズムを実装したが、これのバグは取り切れず、バグを踏まなくてもこれによって最適化の結果ターン数がかえって長くなってしまう現象などが発生し、この時点で完全に心が折れてプルシュカの方針は諦めることにした*4。
コンテストの残り時間はボンドルドの改良に費やしたり唯一神の訃報に驚いたりしていた。
感想
非ゼロの貢献ができてよかったけれど、ナナチはかなり負債を残して osa_k や y3eadgbe に苦労をかけたし、プルシュカは投入した時間に見合う成果ではなかったのが残念。
毎年 webapp をコピペしていることを考えると ICFPC 用 webapp ライブラリが作れるのではないかとちょっと思ったりした。
宿題
- プルシュカの方針は実現可能なのか。
特にデッドロックを依存グラフから検出できるか。移動命令の制約を保っているので各命令での場所はわかるはずだが、グラフに WAIT が現れないのでどうなんだという感じ。
AtCoder Grand Contest 022 C - Remainder Game を解くときに考えたこと
背景
こういう記事が出ました。で、ぼくが気になったのが、実際のところこの記事で言及されている問題（C - Remainder Game）を解くときに人々はどういう思考をするんだろう？ ということでした。多分他の人も気になっていると思うので、先ず隗より始めよということで自分が考えたことを書きます。無駄なこともいろいろ考えてて長くなりますが、おつきあいください。
筆者について
これを書いているとき AtCoder Rating 2302 です。700 点問題なら時間さえあればまあ解けるんですが、コンテスト中に確実に通せるかと言われると……というのが最近の実感です。
では始めます。
初手の決定
（典型っぽい要素から出てきたアイデアを太字で強調します）
1回のコストは 2^k ということからいかにもビットで考えてくださいという雰囲気を感じ取り、同じ k を2回以上使う必要がないならビット列の辞書順最小なるなあとまず思います。辞書順最小には文字を先頭から小さい順に試して可能かどうか判定するという典型があるので、これに落ちると嬉しいということを意識しました。
つぎに k を選んで操作するのを繰り返すという点ですが、これについては元記事にもあるように k の順序や回数に便利な制約をつけられると嬉しい気持ちになりました。コストの部分でも言ったように2回以上使わないという制約があるといい感じですし、順番についてもいい感じの制約をつけられないか考えることにしました。
操作列に関する考察
いきなり全体で考えると頭が爆発するので、ぼくがよくやるのは部分問題について考えることです。これが解けないと話にならないし、部分問題の考察結果が活用できることはよくあります。で、今回考えた部分問題が n = 1 かつ出力が -1 かどうかのみ判定するというやつで、これについては a / 2 より大きい k を選ぶことを考えると b が x / 2 未満であることが必要十分だとわかります。が、これだけではどうこうできる感じでもありません。
コストについても考えていきたいので、引き続き n = 1 で k の列の制約について考えます。n = 1 なので mod は必ず取るとしてよいことに留意しつつ、たとえば 2, 3, 2 の順でやることに意味はあるのか……と想像していくと、なんとなく同じやつは2回やっても無駄な感じがしますが、証明できる感じはしません。
（ここで結構考える）
具体例で色々計算しているうちに、小さい k で mod を取ったあとでそれよりと同じか大きい k を選んでも値は変化しないことに気が付きます*1 。すなわち、意味のある操作列は k_1 > k_2 > k_3 > ... を満たすということで、辞書順最小の典型に落ちることが分かりましたし、この結果を得たときにこの問題が解けそうだという感触を得ます。
判定問題
今までに考えてわかったことをまとめると、次のようなコードを書けばいいことになります。
- 各要素についてコスト無視で可能かどうか判定してダメなものがあれば -1 *2
- k として max(a) から 1 まで大きい順に、「それがないとダメか判定」して必要なら入れる
- 必要な k のコストの総和を出力
あとは「それがないとダメか判定」を詰めればいいわけです。
部分問題から考えて1個ずつ、k 未満を全部使っても b にはならないかどうか判定し、もしそうなら a を x % k で書き換えていけばいいかなと考えます。たとえば、次の入力
2
17 10
8 1
に対して、k = 9 は 17 に対して絶対必要なので使用します。
ここで気になったことが出てきて、ある k が必要だとわかったときにそれをほかの a の要素を書き換えるのに必要かどうかは定かではないということです。先程の例だと 10 を k = 9 で 1 に書き換えれば終わりですが、これの b_2 が 1 ではなく 2 だと書き換えないほうが得です。
書き換えてループを回す戦略がうまく行かなさそうなことがわかったのでこの方針を捨て、辞書順最小の典型で判定問題を書くときに利用できるすでに決定した列の情報を利用することを考えます。
n = 1 で k の操作列が与えられたときに a を b にできるか考えると、これは部分和問題の足し算を mod k に置き換えたものだと気がつき、同じような動的計画法を実装すればいいことがわかります *3。
実装
https://beta.atcoder.jp/contests/agc022/submissions/2408219
これをコードにすると上のようになり、これで AC です。a < b のケースを見落として 1 WA 食らいました……。
dp 関数が部分和問題を変形した動的計画法の部分で、ok 関数が判定問題の部分です。
最後に
他の人が解いた過程も知りたいので他の人も書いてください！！！
他の人
AGC022 とか reminder game atcoder でググって出てきた皆さんです。判定問題の部分で解説にあるようなグラフ構築でやってる人が多いです。
(22:08 追加) 各操作が最大1回ってのが見えるの速くてビビる あとぼくも時間計っておけばよかった
項目応答理論を用いた音楽ゲームの譜面難易度推定における一次元性の確認
導入
心理学的な量を測定するための理論の1つである項目応答理論においては、（多次元拡張されていなければ）応答が一次元性を持つこと、すなわち測定しているただ1つの量のみによって応答が説明できることを仮定しています。例えば TOEFL は項目応答理論を用いて語学力という心理量を測定する試験ですが、すべての問題について、それが解けるかどうかは各人が持つ語学力によって決まっているという仮定をおいていることになります。
項目応答理論の応用としては、語学力の他にも音ゲーの譜面難易度推定というものがあります*1。こちらにおける一次元性はどうでしょう、地力という心理量があってそれを測定していると考えてもよいのでしょうか。SOUND VOLTEX なら地力はつまみ力・鍵盤力・片手力などの要素に分解して議論することが一般的です。IIDX 出身のプレイヤーが14 *2 が半分も埋まらないうちにあっさり大宇宙ステージ [EXH] をクリアするなど、一次元性に反しそうな例も知られています。ボルテの応答は先に挙げた要素からなる多次元量によって説明するほうがよいという考え方もありえます。果たしてボルテのデータセットに一次元の項目応答理論をそのまま適用するのは妥当なのか、検討しました。
手法
プレイデータに対して主成分分析を行い、それぞれの主成分の解釈を行いました。
SDVX III のスコアツールに登録されているデータのうち twitter 上で収集できたものをもちいました (プレイヤー数 2375) 。このデータ上でクリアレート *3 が 95% 以下の 351 譜面を対象として、プレイヤーが譜面を通常ゲージでクリアしていれば 1、そうでなければ 0 とした反応行列を生成しました。プレイヤーをデータ点とし、各譜面のクリア反応が説明変数です。
このデータをもちいて、各譜面のクリア反応のペアの相関を求めて相関行列とし、これの固有ベクトルを計算しました。
結果
寄与率（各固有値の固有値の総和に対する割合）は次のとおりです。
寄与率が低い順にソートしています。とても偏っていることがお分かりいただけるかと思います。
こちらが上位 5 成分について拡大したものです。第1主成分だけで 0.5 以上ありますし、この 5 つの寄与率の和は 0.722 にもなります。
各プレイヤーの第1主成分得点を横軸に、第2主成分得点を縦軸に取った散布図は次のようになります。
なんだかものすごくきれいな曲線が見えます。
同様に、縦軸を第3主成分得点や第4主成分得点に置き換えると次のようになります。
ここにもきれいな曲線が見えます。
また、各種成分ベクトルの要素は、第1主成分については全て正、それ以外は正の要素と負の要素がだいたい半々でした。
議論
寄与率のグラフを見ると、全体の分散のほとんどは少数の主成分で説明できることがわかります。特に、第1主成分の寄与率が0.5を超えており、これだけでも一次元性が成り立っていると言ってもいいかもしれません。
しかも、この第1主成分はただひとつ要素が全て正です。これはクリア力の主成分であると解釈できます。
より興味深いのは主成分得点です。主要主成分の方向に射影するととてもきれいな曲線が出てきます。この現象を説明する1つの仮説を以下に説明します。
簡単のため、レベル14・レベル15・レベル16の3譜面からなるデータセットで同様の実験をしたと考えます。これらの譜面の難易度には十分な一次元性があるとすると、データ点の分布は次のようになるはずです。
ここに主成分、つまり分散が大きくなる方向を書き加えると、
こうなります。これは第1・第2主成分得点の散布図に近い感じがします。第3主成分は、15と16の軸を取り替えて *4、
こんな感じになっている気がします。
結論
主成分分析を行うことにより、寄与率 0.5 を持ち、しかも地力と解釈できる主成分を得ました。第2主成分以下についても、一次元性を仮定すれば難易度を別の形で表現したものであるとして説明できる可能性を示しました。SOUND VOLTEX のクリアデータは一次元性を仮定して解析してもよさそうです。
今後の課題
- 他の反応（ハードクリア、UC *5 など）での一次元性
- 他のゲームに置ける一次元性
- 譜面属性は経験的には明らか。今回はノイズとの分離に失敗しただけかもしれない。一般的に考えられている属性が偏った譜面だけをデータセットに集めたら主成分にそれが現れるかも *6
- 「仮説」は主成分得点の散布図が特定の曲線上以外にも点を持つことを完全には説明できていない。
ISUCON6: Team イーグルジャンプ
ISUCON6 の予選に ICFPC のときのチームのサブセット (osa_k, mkut) で出ていました。
予選大敗北で、個人的にはデータに基づかずに適当に改善していっていた & ログ解析環境の準備を軽視した結果ボトルネック (クソデカ正規表現) に取り組むのがとても遅くなったのが敗因だと思っています。来年参加する人や実務で高速化する人は気をつけようね！
以下、チーム Slack で展開されたイーグルジャンプの心温まる会話集です（チーム名に合わせたアイコンを使ってるうちに気分がノッてきてなりきりをやっていました）。
イーグルジャンプの日常
今までなりきりをやるのは頭のネジが足りない人だと思っていたのですが、いざやってみるとあたかも自分が美少女になったような気分になり、やってる人の気持ちがわかりました。 みんなもやりましょう。
デプロイは osa_k 謹製 hubot aoba によって自動化されていましたが、本番時にうまく動かなかったのが残念。
いやあ素敵な会社だなあ、おっとこんなところに Javascript のコードがあるぞ、実行してみよう……？
ところがどっこいっ... 現実ですっ...これが現実っ…！
ICFPC 2016: Team 天羽々斬
EDIT 2016/9/22: !!! 最終順位も2位でした !!! やったぜ
ICFPC 2016 に出ていました。ランキング凍結時点で2位でした。優勝してるといいな〜、1位は凍結前で我々の3倍だったり1問を除いて全問解いたりしてますが。
ICFP Programming Contest お疲れ様でした。Unagi は残念ながら 1 問だけ残して完全試合達成ならず。。。 #icfpc2016 pic.twitter.com/LxLXMEqDnz
— Takuya Akiba (@iwiwi) 2016年8月8日
ぼくは基本的にはアルゴリズムを考えて実装する係でした。この記事では自分のやったことについて書きます。インフラ周りについては @osa_k がきっと何か書いてくれると思います。
EDIT 2016/8/12: @osa_k が書いてくれました。さすが！
問題: http://icfpc2016.blogspot.jp/2016/08/task-description.html
凍結前のランキング: http://2016sv.icfpcontest.org/leaderboard
ソースコード: https://github.com/osak/ICFPC2016
書いたツール
今年は SOUND VOLTEX からツール名を取りました。
rasis
チーム slack 用のコマンドラインインターフェイス。各人が思い思いの口調で喋らせてキャラ崩壊してたのがおもしろかったです。
ちなみにこのツールはコンテスト開始前に @osa_k が slack を立てた時に作りました。準備は大事。
maxima
汎用ソルバー。facet（折り紙の折れ線で作られる多角形）が何枚重なっているのかやそれらの表裏や接続関係を全探索して正方形に復元できるかをチェックするアルゴリズムです。
コンテスト開始3時間後のお昼ごはんを食べている頃に思いついてチームメイトに言ってみると軒並み「確かに解けそうだけどバグる要素しかない（線分アレンジメント・双対グラフ構成・動的計画法による重なり枚数の列挙・全域木の全列挙・折り紙の復元）」という反応でしたが開始直後でやる気にあふれていたこともあり気合で実装しました。
Lightning が終了してもバグが取りきれず、一眠りしたあとでデバッグがおおまかに完了しましたが、結局折る回数が2回を超えると計算量が爆発してまともに解けませんでした。凸でないケースが解けるという強みがありましたが、それも @yuusti 作の天空の夜明けで解ける範囲であってこのツールは結局得点にほとんど貢献しませんでした。
いくらやる気にあふれていても事前に実装難易度や計算量を見積もっていれば結末はある程度予測できたはずで、今回の反省点になりました。
grace
すでに解いた問題とシルエットが合同（すなわち平行移動・回転・鏡像反転して得られる）な問題を探してきて解くソルバー。回転行列の導出がやや面倒である以外は、solution の生成で mkut が作った gideon が利用できたこともあってサクッと実装できました。
他のチームが古事記の再利用やそれらに少し手を加えただけの合同な問題を出していることが多かったので、少ない労力で高い効果を得ることができ maxima とは対照的な存在となりました。
また、この合同性を用いてまだ解かれていない問題をクラスタリングし、そのクラスターから得られる得点が多い順に我がチームが誇る折り紙職人が解いていくという戦略にも使用され、こちらも高い効果を発揮しました。
grace cluster を報告する rasis。
逆羅刹 (@osa_k 作の管理用サーバー) にもクラスタ一覧を見るページを付けてもらい、最終的にはぼくが何もしなくても職人が解くべき問題を探せる状態になっていました。
tsumabuki
@yowa さんチームが出した問題専用のソルバー。
すべての問題をビジュアライズして眺めていた @yuusti が、Team yowa からの問題は合同でなく grace では効率的に処理できないけれどもかなり規則的な生成法で生成されていることを発見しました。
他のチームもあまり解いていなかったこともあり、専用ソルバーを開発することになって書かれたのがこのツールです。終了8時間前くらいから実装を始めましたが、コンテスト終了までにバグを取り切って目標の問題を全部解き切れました。
反省
maxima をすぐに書き始めずに考え続ける精神力と判断力が必要でした。実装しているときは結構楽しかったけどね。
職人用に grace でクラスターを生成するとかすべてのビジュアライズされた問題をまとめて表示して比較・研究するというアイデアを出すなど、問題そのものでなく問題を解きやすくするための考察をできたのはよかった点です。チームに TopCoder 赤い人が2人もいるので問題考察力以外での貢献をすべきだと考えていましたが、無事達成できました。
来年は Unagi が殿堂入りしてくれたら優勝できるんですかね……。
天羽々斬 having dinner #icfpc2016 pic.twitter.com/5Pnj0Nr8dG
— シン・アズニャン (@osa_k) 2016年8月7日
1位だったときにチームで出前の寿司をとって食べました。この時は楽しかったなあ。
kawatea 問題
今年の ICPC 国内予選が終わりました。選手の皆さん、そして運営に携わった皆さん、本当にお疲れ様でした。
さて、ぼく界隈で大変注目すべきこととして、今年から審判団に大学の同期であった kawatea がいます！！！！ どこで差がついたのか、慢心、環境の違い……。
今年度からICPCの日本リージョンの審判団に加わることになりました。よりよいコンテストにできるよう頑張ります。
— かわてぃー (@kawatea03) 2016年4月11日
かわてぃーぷろ！！！！
ところで、こちらの問題をご覧ください。
indeednow-finala-open.contest.atcoder.jp
無向の辺に適宜向きを定めてある値を最適化する？？？ 今年の国内予選の H か？？？ という疑念がこれまたぼく界隈で話題になりました。
というわけで、思い出せる限りで過去の kawatea 問題を集めました。アジア地区予選対策にご活用ください*1。
2012年 JAG夏合宿 2日目 not_shiokawa + tokoharu セット
Treasure Hunt | Aizu Online Judge
House Moving | Aizu Online Judge
UTPC (FY) 2013
G: 夏休みの掃除当番 - 東京大学プログラミングコンテスト2013 | AtCoder
I: 支配と友好 - 東京大学プログラミングコンテスト2013 | AtCoder
CODE FESTIVAL 2014
あさぷろ
D: 枕決め - CODE FESTIVAL 2014 Easy | AtCoder
C: 宝探し 2 - CODE FESTIVAL 2014 Hard | AtCoder
チーム対抗リレー
F: ループを探せ - CODE FESTIVAL 2014チーム対抗早解きリレー | AtCoder
J: Color Game - CODE FESTIVAL 2014チーム対抗早解きリレー | AtCoder
indeed なう 本戦A
A: Table Tennis - Indeedなう（オープンコンテスト） | AtCoder
D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder
UTPC (FY) 2014
C: 最小カットと最大カット - 東京大学プログラミングコンテスト2014 | AtCoder
E: 宝くじ - 東京大学プログラミングコンテスト2014 | AtCoder
J: 看板の塗り替え - 東京大学プログラミングコンテスト2014 | AtCoder
*1:という建前でかわてぃーの作問センスを鑑賞していってください
