目隠しルービックキューブ Old Pochmann法の変形Yパームの代替手順

まとめ

M2/OPにおける2点交換の手順、エッジのM2法は M2' の1手なのに、コーナーのOld Pochmann法は R U' R' U' R U R' F' R U R' U' R' F R の15手と長いですよね。 F2 r2 U' r' F r' F2 R U' R' の10手でULBコーナーとDFRコーナーを交換することができる。コーナーの向きが変形Yパームと異なるので、分析を、ULBステッカーからではなく、BULステッカーから始める必要がある。それ以外は、セットアップの手順もパリティ手順もそのままで良い。

回している様子はこちら。

www.youtube.com

www.nicovideo.jp

以降は、M2/OP法の簡単な解説や、手順の探し方、他の手順など。

目隠しキューブとM2/OP法

目隠ししてキューブを揃えるという競技(3BLD)がある。一発芸みたいなものではなく、WCA(World Cube Association)の公式種目にも目隠しキューブがある。目を開けてキューブを揃えるのとは、揃え方が全く異なる。次の動画やPDFを見ると良い。

www.youtube.com

acrobat.adobe.com

簡単に解説。初級者向けの解法では、特定のキューブ(バッファ)と他のキューブ(ターゲット)の2個を交換することを繰り返して揃えていく。

例えば、

0 1 2 3 4 5 6 7 8 9
-------------------
5 3 8 4 2 6 1 0 9 7

の下段を上段の状態に揃えたいとき。0の位置には5がある、5の位置には6がある、6の位置には1がある……と辿っていき、

5 6 1 3 4 2 8 9 7

という文字列を覚える。そして、0の位置と5の位置を交換、0の位置と6の位置を交換、0の位置と1の位置を交換、……とすると揃う。

5 3 8 4 2 6 1 0 9 7
6 3 8 4 2 5 1 0 9 7
1 3 8 4 2 5 6 0 9 7
3 1 8 4 2 5 6 0 9 7
4 1 8 3 2 5 6 0 9 7
2 1 8 3 4 5 6 0 9 7
8 1 2 3 4 5 6 0 9 7
9 1 2 3 4 5 6 0 8 7
7 1 2 3 4 5 6 0 8 9
0 1 2 3 4 5 6 7 8 9

数学的な言葉で言えば、任意の置換は、2個の要素(うち1個は固定)を交換する置換の合成で表せるということである。

初心者が0↔1, 0↔2, 0↔3, …と多くの手順を覚えるのは大変である。そこで、基本的には、実際に2個のキューブを交換する手順は1個だけで、前後にセットアップという手順を付けることで、バッファ(上の例では0の位置)と任意のキューブを交換する手順としている。実際に2個のキューブを交換する手順というのが、エッジのM2法では M2' の1手、コーナーのOld Pochmann法では R U' R' U' R U R' F' R U R' U' R' F R の15手である。この手順は、普通にキューブを揃えるときの「Yパーム」用の手順が元になっていて、「変形Yパーム」と呼ばれている。15手って長くない? もっと楽な手順があるんじゃないの? というのが動機である。

ちなみに、上級者向け解法でも、 5 6 1 3 4 2 8 9 7 のような文字列を覚えるところまでは一緒。バッファと任意の2個の計3個のキューブを交換する818個の手順を覚えて、2個ずつ揃えていく(3-style)。すご。

R2法

コーナー用にR2法という手法があるらしい。名前からして、 M2 の代わりに R2 の1手を使いそう。

roudai.net

M2+R2法のところのリンク先のページはなぜか途中で切れているが、載せているページが他にあった。

cuberaction.blogspot.com

あー、

しかし、特にR2法については例外パターンが多く、手順を覚えるのが少し大変です。

を理解した。これは大変。

なぜR2法が使われないのかを解説している動画もあった。たぶん同じ事を言っている……と思う。

www.youtube.com

変形Yパームの代わりの手順を探す

なるほど、 R2 みたいな他のコーナーやエッジを巻き込む手順では例外が増えてしまうのか。それなら、変形Yパームのような巻き込むキューブの少ない手順を探せば良い。条件を考えてみると……、

  • 2個のコーナーの交換である
  • そのうち1個のコーナー(バッファ)に隣接した2個のエッジが交換される
    • 2個のコーナーのみを交換するのは不可能
    • バッファと交換されるエッジを含む面は、セットアップで使えないので、最小限にしたい
    • 2個のコーナーが交換され、3個のエッジが交換されるという状態もありえない
  • もう1個の交換されるコーナーはどこでも良い

と思って探したけれど、実際には次の条件もあったほうが良い。

  • 変形Yパームと同じコーナーが(ULBとRDF)交換されるほうが良い
    • バッファ以外のコーナーはどこでもセットアップはできるはずだけれど、対角に位置していないと、セットアップ手数が増える
      • 変形Yパーム代わりの手順がよほど短いならそれでもペイするが……
    • 対角ならどこでも良いのだけど、どうせなら変形Yパームと全く同じコーナーだと、セットアップの手順を覚え直さなくて良い
    • それでも向きはどうでも良い
      • 分析の開始ステッカーが変わるだけ
  • 変形Yパームと同じエッジ(ULとUB)が交換されるほうが良い
    • ここが変わると、パリティ手順も探さないといけないので

で、プログラムを書いてこのような条件で探した。

github.com

手順と使い方、使えるのか

出てきたものがこれ。

