1202バイトの Lazy K FizzBuzz をほとんど理解しないまま1117バイトに縮めた話(ネタバレ)

Anarchy Golf で長らく最短記録の座にあった rst76 さんの1201バイトの Lazy K FizzBuzz が公開されているのを見つけました。

https://github.com/rst76/Lazy-K/blob/master/fizz_buzz.lazy

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K`SK)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`
K(SS(SSSS(SS`SK))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S
`KS(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(S
S`SK))(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K`SK)
`KI)))))))(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`
S`KS(S`K`S`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K
`SK))))`K`KI)))))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS
(SS(SSS))))(SS`SK))S(S`KSK)))))))`KK)))))`SK))))`KI)(S(S(S`K
S(S`K`S`K(S`KSK)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K
(S`K`S(SI`K(S(S(S(SSS)(SS`SK))S)(SSSS(SS(SS`SK)))(S`KSK)))K)
(S`K`S(SI`K(S(S(S(SS(SS(SSS)))(SS`SK))S)(SSSSSS(SS`SK))(S`KS
K)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K`SK)K))(SII))))))`KK))
)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(SS(
SS(SSSS(SS(SS`SK))))(S`KSK)))K)(S`K`S(SI`K(S(S(SS`S(SSS)(SS`
SK))S)(SSSSSS(SS`SK))(S`KSK)))K)))(S`KK(S`K(SII(S(S`KSK)I)(S
`K`S(SI`K`SK)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI`K(SS(S(
SS`SK)(SS(SS(SSSS(SS`SK)))))(S`KSK)))K))))(S`K`S`K`S(SI`K(SS
(SSSS(SS`SK))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK
))))))))`K`K(S(SS`SK)(SS(SSSS(SS`SK)))(S`KSK)(S`K`SIK)`KK))I
)

これを、コードの意味をあまり考えずに、局所的な最適化だけで1117バイトに縮めました。

1. Jot記法

Lazy K では、 SKI 記法の他に Jot 記法という書き方ができます。 Jot 記法の詳細はさておき、`SK`KIと同じ意味を0の1文字で書けることが、 Lazy K 処理系のソース の353行目辺りを読んでみるとわかります。上記のコードには`SK`KIが合計26回使われていますので、これらを0に書き換えれば52バイト縮みます。

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K`SK)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`
K(SS(SSSS(SS`SK))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S
`KS(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(S
S`SK))(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K`SK)
`KI)))))))(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`
S`KS(S`K`S`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K
`SK))))`K`KI)))))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS
(SS(SSS))))(SS`SK))S(S`KSK)))))))`KK)))))`SK))))`KI)(S(S(S`K
S(S`K`S`K(S`KSK)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K
(S`K`S(SI`K(S(S(S(SSS)(SS`SK))S)(SSSS(SS(SS`SK)))(S`KSK)))K)
(S`K`S(SI`K(S(S(S(SS(SS(SSS)))(SS`SK))S)(SSSSSS(SS`SK))(S`KS
K)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K`SK)K))(SII))))))`KK))
)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(SS(
SS(SSSS(SS(SS`SK))))(S`KSK)))K)(S`K`S(SI`K(S(S(SS`S(SSS)(SS`
SK))S)(SSSSSS(SS`SK))(S`KSK)))K)))(S`KK(S`K(SII(S(S`KSK)I)(S
`K`S(SI`K`SK)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI`K(SS(S(
SS`SK)(SS(SS(SSSS(SS`SK)))))(S`KSK)))K))))(S`K`S`K`S(SI`K(SS
(SSSS(SS`SK))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK
))))))))`K`K(S(SS`SK)(SS(SSSS(SS`SK)))(S`KSK)(S`K`SIK)`KK))I
)

