AtCoder Grand Contest 022 C - Remainder Game を解くときに考えたこと

背景

chokudai.hatenablog.com

こういう記事が出ました。で、ぼくが気になったのが、実際のところこの記事で言及されている問題(C - Remainder Game)を解くときに人々はどういう思考をするんだろう? ということでした。多分他の人も気になっていると思うので、先ず隗より始めよということで自分が考えたことを書きます。無駄なこともいろいろ考えてて長くなりますが、おつきあいください。

筆者について

amylase - AtCoder

これを書いているとき 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 でググって出てきた皆さんです。判定問題の部分で解説にあるようなグラフ構築でやってる人が多いです。

noimin.hatenablog.com

hamko.hatenadiary.jp

kurkur.hatenablog.com

thaim.hatenablog.jp

d.hatena.ne.jp

(22:08 追加) 各操作が最大1回ってのが見えるの速くてビビる あとぼくも時間計っておけばよかった

tozangezan.hatenablog.com

*1:これが典型に思える人だと10分ACが見えてくるのだと思います

*2:最初に考えた部分問題の結果をそのまま利用します

*3:実際にはなんか有名 DP っぽいと思ったところで実装がイメージでき、今これを書くときに部分和問題の名前を思い出しました

項目応答理論を用いた音楽ゲームの譜面難易度推定における一次元性の確認

導入

心理学的な量を測定するための理論の1つである項目応答理論においては、(多次元拡張されていなければ)応答が一次元性を持つこと、すなわち測定しているただ1つの量のみによって応答が説明できることを仮定しています。例えば TOEFL は項目応答理論を用いて語学力という心理量を測定する試験ですが、すべての問題について、それが解けるかどうかは各人が持つ語学力によって決まっているという仮定をおいていることになります。

項目応答理論の応用としては、語学力の他にも音ゲーの譜面難易度推定というものがあります*1。こちらにおける一次元性はどうでしょう、地力という心理量があってそれを測定していると考えてもよいのでしょうか。SOUND VOLTEX なら地力はつまみ力・鍵盤力・片手力などの要素に分解して議論することが一般的です。IIDX 出身のプレイヤーが14 *2 が半分も埋まらないうちにあっさり大宇宙ステージ [EXH] をクリアするなど、一次元性に反しそうな例も知られています。ボルテの応答は先に挙げた要素からなる多次元量によって説明するほうがよいという考え方もありえます。果たしてボルテのデータセットに一次元の項目応答理論をそのまま適用するのは妥当なのか、検討しました。

手法

プレイデータに対して主成分分析を行い、それぞれの主成分の解釈を行いました。

SDVX III のスコアツールに登録されているデータのうち twitter 上で収集できたものをもちいました (プレイヤー数 2375) 。このデータ上でクリアレート *3 が 95% 以下の 351 譜面を対象として、プレイヤーが譜面を通常ゲージでクリアしていれば 1、そうでなければ 0 とした反応行列を生成しました。プレイヤーをデータ点とし、各譜面のクリア反応が説明変数です。

このデータをもちいて、各譜面のクリア反応のペアの相関を求めて相関行列とし、これの固有ベクトルを計算しました。

結果

寄与率(各固有値固有値の総和に対する割合)は次のとおりです。

f:id:pepsin-amylase:20170317040856p:plain

寄与率が低い順にソートしています。とても偏っていることがお分かりいただけるかと思います。

f:id:pepsin-amylase:20170317040900p:plain

こちらが上位 5 成分について拡大したものです。第1主成分だけで 0.5 以上ありますし、この 5 つの寄与率の和は 0.722 にもなります。

各プレイヤーの第1主成分得点を横軸に、第2主成分得点を縦軸に取った散布図は次のようになります。

f:id:pepsin-amylase:20170317041402p:plain

なんだかものすごくきれいな曲線が見えます。

同様に、縦軸を第3主成分得点や第4主成分得点に置き換えると次のようになります。

f:id:pepsin-amylase:20170317041607p:plain

f:id:pepsin-amylase:20170317041640p:plain