len: 10
 ULB(DFR) DFR UB UL: R U R' F2 L D' L D L2 F2
 ULB(RBD) DRB UB BL: R D2 L2 F L F' L D2 R' B
 ULB(RDF) DFR UB BL: R2 U2 F' U' F U' R2 D B' D'
 ULB(RUB) UBR UB BL: R2 D B D' R2 U F' U F U2
 ULB(UBR) UBR UB UL: R2 F' U' F R2 B' D B' D' B2
 ULB(DFR) DFR UB UL: R2 B2 D B D' B R2 F' U F
 ULB(FUR) URF UB UL: R' F2 L2 D' L' D L' F2 R U'
 ULB(RDF) DFR UB BL: R' B' R D2 L' F L' F' L2 D2
 ULB(RFU) URF UB UL: L F2 R' D R' D' R2 F2 L' U'
 ULB(FDL) DLF UL BL: L F' D2 B R' B R B2 D2 F
 ULB(LFD) DLF UL BL: L B D2 F2 R F R' F D2 B'
 ULB(UFL) UFL UB UL: L2 D' L' D L' F2 R U' R' F2
 ULB(LDB) DBL UB BL: L2 F L F' L D2 R' B R D2
 ULB(FDL) DLF UL BL: L' U' F2 D2 R' D' R D' F2 U
 ULB(LFD) DLF UL BL: L' D F2 U' R U' R' U2 F2 D'
 ULB(BDR) DRB UB BL: L' D2 R F' R F R2 D2 L B
 ULB(RBD) DRB UB BL: U R2 D' F D' F' D2 R2 U' B'
 ULB(FUR) URF UB UL: U R' F2 L D' L D L2 F2 R
 ULB(RFU) URF UB UL: U L F2 R2 D R D' R F2 L'
 ULB(FLU) UFL UL BL: U2 R U R' U F2 D' L D F2
 ULB(RUB) UBR UB BL: U2 F' U' F U' R2 D B' D' R2
 ULB(RFU) URF UB UL: U' F R2 B' D B' D' B2 R2 F'
 ULB(FDL) DLF UL BL: U' F2 D R' D R D2 F2 U L
 ULB(FUR) URF UB UL: U' B' R2 F2 D' F' D F' R2 B
 ULB(LFD) DLF UL BL: D F2 U2 R U R' U F2 D' L
 ULB(RDF) DFR UB BL: D B D' R2 U F' U F U2 R2
 ULB(LDB) DBL UB BL: D2 R' B' R D2 L' F L' F' L2
 ULB(RDF) DFR UB BL: D2 L2 F L F' L D2 R' B R
 ULB(BLD) DBL UL BL: D2 F L F' D2 B R' B R B2
 ULB(FRD) DFR UL BL: D2 B2 R' B' R B' D2 F L' F'
 ULB(BDR) DRB UB BL: D' R2 U2 F' U' F U' R2 D B'
 ULB(FRD) DFR UL BL: D' L' D F2 U' R U' R' U2 F2
 ULB(RFU) URF UB UL: F R2 B2 D B D' B R2 F' U
 ULB(FRD) DFR UL BL: F L F' D2 B R' B R B2 D2
 ULB(UFL) UFL UB UL: F2 R U R' F2 L D' L D L2
 ULB(DFR) DFR UB UL: F2 L2 D' L' D L' F2 R U' R'
 ULB(FRD) DFR UL BL: F2 U2 R U R' U F2 D' L D
 ULB(FLU) UFL UL BL: F2 D' L' D F2 U' R U' R' U2
 ULB(DFR) DFR UB UL: F' U' F R2 B' D B' D' B2 R2
 ULB(FDL) DLF UL BL: F' D2 B2 R' B' R B' D2 F L'
 ULB(RBD) DRB UB BL: B U R2 D2 F D F' D R2 U'
 ULB(LFD) DLF UL BL: B D2 F' R F' R' F2 D2 B' L'
 ULB(BDR) DRB UB BL: B D' R2 U F' U F U2 R2 D
 ULB(BLD) DBL UL BL: B2 R' B' R B' D2 F L' F' D2
 ULB(UBR) UBR UB UL: B2 D B D' B R2 F' U F R2
 ULB(RBD) DRB UB BL: B' R D2 L' F L' F' L2 D2 R'
 ULB(FUR) URF UB UL: B' R2 F D' F D F2 R2 B U
 ULB(BDR) DRB UB BL: B' L' D2 R2 F' R' F R' D2 L

追加の条件を満たすのはこの4個。

 ULB(DFR) DFR UB UL: R U R' F2 L D' L D L2 F2
 ULB(DFR) DFR UB UL: R2 B2 D B D' B R2 F' U F
 ULB(DFR) DFR UB UL: F2 L2 D' L' D L' F2 R U' R'
 ULB(DFR) DFR UB UL: F' U' F R2 B' D B' D' B2 R2

2点交換の手順だから、逆再生も同じ状態になる。また、結果的にULBとDFRの交換になっていて、これはBLエッジとFRエッジを含む斜めの面で対象なので、その面で対象の手順も出てくる。実質的に1個の手順。

3個目の F2 L2 D' L' D L' F2 R U' R' を実際に回すときはこうするだろうと書き換えると、最初に書いた F2 r2 U' r' F r' F2 R U' R' になる。5手目のFが回しづらい。左手親指で跳ね上げるか、右手ミハエルトリガーか。

1個目の R U R' F2 L D' L D L2 F2R U R' F2 r F' r U r2' F2 という感じだろうか。これも6手目の F' や8手目の U あたりがつらい。

2個目の R2 B2 D B D' B R2 F' U F はそのまま回せるっちゃ回せるが、押し込みが多くなってつらい。

4個目は回し方が分からん。

(実質同じ手順だから)どれもULBとDFRがこのステッカーの順で入れ替わる。変形Yパームとは違う。とはいえ、これは分析のときの開始ステッカーを変えるだけである。ULBのUステッカーからではなく、Bステッカーから読み始めれば良い。そうすれば、セットアップ手順を変える必要は無い。追加の条件で、変形Yパームと同じエッジが入れ替わるので、エッジとコーナーの間のパリティ手順は変形Yパームのものがそのまま使える。

手数は短くなってはいるけれど、回しづらい分で、変形Yパームと比べたときにどうなんだろうなぁ。少しでもタイムを削るより先に、まずは成功確率を上げたいわけで、回しにくいのは大きなデメリットかなぁ。変形Yパームは当然Yパームと似ていて、うっかり最後に F' を付けてしまうというミスを良くする。それが無くなるという小さなメリットはあるかもしれない。

Future work

探索時間が伸びてしまうので、2層回しや中層回し、持ち替えは含めていない。それらを含めればもっと良い手順があるかもしれない。ある手数で見つかった時点で探索を打ち切っている。1手増えたところにもっと回しやすい手順があるかもしれない。

あと、プログラムが出してきた手順を全部は確認していないので、その中に良いものがあるかも。使う面を限定した結果もここに載せている。

github.com

目隠し2x2x2キューブ

聞かないな。上級者は2x2x2なら普通に揃える方法で、最後まで読み切って、目を瞑っても揃えられたりするのか? 私は無理。なので、2x2x2の変形Yパームにあたる何か良い手順があれば、2x2x2目隠しが楽になって嬉しい。上げた条件からエッジの条件を無視すれば、2x2x2用の手順になるはず。でも、3x3x3用より短い9手以下の手順は無かった。残念。

Gmailのエイリアスを生成するChrome拡張を作った&意味はあるのか?

例えば、 example@gmail.com というGmailアドレスを使っているとき、 example+hoge@gmail.com のように + の後に別の文字列を入れたり、ex.am.ple@gmai.com のように . を挿入したりしても、メールが届く。何かでメールアドレスを登録するとき、私は + の後にランダムな文字列を付けたメールアドレスを使っている。この作業が面倒になってきたので、Chrome拡張を作った。