↓(-52 Bytes)

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0))
)))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS(SS(SSS))))(SS
0))S(S`KSK)))))))`KK)))))0))))0)(S(S(S`KS(S`K`S`K(S`KSK)(S(S
(SI`K(SI`K0))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)
(SS0))S)(SSSS(SS(SS0)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SS(SS(SS
S)))(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`
K`S(SI`K0)K))(SII))))))`KK)))(S(S(SI`K(SI`K0))`K(SII(S`K`S(S
I`K`S`K(S`K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0))))(S`KSK)))K)(S`K`
S(SI`K(S(S(SS`S(SSS)(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(
S`K(SII(S(S`KSK)I)(S`K`S(SI`K0)K))(SII))))))`KK))`K(S(S`KSK)
I(S`K`S(SI`K(SS(S(SS0)(SS(SS(SSSS(SS0)))))(S`KSK)))K))))(S`K
`S`K`S(SI`K(SS(SSSS(SS0))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)
))`K`S(S`KSK))))))))`K`K(S(SS0)(SS(SSSS(SS0)))(S`KSK)(S`K`SI
K)`KK))I)

2. 数値の表現の短縮

コードにSS(SS(SS(SSS)))という部分があります(ちなみに、これは1桁の数値に48('0'の文字コード)を加えて数字に変換しているコードの一部分です)。ところで、試しに括弧を全て取り除いたSSSSSSSSSというものをひたすらβ簡約してみると、先程のSS(SS(SS(SSS)))に戻ることがわかります。よって、この部分は単にSSSSSSSSSと書くことができて、6バイト縮みます。

同様に、SS(SS(SSS))という部分(これはチャーチ数の105('i'の文字コード)を生成するコードの一部分です)もSSSSSSSで良いので、4バイト縮みます。

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0))
)))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS(SS(SSS))))(SS
0))S(S`KSK)))))))`KK)))))0))))0)(S(S(S`KS(S`K`S`K(S`KSK)(S(S
(SI`K(SI`K0))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)
(SS0))S)(SSSS(SS(SS0)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SS(SS(SS
S)))(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`
K`S(SI`K0)K))(SII))))))`KK)))(S(S(SI`K(SI`K0))`K(SII(S`K`S(S
I`K`S`K(S`K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0))))(S`KSK)))K)(S`K`
S(SI`K(S(S(SS`S(SSS)(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(
S`K(SII(S(S`KSK)I)(S`K`S(SI`K0)K))(SII))))))`KK))`K(S(S`KSK)
I(S`K`S(SI`K(SS(S(SS0)(SS(SS(SSSS(SS0)))))(S`KSK)))K))))(S`K
`S`K`S(SI`K(SS(SSSS(SS0))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)
))`K`S(S`KSK))))))))`K`K(S(SS0)(SS(SSSS(SS0)))(S`KSK)(S`K`SI
K)`KK))I)

↓(-10 Bytes)

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0))
)))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SSSSSSSSS)(SS0))S(S
`KSK)))))))`KK)))))0))))0)(S(S(S`KS(S`K`S`K(S`KSK)(S(S(SI`K(
SI`K0))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)(SS0))
S)(SSSS(SS(SS0)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SSSSSSS)(SS0))
S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K0)
K))(SII))))))`KK)))(S(S(SI`K(SI`K0))`K(SII(S`K`S(SI`K`S`K(S`
K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0))))(S`KSK)))K)(S`K`S(SI`K(S(S
(SS`S(SSS)(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(SII(S(
S`KSK)I)(S`K`S(SI`K0)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI
`K(SS(S(SS0)(SS(SS(SSSS(SS0)))))(S`KSK)))K))))(S`K`S`K`S(SI`
K(SS(SSSS(SS0))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`K
SK))))))))`K`K(S(SS0)(SS(SSSS(SS0)))(S`KSK)(S`K`SIK)`KK))I)

3. その他