ここにもきれいな曲線が見えます。

また、各種成分ベクトルの要素は、第1主成分については全て正、それ以外は正の要素と負の要素がだいたい半々でした。

議論

寄与率のグラフを見ると、全体の分散のほとんどは少数の主成分で説明できることがわかります。特に、第1主成分の寄与率が0.5を超えており、これだけでも一次元性が成り立っていると言ってもいいかもしれません。

しかも、この第1主成分はただひとつ要素が全て正です。これはクリア力の主成分であると解釈できます。

より興味深いのは主成分得点です。主要主成分の方向に射影するととてもきれいな曲線が出てきます。この現象を説明する1つの仮説を以下に説明します。

簡単のため、レベル14・レベル15・レベル16の3譜面からなるデータセットで同様の実験をしたと考えます。これらの譜面の難易度には十分な一次元性があるとすると、データ点の分布は次のようになるはずです。

f:id:pepsin-amylase:20170317044424p:plain

ここに主成分、つまり分散が大きくなる方向を書き加えると、

f:id:pepsin-amylase:20170317044452p:plain

こうなります。これは第1・第2主成分得点の散布図に近い感じがします。第3主成分は、15と16の軸を取り替えて *4

f:id:pepsin-amylase:20170317044643p:plain

こんな感じになっている気がします。

結論

主成分分析を行うことにより、寄与率 0.5 を持ち、しかも地力と解釈できる主成分を得ました。第2主成分以下についても、一次元性を仮定すれば難易度を別の形で表現したものであるとして説明できる可能性を示しました。SOUND VOLTEX のクリアデータは一次元性を仮定して解析してもよさそうです。

今後の課題

  • 他の反応(ハードクリア、UC *5 など)での一次元性
  • 他のゲームに置ける一次元性
  • 譜面属性は経験的には明らか。今回はノイズとの分離に失敗しただけかもしれない。一般的に考えられている属性が偏った譜面だけをデータセットに集めたら主成分にそれが現れるかも *6
  • 「仮説」は主成分得点の散布図が特定の曲線上以外にも点を持つことを完全には説明できていない。

 

 

 

*1:強引な導入です

*2:III 基準。実験をしていた頃は IV はリリースされていませんでした。

*3:プレイしたことのあるプレイヤーのうちクリアした人の割合

*4:どちらか一方の重みをマイナス1倍することに対応する?

*5:フルコンボのことです

*6:簡便な実験法としてはボルテでテカリと松戸の譜面を集めてくるなどが考えられます

ISUCON6: Team イーグルジャンプ

ISUCON6 の予選に ICFPC のときのチームのサブセット (osa_k, mkut) で出ていました。

予選大敗北で、個人的にはデータに基づかずに適当に改善していっていた & ログ解析環境の準備を軽視した結果ボトルネック (クソデカ正規表現) に取り組むのがとても遅くなったのが敗因だと思っています。来年参加する人や実務で高速化する人は気をつけようね!

 

以下、チーム Slack で展開されたイーグルジャンプの心温まる会話集です(チーム名に合わせたアイコンを使ってるうちに気分がノッてきてなりきりをやっていました)。

イーグルジャンプの日常

f:id:pepsin-amylase:20160922001436p:plain

今までなりきりをやるのは頭のネジが足りない人だと思っていたのですが、いざやってみるとあたかも自分が美少女になったような気分になり、やってる人の気持ちがわかりました。 みんなもやりましょう。

f:id:pepsin-amylase:20160922001926p:plain

デプロイは osa_k 謹製 hubot aoba によって自動化されていましたが、本番時にうまく動かなかったのが残念。

f:id:pepsin-amylase:20160922002042p:plain

いやあ素敵な会社だなあ、おっとこんなところに Javascript のコードがあるぞ、実行してみよう……?

f:id:pepsin-amylase:20160922002335j:plain

ところがどっこいっ... 現実ですっ...これが現実っ…!

ICFPC 2016: Team 天羽々斬

EDIT 2016/9/22: !!! 最終順位も2位でした !!! やったぜ

 