chrome.google.com

アイコンをクリックするとランダムなエイリアスを表示するだけ。

Gmail的には、全く別のメールアドレスを使うことを「エイリアス」と呼んでいて、こっちはmodifiedとかvariationと呼ぶべきなのかもしれない。まあ、いいか。

support.google.com

gmail.googleblog.com

ずっとそうしてきたけど、意味はあるのだろうか。

メリット

スパム対策

そもそもはスパム対策だった。もしメールアドレスが漏洩したときに、その漏洩したエイリアスに届いたメールは全部消すように設定できる。「お前のところから漏れたのか💢」と漏洩元を知ることもできる。でも、スパムを送る人もバカじゃないから、 + 以降を消すのではないだろうか。 . を挿入するほうは、Gmail以外だと届かなくなるだろうし、 . を全部消してから送るということはしなそうな気もする。でも、 . のほうは生成できる数が少ない。メールアドレスの規格上、 . は連続してはいけない。

宣伝メール対策

唯一役に立つのは、スパム業者と言うほど悪くもないが、宣伝メールを頻繁に送ってきて「配信停止はこちらにメールでご連絡ください」とか書かれている業者だろうか。いちいちメールを送らなくてもそのままゴミ箱に放り込むように設定できる。

デメリット

使えないときがある

メールアドレスの規格上は、+ は許されているのだが……。

https://www.rfc-editor.org/rfc/rfc5322.txt

入力欄で「使えない文字が含まれています」と言われるならまだマシで、入力は受け付けられるがいつまで経っても確認メールが届かないということがけっこうある。

RFC違反であることは承知の上で、あえて + を弾いていることもあるらしい。1個のGmailアカウントでサービスのアカウントを登録されることを防ぐため。 . の挿入で大量に作れるからあまり意味は無いのでは? と思うが……。

RFC違反アドレスのアドレスを使っている人にメールをお送りしています。システム変更で今後は使えなくなるので、メールアドレスを変更してください」というメールが届いたこともある。RFCに準拠していないのはそっちだ💢

防衛省から物理の手紙が届いたこともある。これはこれですごい。

返信が面倒

今どき、メールアドレスを登録することは数あれど、メールを送ることはあまり無い……が、たまにはある。 + 付きのメールアドレスで登録してメールが届き、返信を求められたときが面倒。向こうがメールアドレスで管理している可能性があるので、( + の有無が違うだけとはいえ)異なるメールアドレスから返信するのは良くないだろう。Gmailの設定画面で(Gmail的な意味での)エイリアスとして登録して、送信元にすることはできる。でも面倒。

自分のメールアドレスが自分で分からない

そういう事態に陥ったことは無いのだけど、そのうちハマりそうで怖い。

パスワード管理ソフトのデータを吹っ飛ばしてしまったとする。たいていのサービスで「パスワードを忘れました」というと、「それではあなたのメールアドレスを教えてください」となるはず。このときに自分のメールアドレスが分からない。登録時に普通は確認メールが飛んでくるので、Gmailにさえログインできれば何とかなるし、ログインできなかったらそもそもパスワードのリセットもできないだろうけど。本人が自分のメールアドレスを知らないという状況は想定されていないはずで、他にも思いがけないところで困るかもしれない。

これが怖いので、最近は、重要そうなサービスには + を付けずに登録している。

Chrome拡張を作っておいて言うのもなんだが、面倒なことをしないで、メールアドレスそのまま使えば良いのではという気がしつつある。

ルミナスの突っ張りメタルラックを段差のある天井に設置する方法

このシリーズを、

【ルミナス レギュラー】テンション(突っ張り)ラック商品一覧|スチールラック・メタル製ラック通販のルミナスクラブ

ここに設置した。

同じ事をしたい人がいるかもしれないし、販売サイトの記載だけでは分からないこともあるので、書いておく。

Disclaimer。 ここに書いてあることが何か間違っていて、上手く行かなくても責任は負いかねる。 私が間違っていなくても、仕様に書かれていないことは、こっそり変わることもある。 確実を期すなら、販売元に問い合わせたほうが良い。

まずは私が取った以外の方法。

そもそも、天井の高いところと低いところの高さがどちらも突っ張り棒の調節可能な範囲に収まっているならば、何も難しくない。 突っ張り棒の長さは個別に調節可能。 我が家の天井の段差は差が大きすぎて不可。

奥行きの狭いものを買って、全体を奥の部分に収めるのも手。 でも、奥行きで収納力はだいぶ変わるよなぁ。

奥のほうの2本だけ突っ張るという手もあるかもしれない。 タンスとかに耐震対策で突っ張り棒を付けるという話だと、前のほうではなく後ろのほうに付けろという話が出てくる。 しかし、ホントに大丈夫なのかが心配なのと、後述のように、ハーフシェルフを使うと手前側の奥のほうの空間を有効利用できる。

各ポールは、アジャスター固定用のネジ穴がある下部ポールと、中間ポール、突っ張り棒の上部ポールの3本でできている。 延長用の色々な長さのポールが売っているので、中間ポールをそれに取り替えて長さを良い感じにするという方法が思いつく。 が、ここに問題があり、突っ張り棒と延長用のポールでは溝の高さが違うらしい。 なんで???

https://www.luminous-club.com/products/detail/product_934/

どうしたもんかなぁと考え、「でも、4本全部(長さの違う)延長用ポールを入れれば、上部ポールは溝が合うのでは?」と思い至った。 こういうこと。

これは実際に上手くいった。

1個だけ注意点があり、初めから付属している中間ポールも延長ポールとは溝が合わない。 上から順番に、31cmの延長ポール、46cmの延長ポール、(初めから付いている)中間ポール、上部ポール(突っ張り棒)。 後から買った61.5cmの延長ポールも、31cmや46cmの延長ポールと同様だった。 2本を元の中間ポールで、2本の中間ポールを延長ポールに変えると、中間ポールより上が全て棚設置不可になる。中間ポールの長さが延長ポールに無いなぁとは思ったんだよな……。中間ポールと上部ポールは溝が合う。(試していないけど)中間ポールを抜くだけなら、どこでも棚が設置できるはず。

中間ポールの反対側は延長ポールと同じように半ピッチなので、逆向きに付ければ、中間ポール&延長ポール部分は溝が合うかもしれない。 でも、逆向きにすると、二重線部分が面倒なことになる。 元の向きだと二重線の上の溝が他の溝と合うけど、下を合わせなければいけなくなってしまう。

