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:という建前でかわてぃーの作問センスを鑑賞していってください
SOUND VOLTEX の TOTAL 値
結論
SOUND VOLTEX の Effective Rate (通常ゲージ) は PUC すれば 210 % 増加すると思われます。
解説
基礎資料
SDVX 譜面保管所様の次のプレイ動画を資料とします。
I'm so Happy の NOVICE 譜面は全 408 チェイン、そのうちショートチップと直角つまみ（以下、これらをまとめてショートと呼びます）による分は 122 で、残りの 286 はロングと直角でないつまみ（以下、これらをまとめてロングと呼びます）によります。
仮定1: ショートとロングの回復量比は 4:1
NOVICE 譜面を見ていると、ショートを 1 つ取るたびにゲージがだいたい 1 % 増えて、ロングを1小節分取るとチェインが 16 増えてゲージがだいたい 4 % 増えることに気が付きます。
このことから、ショートとロングの回復量比は 4:1 であると考えられ、これはミス時の減少量の比と一致するので妥当な推測といえます。
仮定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: 不快な、どぎつい
基本的には首を出してても安全だよと言いつつ正面から近くで撃ち合うときなど危険なときにはちゃんと西住殿が隠れてることに気がついた。
Girls und Panzer ep.7-9
1回戦後の戦力増強タイム (7話) とプラウダ戦 (8, 9話)
気になった表現など
7話
invalid: 1. 病弱な、病人、病弱にする（動詞は通例受け身)） 2. 無効な
病弱引数例外
antisocial: 反社会的な、非社交的な
あんたいそしある、みたいな感じで言われたので聞き取り不能だった。綴りと音が一切一致しない英語は本当にクソだと思う。
yell: 大声で叫ぶ、叫び声。エール
ICPC に YellowYell って京大のチーム名がありましたね。
get anywhere: 成功する。役に立つ。 any- なのでなんか平叙文ではあまり使わなさそうな感じがする。
be held back: 足止めを食らう
本編では（麻子が）留年をするという意味で登場
supposedly: （文修飾で）……と想像される。
grandly: 雄大に
pull it off: うまくやる、なんとかする
butt: 棒などの太い方の端、根本、（米口語）おしり
slack off: 勢いを緩める
cowards: 臆病者共
生徒会の人が使っててほんとこわいと思いました（小並感）
dandy: (口語) すてきな
pumped up: アドレナリンの活性化から来る興奮と熱狂で緊張する (pumped upの意味 - 英和辞典 Weblio辞書)
divination: 占い
<- divine: 占う、神聖な
-> divine rights: 神授王権 Civ4では大した効果がない上に宗教キチが神学から速攻で取りに行くせいで交換材料にすらならない残念な技術だったような。
8話
suck: なめる、（米俗）嫌気がさす
仕事で Javascript sucks. ばっかり言ってたので後者の意味は知ってた。
The race is not given to the swift, nor the battle to the strong. 脚が速いものが競争に勝つとは限らないし、強いものが戦いに勝つとも限らない。聖書からの引用。
laid back: くつろいだ、リラックスした
mallard: マガモ。カモさんチームのことですね。
arrogant: 傲慢な
<-> modest: 謙虚な。大学院生の頃に謙虚で優秀という言葉を乱用していたのを思い出す。
thoroughly: 徹底的に、まったく
liver: 肝臓
remnisce: 追想する、思い出を語る
burden: 重荷
cocky: (口語) 生意気な
HE shell: 榴弾 (High Explosive)
nuts: (米俗) (憎悪や落胆の意味で) ばかな、くだらない
intact: 手付かずで
9話
consolidate: 合併整理する
endowment: 寄付金、天分
all on the table plan: ところてん作戦 なんでこの訳なんだろう。
deliberate: わざと、故意の
pierce: 貫通する
hibernate: 冬眠する、引きこもる
root for: 応援する
underdog: (試合などで) 負けそうな方
-> rooting for the underdog: 判官贔屓
daft: (口語) ばかな、まぬけな
tracer round: 曳光弾
<- round: この場合は（弾薬の）一発の意味
hall monitor: 風紀委員
lure: 誘惑する、誘い出す、ルアー
pursuit: 追跡、追求
<- pursue: 追跡する、追求する。名詞形の綴が予測不能。英語はクソ。
Girls und Panzer ep.4-6
前回の続き。聖グロ戦とサンダース戦の部分。
気になった表現など
4話
とりあえずただ見てただけなのであまりメモってない。あとで見なおそう
5話
戦車道カフェでの麻子のセリフがクソ早くて難しかった。幸い英語字幕がセリフと同じだったので何言ってるかわかった。ガルパンの英語版は全体的に聞き取りやすいと感じてるけど、ここだけ異常に難しくてほんとうに困った。
日本語版: 強豪校が有利になるように、示し合わせて作った暗黙のルールとやらに負けたら恥ずかしいな。
英語版: It'd be pretty embarrasing if one of those teams beats veterans that all sat around in the ivory towers coming up with that rule.
indubitably off-putting: 本当に感じが悪いな
その直後の華のセリフ。単語がどれ一つわからなくて笑った。
intrusion: 侵入
秋山理髪店を訪れるシーン。 sorry for the intrusion (おじゃまします)。動詞は intrude。
infiltrade: 潜入する
all-hands: 全員、全体。all-hands meeting で全体ミーティング
platoon: 小隊。splatoon はこれと splat の組み合わせ。
sergeant: （米陸空軍・海兵隊で）軍曹。米海軍で同等の階級は petty officer 兵曹。
imposter: 詐欺師、ペテン師
サンダース高潜入ビデオから。軍事系の単語が多い。
maneuverability: 機動力
maneuver: 巧みに操縦（する）
perv: （俗語）性的倒錯者
wiretap: （通信などを）盗聴する
retreat: 退却する
サンダース戦前半から。retreat は Civ4 のおかげで知ってた。
6話
draw first blood: 先制する
reassuring: 安心させる、元気づける
commission: 委任、任務
parting: 告別、離別、死去。parting haiku で辞世の句。
seize: つかむ、捕らえる。物理的でない対象にも使えそうな感じ。便利ワードっぽい。
applause: 拍手、称賛
アリサが全体的によくしゃべってくる強敵だったけど比較的わかりやすい。