ICFPC 2016 に出ていました。ランキング凍結時点で2位でした。優勝してるといいな〜、1位は凍結前で我々の3倍だったり1問を除いて全問解いたりしてますが。

 

ぼくは基本的にはアルゴリズムを考えて実装する係でした。この記事では自分のやったことについて書きます。インフラ周りについては @osa_k がきっと何か書いてくれると思います。

EDIT 2016/8/12: @osa_k が書いてくれました。さすが!

osak.hatenablog.jp

問題: 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 を立てた時に作りました。準備は大事。

f:id:pepsin-amylase:20160809070122p:plain

 

maxima

汎用ソルバー。facet(折り紙の折れ線で作られる多角形)が何枚重なっているのかやそれらの表裏や接続関係を全探索して正方形に復元できるかをチェックするアルゴリズムです。

コンテスト開始3時間後のお昼ごはんを食べている頃に思いついてチームメイトに言ってみると軒並み「確かに解けそうだけどバグる要素しかない(線分アレンジメント・双対グラフ構成・動的計画法による重なり枚数の列挙・全域木の全列挙・折り紙の復元)」という反応でしたが開始直後でやる気にあふれていたこともあり気合で実装しました。

Lightning が終了してもバグが取りきれず、一眠りしたあとでデバッグがおおまかに完了しましたが、結局折る回数が2回を超えると計算量が爆発してまともに解けませんでした。凸でないケースが解けるという強みがありましたが、それも @yuusti 作の天空の夜明けで解ける範囲であってこのツールは結局得点にほとんど貢献しませんでした。

いくらやる気にあふれていても事前に実装難易度や計算量を見積もっていれば結末はある程度予測できたはずで、今回の反省点になりました。

grace

すでに解いた問題とシルエットが合同(すなわち平行移動・回転・鏡像反転して得られる)な問題を探してきて解くソルバー。回転行列の導出がやや面倒である以外は、solution の生成で mkut が作った gideon が利用できたこともあってサクッと実装できました。

他のチームが古事記の再利用やそれらに少し手を加えただけの合同な問題を出していることが多かったので、少ない労力で高い効果を得ることができ maxima とは対照的な存在となりました。

また、この合同性を用いてまだ解かれていない問題をクラスタリングし、そのクラスターから得られる得点が多い順に我がチームが誇る折り紙職人が解いていくという戦略にも使用され、こちらも高い効果を発揮しました。

f:id:pepsin-amylase:20160809072948p:plain

grace cluster を報告する rasis

逆羅刹 (@osa_k 作の管理用サーバー) にもクラスタ一覧を見るページを付けてもらい、最終的にはぼくが何もしなくても職人が解くべき問題を探せる状態になっていました。

tsumabuki

@yowa さんチームが出した問題専用のソルバー。

すべての問題をビジュアライズして眺めていた @yuusti が、Team yowa からの問題は合同でなく grace では効率的に処理できないけれどもかなり規則的な生成法で生成されていることを発見しました。

他のチームもあまり解いていなかったこともあり、専用ソルバーを開発することになって書かれたのがこのツールです。終了8時間前くらいから実装を始めましたが、コンテスト終了までにバグを取り切って目標の問題を全部解き切れました。

反省

maxima をすぐに書き始めずに考え続ける精神力と判断力が必要でした。実装しているときは結構楽しかったけどね。

職人用に grace でクラスターを生成するとかすべてのビジュアライズされた問題をまとめて表示して比較・研究するというアイデアを出すなど、問題そのものでなく問題を解きやすくするための考察をできたのはよかった点です。チームに TopCoder 赤い人が2人もいるので問題考察力以外での貢献をすべきだと考えていましたが、無事達成できました。

来年は Unagi が殿堂入りしてくれたら優勝できるんですかね……。

 1位だったときにチームで出前の寿司をとって食べました。この時は楽しかったなあ。

kawatea 問題

今年の ICPC 国内予選が終わりました。選手の皆さん、そして運営に携わった皆さん、本当にお疲れ様でした。