ということで、段差のある天井に設置したければ、最初から付いている中間ポールはポイして、長さの違う延長ポールに変えれば良い。延長ポールと上部ポールの組み合わせになる部分以外には棚が設置できる。

私が買ったものはこれ。 他の製品ではまた違う可能性はある。

この記事を書くのに色々と見ていたら、このズレを調整するパーツがあるらしい。 え、あるの???

https://www.luminous-club.com/feature/faq/

何らかの理由で溝がズレるのは仕方ないとして、このパーツは標準で付属するべきでは? せめて、問い合わせとかではなく、普通に売るべきでは? そもそも商品ページの溝がズレているの注意書きにもこのパーツがあると書くべきでは? と思うが……なんだろうね。ジョイント数が増えると弱くなりそうだし、電話で使い方とか使っているパーツとか聞いて、大丈夫そうなら送るとかなのかもしれない。

ハーフシェルフ

https://www.luminous-club.com/products/detail/product_790/

奥行き半分で、2本のポールに設置できる棚がある。

良い感じ。

まあ、最初はこうだったけど。

次項のパワポで色々と考え、面倒になってきて、「何とかなるだろ」で買ったら、さすがに一番上の棚が使いづらかった。

あと、31cmの延長ポールと46cmの延長ポールなら棚設置不可の高さが15cmのところ、31cmの延長ポールと61.5cmの延長ポールだと30.5cm設置不可なので、棚の高さの制約がキツい。 なかなか上手くいかない。

耐荷重20kgで、テレビも置けると謳っている。 ただ、止めろという記載は見当たらないけど、ポールに負荷が掛かりそうなので、フルサイズの棚板より上にハーフサイズの棚板を付けて重いものを置くのは止めたほうが良いかもしれない。 ポールに負荷が掛かると、今度は天井に負荷が掛かりそうだし。 そもそも高いところに重いものを置くのは危ない。

PowerPointが便利

数字だけを見て組み合わせを色々と試していると、頭がこんがらがってくる。 そういうときにPowerPointが便利。 幅と高さを数値入力できるので、実際の1/10くらいの値でポールなどの長方形を作って、色々と試すと良い。

ライト、スリム

ルミナスのレギュラーラックはポール系が25mmだけど、19mmのライトがある。

昔学生の頃に買ったのはライトで、理由は値段が安いから。 ちょっと華奢な感じがする。 まあ、社会人になって多少のお金はあるし、レギュラーで良いだろと思って、今回はレギュラーを買った。 値段としっかりさだけのトレードオフと思っていたが、レギュラーはラック自体が重い。 スチールラックを使ったことのある人は分かると思うけど、棚板の高さ調整がけっこう大変。 この大変さも上がっている感がある。 そんなに重いものは置かないので、ライトで良かったかもしれない。

スリムもある。 ワイヤーが横になっているのを売りにしているけど、耐荷重が軽い分、棚板も自体も軽かったりするのかな?

組み合わせ

買ったのはNLH9018-6T。 届いて知ったのだが、これは5段のラック(NLH9018-5)と棚板1枚(ADD-P2560J)、突っ張りポール(ADD-P2560J)のセットである。 個々のパーツをセットにしたわけではなく、既存のセットと追加パーツのセット。 個別のパーツのページにより詳しい説明が書かれているかもしれないし、どういうセットなのかを書いてくれ……と思ったら書いてあった。 ここ。

でも、付いてきた円形アジャスターが書かれていないな。 おまけなのか、構成品は最大3個までしか書かれないのか。 謎。

ルービックキューブを崩すのはどのくらい難しいのか

「何回くらい回せば崩したことになるのかな?」とかが気になって、この記事を読んでいるなら、悪いことを言わないので、csTimerとかのスクランブル機能を使ってほしい。 この手のツールは、ルービックキューブの可能な配置43,252,003,274,489,856,000通りから等確率に配置を生成してくれる。 崩すという意味ではこれが正しいはず。

cstimer.net

この記事での「崩す」の定義は、「6面全てに6色が現れるようにする」である。

元ネタはこの動画。

www.youtube.com

動画の概要。

  • ルービックキューブを揃えられる人と、揃えられない人が対決したい
  • 揃えられる人が揃える時間と、揃えられない人が崩す時間で比べよう
  • 「崩す」とは「6面全てに6色が現れるようにする」ことである
  • あれ、崩すの難しくない?

という流れ。 それで、どのくらい難しいのかが気になった。

難しさの評価というのも難しい。 揃えた状態というのは約4千京個の中に1個しかなく、ある意味で一番難しいが、揃えられる人にとっては簡単である。 とりあえず、キューブの全ての可能な配置の中に6面全てに6色が現れるものがどのくらいあるのかと、揃った状態から6面全てに6色が現れるようにするまでの最小手数を調べた。

使ったプログラムはここ。

github.com

6面全てが6色となる確率

厳密な値を得たいが、難しいので、キューブの配置をランダムに1億個生成して調べた。 他の場合も気になるから、色数が最小の面の色数と、色数が最大の面の色数別に集計した。 見方がちょっと難しいかもしれない。 min, max = 2, 3 のところに1と書いてあるのは、各面の色数が2色から3色までの配置は1億個中に1個しかなかったということ。

min\max 1 2 3 4 5 6 sum
1 0 0 0 0 13 0 13
2 0 1 1,357 78,059 106,067 185,484
3 0 39,695 4,563,479 8,834,256 13,437,430
4 34,643 17,218,401 51,445,599 68,698,643
5 1,854,157 15,794,432 17,648,589
6 29,841 29,841
sum 0 0 1 75,695 23,714,109 76,210,195 100,000,000

数字は同じだが1億で割ったパーセント表示のほうが分かりやすいかもしれない。

min\max 1 2 3 4 5 6 sum
1 0.000% 0.000% 0.000% 0.000% 0.000% 0.000% 0.000%
2 0.000% 0.000% 0.001% 0.078% 0.106% 0.185%
3 0.000% 0.040% 4.563% 8.834% 13.437%
4 0.035% 17.218% 51.446% 68.699%
5 1.854% 15.794% 17.649%
6 0.030% 0.030%
sum 0.000% 0.000% 0.000% 0.076% 23.714% 76.210% 100.000%

あるいは、逆数にして、何個中1個がそういう配置だったかというのもありか。

min\max 1 2 3 4 5 6 sum
1 - - - - 7692307.69 - 7692307.69
2 - 100000000.00 73691.97 1281.08 942.80 539.13
3 - 2519.21 21.91 11.32 7.44
4 2886.59 5.81 1.94 1.46
5 53.93 6.33 5.67
6 3351.09 3351.09
sum - - 100000000.00 1321.09 4.22 1.31 1.00

