うひょ～～～～～～！！！！(49位/1055，ソロ，銀メダル)
参加記代わりに何かを書く！(1か月遅刻)ということで，
銀メダル解法は最後に軽く紹介しつつ，
kaggleコンペそのものの紹介！！（特にAHC参加者向け）
※機械学習の話はありません！
kaggle santaコンペは年末に開催される数理最適化コンテストです
コンペ概要
「3種のルービックキューブ風パズルの特盛にワイルドカード付き」です．
まず配列でパズルの状態が貰えます．
操作の一覧も，配列がどう変化するかという形で貰えます．
完成形までもっていく操作列を出力せよ．
という感じです．
一応，雑魚の初期解は貰えます．
たまに，数マス間違っててもOKなテストケースがあります（ワイルドカード）
cube
ルービックキューブです．
でかいのもあります（最大で33*33*33）．
しましま模様やチェック柄，絵柄付きのサンプルもあります
こちらで遊べます（自分は2*2*2も解けませんでした）
wreath
右と左のリングがあって，どちらも時計・反時計回りに回転ができます．
最大でピース100個程度のリングが2つ繋がっています．
こちらで遊べます（リングの交わり方と色の配置は違うので注意）
globe
地球儀の形をしています．以下の二つの操作ができます．
- 同じ緯度の行を東西に1マス回転
- 経線に沿って真っ二つに切断，片方を180度回転
こちらで遊べます（4eta(しーた)@dna4_さんのコンテスト後tweetより発見）
ルールの違い
1か月焼いたって，いい
皆さんは「焼くのは2秒まで」と言われ続けて育ってきたので，リミッターを解除されたパワータイプのモンスターの気持ちになりますよね
そもそも，入出力が
csvファイルなんです．（※コンペによります）
スパコンで殴って最強の答えを手元で作り，それを提出したっていい．
kaggleとは暴力の世界なのです（？）
じゃあ
「太古から最強のPCで焼いてる人が勝ちそう」
とかなりそうですが，そんなことはありませんでした
詳しくは解法で紹介
順位表を，破壊
kaggleの一番イカれたシステムはやはりこれ
そもそもの話ですが，コンテストで優秀な成績を取ると，これが貰えます．
- メダル（金，銀，銅）
- 称号（グランドマスターとか）（メダルを集めると貰える）
これはコンテスト以外でも貰えます
kaggleサイト内には，解法やコードを公開できるページがあり，
いいね(upvote)を集めることで，メダルや称号を得られます
コンペで勝てなくたって，「記事のグランドマスター」になれるんです
結果として，強い解法を公開する人は一定数存在し，
公開されるや否や，参加者も次々にそのコピペを提出をするため，
いつ自分の解法が焼き払われるのか怯えながら過ごす
というのも，kaggleの特徴です
???「弱ェ奴は死に方も選べねエ」（ドン）
実際に焼き払われた話は解法パートで紹介
解法
解法解説の前に，まずは前提知識を軽く説明．
参考として，コンテスト中に非常にお世話になったフューチャー社の記事も貼っておきます．
HACK TO THE FUTURE ~!
前提知識
通常の3*3*3ルービックでさえ，状態量は10^19乗あるらしく，
適当な探索では時間内に終わりません．
そもそも計算時間以前に，メモリがボトルネックになります．
限られたメモリで答えを見つけるor逐次改善しないといけません．
ここで，以下の工夫が可能です．
双方向化
スタートとゴールから探索するだけで，あら不思議．
探索空間が大体平方根ぐらいになります．
競プロでいう，「半分全列挙」です．
two-phase法
中間ポイントを設けるテクニックです．
ルービックキューブにおける「まず1面揃える」などがこれです．
ゴールまでの手数が長いと，指数的に探索空間が増えるため，
これをするだけでも探索空間が減ります．
さらに，探索する空間に制限を加えやすいのも大きなメリットです．
例えば「まず1面揃える」をする際，揃えたい色以外は考える必要がありません．
無関係な面を一次的に黒で塗りつぶすなどすることで，探索空間を減らすことができます．
3*3*3のルービックキューブのアルゴリズムにおいて有名なものに，「Kociemba's algorithm」があります．
これは上手に中間ポイントを設けることで，かなり最善に近い解を得られます．
以降，中間ポイントを置きまくることをmulti-phaseと呼ぶことにします．
自分の解法
太字が自分で実装したもので，それ以外は拾い物です．
銀メダルの決め手になったのは，大きいglobeのソルバーを作れたことです．
実際それ以外はかなり適当です．
wreathは比較的簡単＋テストケースが少ないため，適当．
cubeはコピペコードが強すぎて，ほとんどコピペそのままになっています．
globeの解法
結論から言うと，３か所のピースをそれぞれ入れ替える操作列（wataさんに倣って3-rotと呼びます）を見つけると，解けます．
まず見つけ方です．
まず，1色ずつ揃えるmulti-phase+双方向全探索を実装する際，気付くべきことが2点あります．
- 今揃える色に関係ない緯度の操作はどうでもいい
- 180度回転の操作は1種でも解ける
1つ目はすぐわかります．
2つ目は，「全ピース東＋180度回転＋全ピース西」によって，あらゆる180度回転が一種類の180度回転で再現できることから証明できます．
これにより，必要な操作が5種類にまで絞れる（南北それぞれの行を東西で2*2通り，回転で1通り）ため，かなり深く探索できます(２０手程度)．
これによって，はじめて実験が可能となります．
うきうきで2点swapの操作を求めると，操作が長いだけでなくglobeのサイズに依存する，非実用的な答えが返ってきます．（絶望）
ここで挫けず，3-rotを試すことさえ出来れば，
- サイズに依存しない
- 操作の先頭と末尾が互いに打ち消し合う
- 操作場所の自由度が高い
という，最強の操作を発見できます
この操作を駆使し，次のステップで解くことが出来ます．
- 北出身と南出身の数を，どの緯度でも半々にする操作を探索
- 3-rotで北出身と南出身で固める，回転して南北について解ける
- 3-rotで経度を調整して完成（柄付きの場合，転倒数に注意）
また，最終日に初期擾乱を山登りで加えるコードを追記し，悪あがきしています．
その他の解法
wreathについては，解と異なるピースの数をなるべく減らす最良優先探索の類をするだけで，そこそこのスコアが出ます．
序盤に
N*N*Nのルービックキューブを解くソルバー(3*3*3に帰着→Kociemba's algorithm)
を使用したnotebook公開攻撃がなされ，通常のルービックはほぼ解かれた状態でスタート（ご丁寧にもwreathとglobeの簡単なケースを解いたデータもセットでついてくる）
チェック柄のルービックキューブは，予め色の塗り替えを行うとこのソルバーで解けるのですが，これもnotebook公開攻撃がなされ，ついに発狂．（中盤ではwreathと塗り替えだけで銀メダル圏内だったのに，一気にメダル圏外へ追い出される）
これを上回るソルバーを作る自信もなく，戦意喪失・・・
結局，ルービックにも3-rotが存在し，それが上位解法ということだそうです．
面内の3-rot操作の存在自体は，フューチャー社のこの記事のおかげでコンテスト中に知りました．
\HACK TO THE FUTURE ~!/
ただ，面内の3-rotだけでは転倒数的に柄付きキューブは解けず・・・（偶置換）
面の外との3-rotも見つけると，自前のソルバーが作れるようです・・・（惜しい？）
ただ，高wildcardの柄付きサンプルは，ソルバー+面内のスワップだけで許されるため，スコアにかなり貢献してくれました．\HACK TO THE FUTURE ~!/
これらに加え，解の最適化や逐次改善を行うコードが公開されており，コピペにコピペを重ねて最終提出です．
感想・まとめ
AHCからのARCからのAHCやないか！！！
強い性質を見つけるためにAHCをして，
強い性質を使ってARCをして，
それをAHCをして改善．
総合格闘技者の気分でした．
最上位のAHCerは世界レベル
wataさんをはじめ，最上位のAHCerが活躍していたのが印象的です．
AHCの競技人口的に，最上位のAHCerが世界で戦えるのか正直疑問があったのですが，バチボコに強くて笑っていました．
メンタル終了
1か月ソロでやるのは流石に辛い．
しかも順位表破壊攻撃で1か月の努力が水の泡になるので，本当に病みます．
最終日は10位ぐらい順位が落ちたので泣きかけました．（潜伏などの順位表の攻防がAHCより激しい）
これを克服するには最強になって破壊する側に回るしかありません．
皆さんも最強になって破壊を行いましょう！ おわり
最後まで読んでいただき，ありがとうございました