さて、ぼく界隈で大変注目すべきこととして、今年から審判団に大学の同期であった kawatea がいます!!!! どこで差がついたのか、慢心、環境の違い……。

 かわてぃーぷろ!!!!

ところで、こちらの問題をご覧ください。

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:という建前でかわてぃーの作問センスを鑑賞していってください

SOUND VOLTEX の TOTAL 値

結論

SOUND VOLTEX の Effective Rate (通常ゲージ) は PUC すれば 210 % 増加すると思われます。

解説

基礎資料

SDVX 譜面保管所様の次のプレイ動画を資料とします。

www.youtube.com

 

I'm so Happy の NOVICE 譜面は全 408 チェイン、そのうちショートチップと直角つまみ(以下、これらをまとめてショートと呼びます)による分は 122 で、残りの 286 はロングと直角でないつまみ(以下、これらをまとめてロングと呼びます)によります。

仮定1: ショートとロングの回復量比は 4:1

NOVICE 譜面を見ていると、ショートを 1 つ取るたびにゲージがだいたい 1 % 増えて、ロングを1小節分取るとチェインが 16 増えてゲージがだいたい 4 % 増えることに気が付きます。

このことから、ショートとロングの回復量比は 4:1 であると考えられ、これはミス時の減少量の比と一致するので妥当な推測といえます。

bemaniwiki.com

仮定2: ゲージ量が x' % と表示されている時、真のゲージ量 x は x' ≦ x < x' + 1 (切り捨て)

EXHAUST 譜面での開始直後の変化を観察すると、1 つ目のオブジェクトで 1 %にならないので切り上げではないことがわかります。 

またゲージ最高の状態からロングで 1 ミスすると 99 %表示になることから四捨五入でもないと考えられるので、ゲージ表示が素直に実装されていれば切り捨てと考えられます。

考察

基礎資料と仮定 1 から、I'm so Happy [NOV] において、合計増加量 t とロング 1 チェイン当たり増加量 x の関係は t = 122 * (4x) + 286 * x = 774t です。

動画において 181 チェイン時点でゲージは 94 %と表示されていて、ここまでに登場したショートは 56 個です (つまりロングは 125 チェイン)。この事実と仮定 2 から 94 < 56 * 4x + 125 * x < 95 という評価を得ますので、これらを解いて 208.46 < t < 210.69 を得ます。

条件を満たす t の中では、クリア基準の 3 倍である 210 はとてもキリがよいのでこれが総増加量ではないかと考えられます。

また、別の難易度の譜面もおおよそ 500 万点の少し前でゲージが最高値に達していることから、この設定は他の譜面にも適用されていると考えてよさそうです。

今後の課題

ハードゲージの回復量とか。

Girls und Panzer ep.10-12

決勝前の準備から決勝戦。11話と12話は戦闘シーンが多くて英語的には非常に簡単。

気になった表現など

10話

swear: 誓う、ののしる

put out: (明かりなどを)消す

spare time: 空き時間

IRL: In Real Life

<-> OLO: OnLine Only

alma mater: 出身校、母校

on the house: 店のおごりで

Operation Bagration: バグラチオン作戦。独ソ戦における赤軍の最大の反攻作戦で、これによりドイツ軍は独ソ戦開始前の位置まで押し戻されることとなった。ソ連の戦車で戦うプラウダとドイツの戦車で戦う黒森峰の関係を意識した引用。

back then: その時には、その当時には

11話

brat: 子供、ガキ

repel: 撃退する、拒絶する

choke: 窒息させる

tease: からかう、(主に米)ねだる

-> Operation Teasy Tease: おちょくり作戦

pacify: なだめる

12話

enormous: 巨大な

valor: 勇気

provoke: いらいらさせる、扇動する

dizzy: めまいがする、ふらふらする

-> Operation Dizzy Dizzy: ふらふら作戦

harsh: 不快な、どぎつい

 

基本的には首を出してても安全だよと言いつつ正面から近くで撃ち合うときなど危険なときにはちゃんと西住殿が隠れてることに気がついた。