見るべきは、min, max = 6, 6 のところの値で、0.03%が6面全てに6色あるような配置だった。 約3,000個に1個。

ちなみに、ある配置から3手で得られる配置の個数は3,240個。 6面全てに6色があるような配置が、キューブの状態空間の中に均等に分布していると仮定するならば、3手程度でそういう配置が作れることになる。

www.cube20.org

約2個に1個は、最小の色数が4で最大の色数が6となる。 へー。

(不完全)1面が揃う確率は、0.000013%しかない。 何となくもう少し高いと思っていた。 でも、たしかに、スクランブルして不完全一面が揃っていた覚えはないな。

6面全てがn色の配置の作りかた

作り方を覚えておけば、動画のような勝負を挑まれたときに役に立つだろう。 そんな機会は無いと思うけど。

パターンキューブを使った作り方と、プログラムで探した最小手数での作り方を載せておく。

1色

これは普通に揃えれば良い。

2色

パターンキューブで各面が2色のものは多い。 チェッカーキューブやヘソキューブが簡単だろうか。

M2 S2 E2

M S M' S'

最小手数は2手。 なるほど、これで良いのか。

R2 U2

3色

私が思いついたのは、チェッカーキューブとヘソキューブの組み合わせ。 チェッカーキューブは対面の色で、ヘソキューブはあるコーナーを中心に回す感じなので、出てくる色が違う。

M2 S2 E2 M S M' S'

パターンキューブで「ケージ」というものがあった。 これ知らなかった。

www.daaokacubeblog.com

L U F2 R L' U2 B' U D B2 L F B' R' L F' R

プログラムで探した最小手数は4手。

R U D' R'

4色

パターンキューブベースで作る方法は思いつかなかった。

ミニキューブインキューブ(↓)を3回行えば各面3個キューブの色が変わると思うかもしれないが、同じ色が出てきてしまう。 ミニキューブインキューブでは、対角線上の2個のコーナーが回転するものの、その回転の方向が逆なので。

www.daaokacubeblog.com

NG例。

B2 R U2 R' U' R U' R' L' U2 L U L' U L B2 y B2 R U2 R' U' R U' R' L' U2 L U L' U L B2 y B2 R U2 R' U' R U' R' L' U2 L U L' U L B2

もちろんそういう配置が存在しないわけではなく、最小3手で作れる。

R U2 F

5色

スーパーフリップでOK。 ルービックキューブは最長でも20手で揃えられるが、20手掛かるパターンとして有名。 全てのエッジが反転していて、各面には4個のエッジがあるので、エッジ以外と合わせて5色。

www.daaokacubeblog.com

B2 R U2 R' U' R U' R' L' U2 L U L' U L B2

最小4手で作ることもできる。

R U D R

6色

本題。

これもパターンキューブベースで作る方法は思いつかなかった。 スーパーフリップからセンターキューブを対面色と入れ替えられれば6色になるが、ヘソキューブと違って、センターを対面と入れ替えることはできない。

これが作れない。 パリティとかそういう話ではなく、キューブを分解しても作れない。コーナーの色の並びが逆だから。

例えば、黄色、緑、赤コーナーの色は、本来はこういう並び。

プログラムに探させた結果はこれ。6手。

R U R2 L2 U L

確率のところに書いた3手程度に比べるとだいぶ手数が多い。 まあ、揃った状態から作ろうとしているからかな。

これを覚えておけば、「揃えるのと崩すので勝負しよう」と言われたときに勝てる。

Posting Puzzleを解いてみた

これ。

mame.github.io

以降には答えも載せているので、まずは自力で解いてほしい。 Stage 3までは人力で、Stage 5まではプログラムを書けば解けると思う。

















プログラムを書いて解く

Stage 4以降は人力では無理だったので、プログラムを書いた。 ソースコード

github.com

どんなアルゴリズムを使っているか。

反復深化法

このパズルは、基本的には、クリアしないままいくらでも続けることができてしまう。 同じ状態がループしたり、あるいは上段か下段がいくらでも長くなったりする。 単純に再帰で深さ優先に探索すると、クリアできない選択肢を掘り続けてしまう。 幅優先で探索しようとすると、メモリが大量に必要になる。

そこでおすすめなのが反復深化法である。 まずは、最大深さ(最大手数を)1に制限して、深さ優先で探索をする。次に最大深さを2に制限して、3に制限して……と徐々に深くしていく方法。 答えが見つけられなかった最大深さの探索が無駄に思えるかもしれないが、意外とそうでもない。 例えば、1手に3通りの選択肢があって、4手で解けるとしたとき、いきなり最大深さを4にしたときは、34=81ノードの探索が必要になる。 反復深化で1手づつ最大深さを増やしていったときは、31+32+33+34=120ノードである。 そんなに大きくは変わらない。 ……というのが教科書的な説明だけど、この問題は置けないピースが多くて、実際には1手あたり3通りも無いので、けっこう無駄になる。 1手ずつ増やすのではなく、もっと段階を粗くするのも良いかもしれない。

ピースの個数の比を求める

このパズルは先のステージに行っても、ピースの個数は3個のままである。 そして、上段に流した封筒の個数と、下段に流したハンコの個数は等しい。 上段のハンコと下段の封筒の個数も同様。

各ピースを何個使うかを3個の変数で表し、等式が2個あるので、変数を2個消せる。 ある1種類のピースの個数で他の2種類のピースの個数が表せる。 つまり、ピースの個数の比が分かる。

反復深化で、使うピースの合計数を決めれば、各ピースを何個使うのかも決まる。 あるピースを使い切ったら、その時点で探索を打ち切ることができる。 これが枝刈りとして優秀だった。

左右を逆にする

上がstage 5の問題、下が各ピースの左右を逆にしたもの。

こうしても本質的には同じ問題である。 ポストに入って消えるのではなく、残しておいて、上下段の右端が揃ったらクリアという問題だと考えると分かりやすいかもしれない。 ピースを使う順番は逆になる。

あるいは、ピースの左右を逆にするのではなく、ポストを右に置いて、左から右に流す問題と考えても良いかもしれない。

本質的には同じ問題だが、探索の難易度は変わる。 他のステージは試していないが、stage 5と6は逆のほうが探索が速くなった。

今後必須になるピースを考える

Stage 5の左右を逆にした問題で、赤枠で囲ったスタンプに注目する。 中央のピースにも封筒はあるけれど、中央のピースはここには置けないので、ここでは必ず左のピースを使うことになる。 この時点で将来左のピースをいくつ使うのかも考慮に入れ、「ピースの個数の比を求める」の枝刈りをすることで、より早期に枝を刈れて速くなる。