(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0)という部分がありあすが、これは(S`K`S(S(SI`K0)`K0)(S(SII)`K0))で良くて、10バイト縮みます。(ちなみにこれは、数値を文字列に変換するときに、10で割った商が0か判定して分岐している所です。 ifnonzero(Scheme版)とか ifnonzeroNXY(rst76さんのHaskell版)というマクロを使うと (ifnonzero n x y)n(Kx)y に展開され、さらにT変換されて前者のようなコードになりますが、今回はy=Iなので、n(Kx)Iとせずとも(n0)0xで十分です。あまり変わっていないように見えますが、T変換すると後者の方が短くなります。)

(SI`K(SI`K0))という部分が2か所ありますが、これは1か所にまとめることができます。関連する箇所の差分を明示しにくいですが、結果的に6バイト縮みます。

(S`K`S`K`S(S`K`S`KK))(S`K`S`K(S`K`SK))にできて、4バイト縮みます。(これは、改行文字の後に次の行を cons する所で、 consXY マクロではなくて consX マクロを使うことで得られます。)

コード末尾から5文字目辺りの`KKKで良くて、2バイト縮みます。(これは、ループカウンタが100になったときに、出力文字列にチャーチ数として解釈できない文字を入れることでエラー終了させるためのものですが、そのためにはKで十分です。しかし、ループの判定をif<=マクロを使って書くと、最短でも`KKになってしまうので、気付きにくい(気付いても修正が面倒)です。)

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0))
)))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SSSSSSSSS)(SS0))S(S
`KSK)))))))`KK)))))0))))0)(S(S(S`KS(S`K`S`K(S`KSK)(S(S(SI`K(
SI`K0))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)(SS0))
S)(SSSS(SS(SS0)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SSSSSSS)(SS0))
S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K0)
K))(SII))))))`KK)))(S(S(SI`K(SI`K0))`K(SII(S`K`S(SI`K`S`K(S`
K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0))))(S`KSK)))K)(S`K`S(SI`K(S(S
(SS`S(SSS)(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(SII(S(
S`KSK)I)(S`K`S(SI`K0)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI
`K(SS(S(SS0)(SS(SS(SSSS(SS0)))))(S`KSK)))K))))(S`K`S`K`S(SI`
K(SS(SSSS(SS0))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`K
SK))))))))`K`K(S(SS0)(SS(SSSS(SS0)))(S`KSK)(S`K`SIK)`KK))I)

↓(-22 Bytes)

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S`K`S(S(SI`K0)`K0)(S(SII)`K0))))))`K`K(S(
S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SSSSSSSSS)(SS0))S(S`KSK))))))
)`KK)))))0))))0)(S`K(S(S(S`KS(S`K`S`K(S`KSK)(S(SI`K(SII(S`K`
S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)(SS0))S)(SSSS(SS(SS0)))(
S`KSK)))K)(S`K`S(SI`K(S(S(S(SSSSSSS)(SS0))S)(SSSSSS(SS0))(S`
KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K0)K))(SII))))))`KK))
)(S(SI`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0
))))(S`KSK)))K)(S`K`S(SI`K(S(S(SS`S(SSS)(SS0))S)(SSSSSS(SS0)
)(S`KSK)))K)))(S`KK(S`K(SII(S(S`KSK)I)(S`K`S(SI`K0)K))(SII))
))))`KK))`K(S(S`KSK)I(S`K`S(SI`K(SS(S(SS0)(SS(SS(SSSS(SS0)))
))(S`KSK)))K)))(SI`K(SI`K0))))(S`K`S`K(S`K`S(SI`K(SS(SSSS(SS
0))(S`KSK)))K)(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))))`K`K(S(SS0
)(SS(SSSS(SS0)))(S`KSK)(S`K`SIK)K))I)

(1117 Bytes)

yukicoder No.5003 物理好きクリッカー 参加記

問題

No.5003 物理好きクリッカー - yukicoder

クッキークリッカーを少し複雑化させたようなルールのゲームにおいて、所定のターン終了後に手持ちのクッキーの数を最大化する問題です。

25日間のマラソンでした。最終的に1位で終えることができました。

考察1

第一感、この問題の本質は、買い物(施設の購入、施設の強化、クリックの強化)の順序を最適化する所にあります。

そして、テストケースごとに異なるのは、たまに(100~200ターンに1度)発生する特殊効果だけです。その他、総ターン数とか価格とかの条件は全く同じです。

ところで、特殊効果って、買い物の最適な順序にあまり影響しないのではないでしょうか? ということは、買い物の順序は決め打ちでいいのではないでしょうか?

というわけで、ローカルでテストケースをいくつか生成して、合計点が高くなるように、買い物の順序を山登りで最適化しました(本当は焼き鈍しというのがしたかったのですが、お察しください)。

山登りで最適化した買い物の順序をコードに埋め込んで提出したのが、次の提出4回目です。

提出4回目

https://yukicoder.me/submissions/301436

C / 3,211 Bytes / 449 ms / スコア 312,529,669,165

上述のとおり、買い物の順序は完全固定です。決められた物を、決められた順序で、買っていくだけです。コード5行目の

char acts[]="AABBBBBDCBB ... ";

というのが買い物の順序のデータで、Aはクリックの強化、Bは設備 hand の購入、などと決めてあり、これを先頭から順に消化していきます。実行時に判断しているのは、

1. 次の買い物をするか、しないか。(次の買い物をすると元が取れなそうだと思ったら、それ以降は買い物を一切しない。)

2. 次の買い物をするとして、定価で買うか、セールまで待つか。(基本は単純な利得比較、ただし早く買うのを有利にするヒューリスティックを少し加味。)

の2点だけで、探索は全くしていません。

なんと、これだけで312e9点も取れてしまいます。

考察2

上記の提出では、買い物の順序を1通りに定めていますが、実行時間はたっぷり余っているので、何通りか試してもいいのではないでしょうか?

そこで、ローカルで50個のテストケースを作り、それぞれ山登りで買い物の順序を最適化してみたところ、意外にも、全部異なる結果になりました。思っていたより、特殊効果は買い物の最適な順序に影響していそうです。

提出7回目

https://yukicoder.me/submissions/302542

C++ / 14,405 Bytes / 150 ms / スコア 317,761,005,802

埋め込んだ50通りの順序を全部試して最も良いものを選ぶようにしました。それ以外は、先のコードとほとんど同じですが、スコアにかなりの改善が見られました。

実行時間がむしろ短くなりましたが、その理由については後述します。

考察3

50通りの順序を試すようにしましたが、まだまだ実行時間に余裕があります。そこで、これらの順序を包含する範囲のようなものを考えて、その中で探索をさせてみようと考えました。例えば、買い物を100回した時点では、ローカルのどのテストケースでも、設備 hand の購入は20回以上27回以下行われていますので、それを探索範囲とします。これを、全ての買い物回数について何を何回以上何回以下というテーブルを作って、コードに埋め込みます。

提出10回目

https://yukicoder.me/submissions/303306

C++ / 19,795 Bytes / 3,205 ms / スコア 329,229,387,323

実行時間と引き換えに、スコアがかなり改善しました。

探索方法は、幅優先探索です。ただし、複数の経路で買った物の数が同じになった場合は、最もスコアの良いものだけを残すようにしています。これにより、探索の状態数の上限は、上述の探索範囲によって規定され、テストケースに依存しないはずです。なお、スコアは、単純に、買い物を今後一切しないと仮定したときの最終クッキー数の大まかな見積りです。

考察4

提出用に範囲付きの探索を実装したので、ローカルで山登りの代わりにこの範囲付きの探索を利用して順序の精度を上げました。具体的には、範囲を少し広げて全ケースを再探索→結果を集約して範囲を更新、を何回か繰り返しました。

提出11回目

https://yukicoder.me/submissions/305186

C++ / 19,900 Bytes / 9,267 ms / スコア 330,658,005,177

ちょっとパラメータ調整をしただけのつもりなのに、実行時間が9秒を超えて、ひやっとしましたが、ともあれ少し改善しました。

これが最終提出となりました。

結論としては、「ローカルで山登り+幅優先探索」+「サーバで幅優先探索」ということになりました。

視覚化

f:id:saito_ta:20181225103338p:plain

視覚化

上の画面は、横軸に買い物の回数、縦軸(下向き)に個別の物(AとかBとか)を買った回数をプロットしたもので、縦の幅がその時点での探索範囲に相当します。どのテストケースでも大体同じような傾向になるという当初の予想が確認できました。

未考察の事項

買い物の順序はかなりちゃんと探索している一方で、セールを待つか否かの判断はぞんざいで、最初に変なヒューリスティックを導入したまま、最後まで改善できませんでした。

あと、買った物で売れる物を最後に全部売るようにしていますが、本当は全部売らないで一部残した方が良いはずです。というのも、売れるものは100個を超えます。100個の物を売るには100ターンかかりますが、終了100ターン前に何かを売るより、それを売らずに100ターン持っておいた方が良いからです。しかし、これは結果に与える影響が無視できるほど小さいのではという推測のもと、ちゃんと考察しませんでした。

余談:入出力と速度について

提出7回目 (150 ms) で実行時間が短くなったのは、ジャッジから特殊効果のデータを読み終えた時点で close(0) を呼んで標準入力を閉じ、それ以降のジャッジからのレスポンスを無視できるようにしたからです。その前の提出4回目 (449 ms) では、クエリを出力するたびにレスポンスを読み捨てていたのですが、これだと解答プロセスとジャッジプロセスが交互にしか動かないため、遅くなっていました。標準入力を閉じると、ジャッジ側に SIGPIPE が発生してしまうようにも思えますが、 yukicoder では「リアクティブ問題で出力を投げっぱなしでもAC」という仕様がアナウンスされていますので、入力を閉じてしまっても(入力を読まずにプロセスを終了するのと大差ないので)問題ないようになっているはずだと推測でき、実際そのとおりでした。

No.3031 (物理学)長距離~教育的問題 解説

おことわり

サンプルが変更されたため、ここに書いた解法は、もはや通用しません。

問題

No.3031 (物理学)長距離相互作用の収束計算に関する教育的問題 - yukicoder

ある仮定の下、イオン結晶内のある点(座標の原点)の電位を求める問題です。

解説

電位は重ね合わせが成り立ちますので、各電荷から受ける電位の総和を求めることになります。

なので、厳密な証明は別として、直感的には、求める電位 \( V \) は、適当な係数 \( A, B, C, \dots, P \) を用いて

\( V = A\,\alpha_{000} + B\,\alpha_{001} + C\,\alpha_{010} + D\,\alpha_{011} + E\,\alpha_{100} + F\,\alpha_{101} + G\,\alpha_{110} + H\,\alpha_{111} \)
\( \quad \quad + \ I\,\beta_{111} + J\,\beta_{113} + K\,\beta_{131} + L\,\beta_{133} + M\,\beta_{311} + N\,\beta_{313} + O\,\beta_{331} + P\,\beta_{333} \)

と表せそうだと言えます。

(気分としては、これらの係数は、電荷の種類ごとの距離の逆数の総和と解釈されますが、実際にはそれぞれの総和は発散するため、厳密な解釈ではありません。)

ここで、原点から見た距離の対称性から、

\( B = C = E \)

\( D = F = G \)

\( I = J = K = L = M = N = O = P \)

が言えますので、

\( V = A\,\alpha_{000} + B\,( \alpha_{001} + \alpha_{010} + \alpha_{100} ) + D\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) + H\,\alpha_{111} \)
\( \quad \quad + \ I\,( \beta_{111} + \beta_{113} + \beta_{131} + \beta_{133} + \beta_{311} + \beta_{313} + \beta_{331} + \beta_{333} ) \)

とまとめることができます。

さらに、 \( \beta_{111} + \dots + \beta_{333} = -4( \alpha_{000} + \alpha_{111} ) \) という条件ですので

\( V = A\,\alpha_{000} + B\,( \alpha_{001} + \alpha_{010} + \alpha_{100} ) + D\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) + H\,\alpha_{111} \)
\( \quad \quad + \ I\,( -4( \alpha_{000} + \alpha_{111} ) ) \)

となります。

ここで、 \( A - 4 I \) を改めて \( A \) と置きなおす( \( H \) も同様)ことにより、

\( V = A\,\alpha_{000} + B\,( \alpha_{001} + \alpha_{010} + \alpha_{100} ) + D\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) + H\,\alpha_{111} \)

だけになります。

さらに、 \( \sum_{ijk} \alpha_{ijk} + \sum_{lmn} \beta_{lmn} = 0 \) という条件から、この左辺を \( - B \) 倍して上式の右辺に加え、 \( A, D, H \) を適宜置き直したことにすることで \( B\,( \alpha_{001} + \alpha_{010} + \alpha_{100} ) \) の部分を消し去ることができて、

\( V = A\,\alpha_{000} + D\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) + H\,\alpha_{111} \)

になります。

ここまで来れば、あとはサンプルで与えられている数値を代入して \( A, D, H \) の値を求めてやれば良くて、

\( V = - 2.324\,\alpha_{000} - 0.486\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) - 0.289\,\alpha_{111} \)

という式を得られます。あとはこれをお好きな言語で1行でコーディングして提出できます。

https://yukicoder.me/submissions/239962 (Perl, 54 bytes)

感想

というわけで、解くだけなら難しいアルゴリズムが必要なわけでもなく、★6はないなあというのが正直なところです。特に、サンプル4が追加されたことで、難易度がぐぐっと下がったように思います。

あと、このようなチャレンジ系の問題は、考える時間を24時間とか1週間とかもらえると嬉しい気がします。2時間で賞味期限が切れてしまうのは、もったいないです。

追記(2018/3/1)

出題当初はサンプルが3つあって、途中で1つ追加されて4つのサンプル(うち3つが線形独立)があったのですが、その後、サンプルが全部削除されてしまったようです。とか書いていたら新たなサンプル(元のサンプル1と実質同じ)が追加されたようです。そんなわけで、上で書いた解法は、サンプル数が足りないので、もはや通用しません。

No.620 ぐるぐるぐるりん 解説

問題

No.620 ぐるぐるぐるりん - yukicoder

所与の \( T, w, v, g_x, g_y \) に対して、

\( \left( \begin{array}c x_0 \\ y_0 \end{array} \right) = \left( \begin{array}c 1 \\ 0 \end{array} \right) \)

\( \left( \begin{array}c x_{t+1} \\ y_{t+1} \end{array} \right) = \left( \begin{array}{cc} v+1 & -w \\ w & v+1 \end{array} \right) \left( \begin{array}c x_t \\ y_t \end{array} \right) + \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

\( \left( \begin{array}c x_T \\ y_T \end{array} \right) = \left( \begin{array}c g_x \\ g_y \end{array} \right) \)

を満たし、かつ \( \sum_{t=0}^{T-1} ( u_{x,t}^2 + u_{y,t}^2 ) \) を最小化するような \( u_{x,t}, u_{y,t} \) を求めよ。

解説

\( M = \left( \begin{array}{cc} v+1 & -w \\ w & v+1 \end{array} \right) \)

と置きます。

満たすべき条件は要するに

\( \left( \begin{array}c g_x \\ g_y \end{array} \right) = M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) + \sum_{t=0}^{T-1} M^{T-1-t} \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

ということです。

\( M \) は拡縮と回転の合成変換となっており、拡縮倍率を表すスカラー \( s = \sqrt{(v+1)^2+w^2} \) と回転を表す行列 \( R = \left( \begin{array}{cc} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{array} \right) \) を用いて

\( M = s R \)

と表すことができます。

このうち、回転 \( R \) は \( \sum_{t=0}^{T-1} ( u_{x,i}^2 + u_{y,i}^2 ) \) の値に影響しませんから、

\( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) = R^{T-1-t} \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

と置くと、この問題の条件は

\( \left( \begin{array}c g_x \\ g_y \end{array} \right) - M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) = \sum_{t=0}^{T-1} s^{T-1-t} \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) \)

を満たし、かつ \( \sum_{t=0}^{T-1} ( u'_{x,t}^2 + u'_{y,t}^2 ) \) を最小化すると言い替えることができます。

これは、成分ごとに考えれば単なるスカラーの問題として解くことができて(*1)

\( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) = \cfrac{s^{T-1-t}}{\sum_i s^{2(T-1-i)}} \left( \left( \begin{array}c g_x \\ g_y \end{array} \right) - M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) \right) \)

となります。

あとは \( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) \) から \( \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \) を復元すれば完成です。

--------

(*1) 球と平面の接点の問題(原点 \( (0,0,0) \) を中心とする球が平面 \( ax+by+cz=d \) に接しているとき、その接点の座標を求めよ)の考え方で解くことができます。

感想

というわけで、ほぼ高校数学の範囲で厳密解を求めることができて、あとは具体的な数値を代入するだけですので、これで★4.5は過大気味ではないかとも思いましたが、実際に解けている人が非常に少なく、強い人も苦労しているようですので、競技プログラミング的には難しい問題のようですね。

No. 410 「出会い」ショートコード解説

はじめに

yukicoder コンテストで出題された問題 No. 410 「出会い」のショートコード(2016年8月13日現在)の解説です。

問題ページ: http://yukicoder.me/problems/no/410

ショートコード: http://yukicoder.me/submissions/110735

問題の概要

入力:

A B
C D

が与えられる(A,B,C,Dは整数)。(abs(A-C)+abs(B-D))*0.5 の値を出力せよ。

私の答案

tr - _|dc -e?sx?sy-d*vlxly-d*v+.5*p

35 bytes です。言語は Bash です。 tr と dc を呼び出しています。 dc は先日 yuki さんにお願いして導入してもらい、使えるようになりました。

dc とは?

逆ポーランド形式の無限精度の計算が行える卓上計算機」だそうです(出典: http://kazmax.zpp.jp/cmd/d/dc.1.html)。今日では、 RubyPython で精度を気にすることなく整数演算ができますが、かつて Perl の時代にはそういうわけにはいきませんでした。なまじっか Perl が使えてしまうせいで RubyPython を覚える気になれない私は、 dc にはまだまだお世話になっています。

コードの解説

まず、 tr - _ で、入力に含まれる - (マイナス)を全て _ (アンダースコア)に変換しています。これは、 dc の入力においては - (マイナス)は二項演算子であり、負号は _ (アンダースコア)で表すことになっているからです。(一方、出力においては負号は - (マイナス)です。つまり、 dc は自分が出力する数値を解釈できないという謎仕様です。)

次に、負号を変換した入力を dc に渡しています。 -e は perlruby の -e と同じで、スクリプトの直接指定です。そのスクリプトをトークンに分解すると、次のようになります。

? sx ? sy - d * v lx ly - d * v + .5 * p

? は、入力を1行読んで実行する、です。最初の ? で入力の A B が読まれ、次の ? で C D が読まれることになります。読まれた値は、スタックにプッシュされます。

sx は、スタックをポップして変数 x に格納する、です。最初の ? の実行後のスタックは A B ですので、 sx で x には B が入り、スタックは A だけになります。同様に、 sy で y には D が入り、スタックは A C になります。

- d * v という一連の命令が2回出てきます。 d はスタック先頭の値の複製、 v は(非負の)平方根です。つまり、スタック先頭の2つの値の差を2乗してその平方根を求めていますので、差の絶対値が得られます。

lx ly は、変数 x と y の値(つまり B と D )をスタックにプッシュします。

+ .5 * で、これらを足して 0.5 倍しています。 .5 *2 / のほうが短そうですが、デフォルトで商が整数になってしまうので、ここではうまくいきません。

p で結果を出力しています。

おわりに

解説の配信のとき、説明が必要っぽい雰囲気だと思ったので、書いてみましたが、いかがだったでしょうか。全く需要がない気もしますが、果たして最後まで読んでくれた人はいるのでしょうか。

gnupack 版 Emacs で IME の on/off に合わせてカーソルの色を変える方法

gnupack 版 Emacs とは

本家 GNU が配布している WindowsEmacs バイナリは、 IME が on のときに

  • 入力中の文字が画面に表示されない
  • C-x b などのキーシーケンスで b が IME に吸われる

などといった不具合があるため、日本語環境ではまともに使うことができません。(なお Emacs 自体が独自の辞書を備えた入力メソッド機能を内蔵しており、そちらを使えば上記の問題は起こりませんが、せっかく IME があるのだからそれを使いたいですよね。)

そこで、 gnupack というプロジェクトが、上記の問題を解決するパッチを当てた Emacs を独自にビルドし配布しています。これのお世話になっている人は多いと思います。私もそうです。

gnupack プロジェクト日本語トップページ - OSDN

(ところで、 gnupack が現在(2016年5月)単体で配布している最新の Emacs は 24.2 と若干古いのが気になります。今後も是非とも本家に追随するか、もしくは上記の問題を解消するパッチを本家に取り込んでもらうようにしてもらえると嬉しいです。なお Cygwin を含むフルパッケージのほうには Cygwin でビルドされた Emacs 24.5.1 が含まれているようですので、そちらを使えということかもしれませんが、 Emacs だけのために Cygwin を丸ごともう1セット導入するというのもなかなか厳しいものがあります。)

IME の on/off に合わせてカーソルの色を変える

例えば IME が on のときだけ Emacs のカーソルが赤くなるようにすると、とても快適です。これについて gnupack 版での設定方法を説明します。(なお MuleMeadow とは設定方法が異なります。また、以下の方法は本家 GNU 配布版 Emacs では使えません。)

やることは以下の3つです。いずれも ~/.emacs.d/init.d に書いておくといいと思います。

1.入力メソッドIME に設定

(setq default-input-method "W32-IME")

初期設定では default-input-method"japanese" に設定されているので "W32-IME" に変更します。この "W32-IME" という入力メソッド名は本家 GNU 配布版には存在しないものです。これを設定することにより、入力メソッドとして IME が使われるようになります。 C-\ (初期設定で toggle-input-medhod コマンドが割当てられている)を押して IME の on/off が切り替わるのを確かめてみてください。

2. [kanji] キーイベントの有効化

(global-set-key [kanji] 'toggle-input-method)

初期設定では [kanji] には ignore が割り当てられているので変更します。これを設定しなくても「半角/全角」キーを押せば IME の on/off は当然切り替わりますが、これを設定することにより、「半角/全角」キーを押して IME の状態を切り替えたときに、次に説明するフックが呼ばれるようになります。また [kanji] キーイベントは「半角/全角」キーを押したときだけでなく、例えば言語バーをマウスでクリックして IME の状態を切り替えたときなどにも発生するため、このときにもフックが呼ばれるようになります。

3.フックの登録

(add-hook 'w32-ime-on-hook (function (lambda () (set-cursor-color "#ff0000"))))
(add-hook 'w32-ime-off-hook (function (lambda () (set-cursor-color "#0000ff"))))

IME が on になったときと off になったときにそれぞれ呼ばれるフックです。ここでカーソルの色を変えています。上記では IME が on のときに赤、 off のときに青ですが、好みに応じて変更してください。

まとめ

以下のコードをあなたの ~/.emacs.d/init.d の最後にコピペして下さい。

(setq default-input-method "W32-IME")
(global-set-key [kanji] 'toggle-input-method)
(add-hook 'w32-ime-on-hook (function (lambda () (set-cursor-color "#ff0000"))))
(add-hook 'w32-ime-off-hook (function (lambda () (set-cursor-color "#0000ff"))))

幾何の問題

知っていればそのまんまですが、知らないと驚くと思います。(私は知らなかったので驚きました。ていうか、答えはわかっていますが解き方がわかりません。)

問題

\(t>0\) とし、点 \(P\) の座標を \((t,\dfrac{1}{2t})\) とします。

2点 \(A,B\) の座標をそれぞれ \((1,1),(-1,-1)\) とします。

このとき、 \(BP-AP\) を求めてください。

(\(BP\)は点\(B\)と点\(P\)との距離、\(AP\)は点\(A\)と点\(P\)との距離。その差を求めてください。)

解説

そうなのです!最初に「知っていればそのまんま」と書きましたが、「逆数のグラフが双曲線であることを」知っていれば、ということです。いや、ちっとも知りませんでした。

なるほど! \(\sqrt{b}-\sqrt{a}\) の形なので、有理化の要領で \(\sqrt{b}+\sqrt{a}\) を掛けたりしてみましたが、複雑化する一方でうまくいきませんでした。まるっと自乗してしまえばいいんですね。素晴らしいです。

解答

\[\begin{align}BP-AP &= \sqrt{(t-1)^2+(\dfrac{1}{2t}-1)^2}-\sqrt{(t+1)^2+(\dfrac{1}{2t}+1)^2} \\ (BP-AP)^2 &= \left(\sqrt{(t-1)^2+(\dfrac{1}{2t}-1)^2}-\sqrt{(t+1)^2+(\dfrac{1}{2t}+1)^2}\right)^2 \\ &= (t-1)^2+(\dfrac{1}{2t}-1)^2 + (t+1)^2+(\dfrac{1}{2t}+1)^2 \\ & \quad - 2\sqrt{\left((t-1)^2+(\dfrac{1}{2t}-1)^2\right)\left((t+1)^2+(\dfrac{1}{2t}+1)^2\right)} \\ &= (t-1)^2+(\dfrac{1}{2t}-1)^2 + (t+1)^2+(\dfrac{1}{2t}+1)^2 \\ & \quad - 2\left(t^2+(\dfrac{1}{2t})^2\right) \\ &= 4 \end{align}\]

よって \( |BP-AP| = 2 \) 。

\(t > 0 \) より \( BP-AP > 0 \) なので \( BP-AP = 2 \) 。

…ということのようです。合ってるかな?