上段か下段が長くなりすぎたら打ち切る

Stage 5はこれで解けた。 ここまでに出てきた手法は全て、答えがあるならば必ず見つけるし、(反復深化を1手ずつ増やせば)最短手数の解法が見つかる。 解けないことが確定した時点で枝刈りをするので。 上段か下段が長くなりすぎたらそこで探索を止めるのは、解けないことが確定する前に枝刈りをするから、あるはずの答えが見つからないことがあるし、答えが出てきても最短手数とは限らない。 できれば最短手数だと確定できる答えを見つけたかったが、諦めた。

答え

ピースは左から順番に0, 1, 2としている。

Stage 1

001

最短3手。

Stage 2

2012

最短4手。

Stage 3

0200211

最短7手。

Stage 4

022001022210002022110101120222201000012102211202101002202121100102111211211

最短75手。

問題はこれ。

先のステージでもピースの中の封筒やスタンプはそんなに増えない。それなのに、これだけ手数が増えるとは驚き。

Stage 5

1211212112111011212120121121121011101110112012120121201210112101121011201211201211201210112121011101
0112012112112012120012101110111010112201120121201212001101101011210112201201200121120110122122011101
0120111101101200101101201202001201022021201121012112011101012120011220121101121201211210112121120121
1211101011101110120012120121202011210112210121120121112011101011101210121200121201120112201122110101
1011011121200120120110112201010120110120010120200220

452手。 最短かどうかは分からないが、まあ、たぶん、最短じゃないかな。 驚きの長さ。

解いているときにどんなことになっているのか気になりますよね。 動画を撮っておきました。

www.youtube.com

動画を撮って気が付いたけど、下段が一旦短くなって、また長くなる。 個数の比からピースの個数を求めて……の枝刈りは、上段か下段が長すぎるのを制約するという役割もある程度兼ねている。 使うピースが偏れば、上段と下段の個数も偏るので。 それなのに、「上段か下段が長くなりすぎたら打ち切る」が効いたのは、下段が一旦短くなるからかもしれない。

Stage 6

解けません。 いや、解けないとか、あるいは未解決問題だとか、ありえると思ったんだよな……。 でも、「もしかしたら解けるかも」で随分と時間を溶かしてしまった。 証明は後述。

ポストの対応問題

このパズルは「ポストの対応問題」の一種である。

en.wikipedia.org

ポストの対応問題は、例えば、次の各ピースを何回使っても良いので、上段と下段を一致させよという問題。

0   1   2
ab  bb  c
ba  b   bc

答えの一例として、 1002 と並べると、上段も下段も bbababc になる。

ポストの対応問題の文字を ab の2種類にし、下段の文字の ab を入れ替えると、Posting Puzzleになる。 「Posting Puzzle」という名前(と郵便ポストに入れるというアイデア)は、このポストの対応問題からでしょう。 ちなみに、ポストの対応問題のポストは、郵便ポストではなく人名である。

ポストの対応問題は、決定不能問題(その問題を解くようなプログラムが存在しない問題)として知られている。 Stage 6のような解けない問題があると言っているわけではなく、解けるかどうかを判定するという問題が解けない。 「そんなの証明できるの?」と思うかもしれないが、証明されている。 問題の表現力が高く、もし解くプログラムが存在するならそのプログラムを埋め込んだ問題が作れて、なんやかんやできる……と私は理解している。

決定不能問題に興味があるなら、このサイトがおすすめ。

iso.2022.jp

で、文字種が2種類のポストの対応問題で、ピースの数やピースの幅が少ないものについて、解けるかどうかや最短手数を網羅的に調べていた人達がいた。

Stage 4は、ピースが3個で、各ピースの最大幅が3の最も手数の掛かる問題である。

Stage 5は、上のリストには載っていないが、Internet Archiveに残っているページに載っていた。

https://web.archive.org/web/20060205173553fw_/http://www.theory.informatik.uni-kassel.de/~stamer/pcp/pcp3en.html

ピースが3個で、各ピースの最大幅が4の最も難しい問題の候補だろうか。 この時点で、452手で解け、340手以内では解けないことが分かっているっぽい。 最短手数が何手かはまだオープンな問題かもしれない。

Stage 6は、この文献に解けないことが証明されたと書かれていた(ここでの「solved」は解けないことが示せたの意)。しかし「Unpublished manuscript」。

https://webdocs.cs.ualberta.ca/~mmueller/ps/jea.pdf

証明が気になるけど、publishされたmanuscriptが見つからない……ということで、Rahnさんにメールで訊いた。

20年前の話だし、スルーされるか、「もう忘れたよ」かと思ったけど、すごく丁寧に教えてくれた。 ありがとうございます。

メールの文章や、送ってもらった論文を転載するのは憚られるけど、証明自体は、公開されているRahnさんの博士論文の42ページにも載っているとのこと。 ドイツ語だけど。

https://publikationen.bibliothek.kit.edu/1000009979/614948

概略。

ピースの左右を逆にした問題を考えると、AかBのパターンが必ず出てくる。 そして、AかBのパターンの後には、必ずAかBのパターンが出てくる。 よって、このパターンは消えることが無く、この問題は解けない。

「AかB」という2種類のパターンがあるのがミソである。 BBBBBB...やBAAAA...などがありえるので、AかBどちらか一方のパターンのみを考えていては、解けないという証明はできない。 そう、1個のパターンを使う方法は思いついていたんだよな……。 でも、色々なパターンを試してみても、どうしてもパターンが消えてしまうパスがあって困っていた。 Stage 6を自力で解けたり、解けないことを証明したりできなかったのは悔しいが、証明が分かってすっきりした。

MC Digital プログラミングコンテスト2023(AtCoder Heuristic Contest 019)参加記

atcoder.jp

github.com

暫定: 27,428,379,227点、26位

システムテスト: 1,128,435,184,437点、24位。

アルゴリズム:

  • 各ブロックのそれぞれのオブジェクト内の始点と方向を入力とし、シルエット外に出ないように、ブロックを広げていく処理を作る
    • 1個のブロックを広げるだけ広げてから次のブロックに行くのではなく、順番に1個ずつ広げていく
      • スコア計算的に、少数の大きなブロクがあるよりも、最小のブロックが大きいほうが良いので
    • 各ブロックでも深さ優先ではなく幅優先的に広げていく
      • 線上ではなく球状にするイメージ
      • 深さ優先ではないほうを試したわけではないが、このほうが良いだろう、たぶん
    • 両方のオブジェクトで別々に向きを指定する意味は無い(左側で90度回転したいなら右側で回転すれば良い)と思うかもしれないが、両方で指定している
      • ブロックを広げていく方向は固定なので、向きを変わればちょっと結果が変わりそう
    • 広げられるブロックが無くなってもシルエットが埋まっていなかったら1x1x1のブロックで埋める
      • でも最終結果にこの片方にしかないブロックが出てくることはほどんどない
  • この処理に渡す、始点と方向のリストを焼きなまし
    • 近傍
      • ブロックを1個追加する
      • ブロックを1個削除する
      • いずれかのブロックのいずれかのオブジェクト中の位置をランダムに選び直す
      • いずれかのブロックのいずれかのオブジェクト中の位置をランダムに±1動かす
      • いずれかのブロックのいずれかのオブジェクト中の方向をランダムに変える
      • ブロックの順番をスワップ
        • 1個ずつ広げていくとはいえ順番があるので、順番にも多少は意味がありそう
      • ブロックの順番を片方だけスワップ
        • 2個のブロックの両方のオブジェクトでの対応関係を交換するということ
        • 説明が難しい……が、たぶんそんなに効いていないので、どうでも良い

seed=0とseed=1の結果は次のようになった。

以降はコンテスト中に考えたことを適当に書き連ねる。

seed=0について

体積7, 9, 9, 9のブロックで作るこれが、たぶん最適解。

取り組み始めたのが遅かったけど、共有される画像は見ていた。スコアの良い画像だと、こんな感じにブロックが層状になっている。これを見て「これは……焼きなましなどではなく、何らかの方針に沿ってブロックを作るゲームかな?」と思っていた。焼きなましで良い感じのスコアになったら、seed=0だけはこんな感じなったわ。共有画像を信じると危険。特にseed=0が特殊な入力の場合。

三面図なら簡単なので……

1個のオブジェクトの三面図が目的のシルエットになる問題なら、シルエットの無い部分を切り抜くだけである。でもこの問題は4面ある。うち2面を平面のブロックの組み替えで作れるようにして……。ということをプログラムを書く前は考えていた。上述の共有されていたseed=0の画像がそんな感じだったし。この方針はいけるのだろうか?

高速化

始点と方向を受け取って立体を作る処理は、6秒の間に10万回~200万回くらい実行できている。最初に書いた方法でブロックを広げていくとき、シルエット外だったりすでに他のブロックがあったりで広げられなかった場所は二度と広げられない。各ブロックのどのマスまで、また6方向のうちどの方向までをチェックしたかを覚えておくと速くなった。

近傍の選択確率

とはいえ、焼ききれておらず、実行時間を伸ばせば伸ばすだけ結果が良くなる。ということは、どの近傍を選ぶのかが重要なはず。

どの近傍をどの確率で選ぶかはOptunaで探索した。後述するように、たぶんちゃんと探索できていないけど。

固定の確率にしているけど、Dや入力生成方法のp、温度(進行状況)で最適な値は変わると思うんだよな。その種類の近傍を何回選んでスコアが何回向上したかを記録しておいて、向上する確率に応じて選ぶようにしてみたけど、結果は返って悪くなったのでボツ。近傍をどういう確率で選ぶべきかという話題をあまり見ない気がする。何か定番の良い方法は無いのだろうか。

スコアのブレ

この問題、ちょっとした運でスコアが大きく変わる。たまたま1x1x1のブロックができてしまったら、スコアが109も増えてしまう。

そんなに時間も無いので、手作業で確認するときは20ケース、Optunaで探索するときは100ケースで動かしていたけど、全然足りない感がある。良くなった……ような……気がする! ちょっと悪くなったけど……これは誤差かなぁ……とかやっていた。こんな状態でまともに改善できるわけがない。クラウドでテストを回すことを考えるべきかもしれない。

RECRUIT 日本橋ハーフマラソン 2023冬(AtCoder Heuristic Contest 018)参加記

atcoder.jp

github.com

暫定: 28,285,318,300点、121位

システムテスト: 1,739,788,605,739点、117位

アルゴリズム:

  • サイズを1/√2にしながら、格子点に試し掘りをする
    • 試し掘りをする場所は、前のサイズでの試し掘りの結果からルートを決め、そのルートの周囲
    • サイズを1/√2とかの話は後述
  • 最後に決めたルートを掘削ときは、直前のマスの頑丈さを一定の割合で減らしたパワーで掘削する
    • 掘れなかったら当然追加で掘削
    • なるべく頑丈さに近いパワーで掘削することが目的
  • 諸々のパラメタをOptunaで探索

17日(金)

コンテスト開始の前日。

このイベントに行って、本を買って読んだ。

connpass.com

gihyo.jp

ヒューリスティックコンテストのために買おうとしている人への注意として、これは「探索アルゴリズム」の本であり、ヒューリスティックコンテストだけの本ではない。 ゲームAIの話も多いので、全編ヒューリスティックコンテストの話だと思っていると「あれ?」となるかもしれない。 とはいえ、ちゃんとヒューリスティックコンテスト向けの話もある。

問題を分類してそれぞれに使うアルゴリズムが解説されており、「実践」だからソースコードもしっかりと載っている。 明日のヒューリスティックコンテストでも、「この問題はどういう種類の問題なのかな?」と見分けて、該当するソースコードをコピペすれば、良いスタートダッシュが切れるだろう(フラグ)。

18日(土)

問題を読む。

これ、進研ゼミでやったところ……ではないw あー、未知の情報があるタイプの問題か。 未知の情報はこちらに敵対的というわけではないので、対戦ゲームともまた違うよね。

パーリンノイズって最近どこかで見たような……SECCONだ。

blog.arkark.dev

この問題は解いておらず、パーリンノイズの詳細を知らないのでまずは調べてみた。 このページが詳しい。

marupeke296.com

いくつかバージョンがあるらしい?

テスターで使われているのはこれで、上の記事の「改良パーリンノイズ」だろうか。

github.com

ソースコードに「procedural noiseに暗号論的乱数なんて要らないよ」みたいなことが書かれている。 テスターは乱数推測を防ぐためにちゃんと暗号論的乱数を使っているけど、ここは弱いのか。 たとえ暗号論的乱数を使っていたとしても、改良パーリンノイズではパターンが少ないらしい。 問題の入力生成方法 f0f1 が一定で dy0 とかが整数だったら何か所か採掘してパーリンノイズを当てるのも現実的だったかもしれん。

入力の段階ごとに出力しながら、 S を自前で計算してみた。

何かややこしいことをしているなと思っていたけど、なるほど、値の小さい領域が広くなるようになっているのか。

19日(日)

インタラクティブ問題で入出力がややこしいので、とりあえずテスターとの通信部分を実装し、サンプルプログラムと同じ(と思っている)アルゴリズムを実装した。

とりあえずサンプルプログラムを出している人は多いと思うのだけど、サンプルプログラムと思われる同じスコアの塊とは微妙にスコアが異なり、tek1031さんと同じスコアになった。 はて……。 まあ、すぐに書き換えるプログラムなので、気にする必要はないだろう。

8,449,216,639点。

どのくらい改善したのかが分かるように以降もそのときのスコアを書いていく。 相対スコアなので、減ったからといってプログラムが悪くなったとは限らない。 相対スコアの計算に使われる最高スコアが更新されているかもしれないから。

テスター経由で動かすのが面倒なので、テスターを内包し、インタラクティブではない問題と同様に、標準入力に入力を渡すだけで動くようにした。

fprintf(stderr, "%1d %2d %3d %.3f %6d %8lld\n", W, K, C, time, n, score);

のようにスコアなどを標準エラー出力に出力し、

set -e

g++ -O2 A.cpp -o A
for i in $(seq 0 99)
do
  f=$(printf %04d.txt ${i})
  echo -n "${f} "
  ./A < tools/in/${f} > output/${f}
done

こんな感じのシェルスクリプトで動かすと、

0000.txt 1  9   2 0.929   8728   890256
0001.txt 3  2   1 0.193   1804   182204
0002.txt 1  4  32 0.641   6088   803616
0003.txt 3  1   1 0.117   1157   116857
 :

こういう出力が出てくる。 お手軽にスコアの傾向が見られて便利。

10マス間隔でパワー100で5回叩き、その結果から線型補間で頑丈さを予測し、ダイクストラ法で掘ってみる。

13,498,197,845点。

2日目の結果としては悪くないだろう。

21日(火)

どう考えても通らないところを試し掘りしているのは無駄。 最初は粗く試し掘りをして、その状態で経路を求め、通ったところを細かく試し掘りする……ということを繰り返して細かくしていくのが良いのではないだろうか。

赤いところを掘ってから、1/2に細かくして青いところを掘ると、赤の結果が使えず無駄である。 1/3に細かくすれば良いけど、ちょっと段階が開きすぎる気がする。

次の段階を斜め45°傾けることを思いついた。 天才か?

20,492,778,007点。

この記事を書いている今思いついたのだけど、単に位置をずらせば良いだけだった……。 補間の端の処理とか面倒だったのに。

そもそも段階的に細かくしていくというのはあまり良くなさそう。 パーリンノイズが2種類の周波数だけなので、大きなサイズでは少しだけ頑丈さに相関があり、小さくなるにつれて徐々に相関が上がっていくという感じにはならなそう。

22日(水)

今まで最後に掘削するときは、パワー100固定で掘っていた。 この100はサンプルプログラムそのままだけど、100が意外と良い感じ。 とはいえ、無駄は大きい。 頑丈さくらいの力で掘りたい。 隣のマスを掘ったときのパワーの合計に適当な定数を掛けて少し減らしたパワーで掘るようにした。 徐々にパワー減らし、掘れなかったら追加で掘るのでパワーが増えて、という感じで頑丈さの変化に追従してくれるはず。

23,562,994,313点。

この問題はパラメタ調整が難しい。 いつもは上記の100ケース動かした結果の一覧を見ながら適当に人力で調整していた。 この問題はたまたま経路が変化したことによってスコアが大きく変わってしまう。

Optunaを召喚。 パラメタ調整は C 別に行った。

そういえば、Optunaも本が出ていた。 買ったけどまだ読んでいない。 次のAHCまでには読みたい。

www.ohmsha.co.jp

28,810,425,261点。

23日(木)

今までは、家の順番は固定で、各家ごとに水場か今までに掘削した水路までの最短経路を求めていた。 家ごとに独立に計算するのではなく、複数の家を同時に考慮するともっと良い経路もあるよね。 良くある問題っぽいけど、探せない……。 頭の良いアルゴリズムを探すことは諦めた。 水場からダイクストラをして最初の家に到達したらその家までの水路を掘る。 距離をリセットして、水路の距離は0とし、ダイクストラをやり直して最初の家以外に到達したらその家までの水路を掘り……。 でちょっと良くなった。

28,277,377,437点。

提出した相対スコアは下がっているが、手元で実行したローカルスコアは良くなっている。

この家(と水場)を全部繋ぎたいなという問題はシュタイナー木と言うらしい。 コンテスト後の感想タイムラインで知った。 へー。 これを知っていたからといってスコアが大きく改善するわけでもなさそうで、まあ良かった。

ja.wikipedia.org

25日(土)

試し掘りを徐々に細かくしていくという方針に限界を感じる。 試し掘り後の水路を作る部分のパワーを完璧に調整できたとしても、上位陣に及ばない。

まず、全ての頑丈さが同じと仮定して最短経路を求めます。 最短経路上で得られる情報が多そうなところを試し掘りします。 頑丈さの予測値が更新されるので、最短経路も更新します。 という方針が良いのでは? と思い実装。 上手く動かない。 最初の最短経路の周りばかり無駄に掘る感じになる。 諦め。

これはこれで正解の方針だったっぽい。 ちゃんと実装していれば……というか、最初からこの方針を取っていれば……。

頑丈さの予測を、単なる線型補間ではなく、p 乗根を取ってから線型補完して p 乗してみる。 入力の生成方法的にこのほうが正しいはず。 p の値は分からないので、間を取って3。

ダイクストラ法で頑丈さに追加の値として C を加えていたけど、1回で掘れるとは限らない……というか、C が小さいときにはパラメタ探索で積極的に回数を増やそうとするので、ここも可変にしてみる。

26日(日)

もう思いつくことも無いので、適当にOptunaを回す。 Optunaのスコアが良くなっても、別のテストケースだと悪くなるので、過学習しているっぽいな。 W , K, C それぞれに10ケースずつ、合計3,200ケースで調整していた。 C 1個あたり400ケースだから、まあ足りないか。 C ごとの各パラメタの値を見比べ、おかしそうなところを適当に人力で変更して最終提出。 もうダメ。

28日(火)

システムテストの結果を見たら、WAが3個、TLEが7個。 なんで??? 試し掘りをするところに家があったりとかのパターンだとは思うのだけど、システムテストでこれだけダメなら、確率的に手元で動かしているときにも起こったと思うんだよな……。 テスターを組み込んだ版でずっと動かしていたからWAの見逃しはありえるにしても、TLEが謎。

色々ダメだったので、次回は頑張ろう。