ごりちゃんがゆく

競プロをするゴリラの精進記録

ゆるふわオンサイト#5-G Exponential Banana Game

writerしました。

www.hackerrank.com

以下ネタバレや解説の記事になるので、自力で解きたい人はご注意！


改行

改行

改行

はてなで改行たくさんいれるのどうするんだ

改行

改

行

改行

改行

こんなもんでいいか

裏話

writerしたとはいえ、ネタはほぼてんぷらさんの助言です

Grundy数やるだけだったゲーム問題を原案置き場に雑に置いといたのですが、

🍤「これGrundy数が0,1,2しかとらないことを利用して変なことできそう」

🦍「変なこと　なに！？」

🍤「先手がゲームに勝てるようにゲーム開始前にバナナをこっそり食べてしまう食べ方何通りありますか、とか」

🦍「うおおお」

というやりとりがあり、ごりちゃん作問してません。

こうやって問題って作るんだなと勉強になりました。

複数人で作問するとこういう貴重な経験ができるので楽しいです
ありがとうございます。

FO社に入ってゆるふわオンサイトの作問してくれる方募集中です。

裏話2

1ターンに B_i^j 本食べる設定にした理由はすごく雑で、Grundy数求めるときの遷移をlog回にしてシミュレーションを間に合わせようとしてたのでした
美しい性質があったとは知らずに...

裏話3

ちなみに

久しぶりに、ゴリラのゴリ太郎君とウホ次郎君はゲームで対決します！

と書いたのですが、これ何が久しぶりなのか伝わってない気しかしないです
(これが伝わった人がいたらかなりのごりちゃんファンだ...)

ゴリ太郎君とウホ次郎君は以前ゆるふわ#2 で対決していたのでした
こっちのほうがゲーム問題としてはとっつきやすいですのでぜひ
www.hackerrank.com

解説

さて、解説なのですが
ここにスライドがあるじゃろ

ざっくりはこれを見てくださいなんですけど
現地解説用に作ったスライドなので どうしてGrundy数がこのような値をとるのか？の証明的なものは書けてなかったです
ので書きます
コンテスト中は実験された方が多いのではないでしょうか
(証明もてんぷらさんが考えてくれたんですが難しかったのでかみ砕いています　間違いありましたらご指摘ください)

以下、現在のバナナの本数を x とします
バナナの本数が n のときの Grundy数を g(n) とします

B_i が奇数のとき

B_i^j は必ず奇数なので、バナナの数の偶奇は1回の操作で必ず反転します。
g(0) = 0 なので、 g(x) =x\mod 2 がそのままGrundy数になります。

B_i が偶数のとき

  • x \lt B_i のとき
    • j = 0しか選べないので、必ずバナナを1本ずつしか減らせず、 g(x) = x\mod 2 となります。
  • x = B_i のとき
    • j = 0 または j = 1 が選べます。食べれるバナナは 1 本または B_i 本です。これらの行動をしたときの Grundy数は g(x-1) = 1, g(x-B_i) = g(0) = 0 となり、これらの mexを取ると 2 になります。
  • x \gt B_i のとき
    • x - 1 \equiv x - B_i^2 \equiv x - B_i^4 \equiv \ldots \pmod{B+1} です
      • B_i^{2n} - 1 が必ず B_i + 1 で割り切れるんですね　すごい
    • 同様に、 x - B_i \equiv x - B_i^3 \equiv x - B_i^5 \equiv \ldots \pmod{B+1} です
    • つまり、すべての操作について、操作の結果残るバナナの本数を mod (B+1) で考えると、 x - 1 または x - B_i となります
    • これらをもとに数学的帰納法を適用することができます。
      • n \gt B_i となる n に対して、Grundy数は g(n) = mex(g(n-1), g(n-B_i)) により求まる
      • これを適用するとGrundy数の列は実際に (0,1,0,1,0,1, \ldots, 2) の繰り返しになることを確かめられる

結局、証明というか、キミの目で確かめてくれ！みたいになってしまった

writerコード

grundy_count() を O(1) で算出するところの実装がつらめでした
こういうのうまく書けるようになりたい
a以上b以下のときの何かの個数を求めたいときに f(b) - f(a-1) みたいにするのはやるやるですね

'''
想定解概要：
  ゲームの勝敗はgrundy数で求まる。
  grundy数の取り得る値が少ないことから、grundy数の値を持ってdpができる。
  grundy数はB_iが奇数のとき、
    0,1,0,1,0,1,0,1, ... となり、
  grundy数はB_iが偶数のとき
    (0,1,0,1,...,2), (0,1,0,1,...,2), ... となる (B_i + 1 周期)
'''

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

MOD = 998244353

# B_i = b の部屋で、バナナto本以下でゲームを開始したときのgrundy数が gとなるパターン数
def _grundy_count(b, g, to):
    if to < 0: return 0
    if b%2:
        if g==0:
            return (to+2)//2
        elif g==1:
            return (to+1)//2
    else:
        if g==2:
            return (to+1)//(b+1)
        elif g==0 or g==1:
            d,m = divmod(to, b+1)
            ret = d*b//2
            if m < b:
                if g==0:
                    ret += (m+2)//2
                else:
                    ret += (m+1)//2
            else:
                ret += b//2
            return ret
    return 0

# B_i = b の部屋で、バナナfr本以上to本以下でゲームを開始したときのgrundy数が gとなるパターン数
def grundy_count(b, g, fr, to):
    return (_grundy_count(b, g, to) - _grundy_count(b, g, fr-1)) % MOD

# dp[i] = これまでのgrundy数を累積した結果がiとなるパターンの数
dp = [1,0,0,0]
for a,b in zip(A,B):
    ndp = [0,0,0,0]
    for i in range(4):
        for g in range(3):
            ndp[i^g] += grundy_count(b, g, a-M, a) * dp[i]
    for i in range(4):
        ndp[i] %= MOD
    dp = ndp

print(sum(dp[1:]) % MOD)

ABC307-C Ideal Sheet の激ヤバコーナーケース

ABC Python

ゴリはABC-Cが解けませんでした。ぐぬぬ

atcoder.jp

問題概要

グリッドAとグリッドBを平行移動して重ねた結果、黒いマスがグリッドXと一致させることができるか？
グリッドA,B,X の縦横の大きさは最大10。

最初考えた方針 (WA)

30*30 の領域を用意して、(10,10) が始点になるようにAを固定する。
Bの貼り付け場所として (0,0) ～ (20,20) を試す。

図1

で、これのBの貼り付け場所 21 * 21 箇所それぞれについて、Xの始点も 21 * 21 箇所試すという方針を考えました。

Xの最大サイズは10なので、10離れた位置まで試しておけば大丈夫だろう、という考えでした。

激ヤバケースとは

コンテスト後にわかったのですが、たとえばこのようなケースが存在します。

激ヤバ

Aの右下が1マスだけ塗られていて、Bの左上が1マスだけ塗られていて、Xは左上と右下が塗られているケースです。

このケースだと、Aの始点とBの始点は縦横最大18マス離れてしまい、最初の方針では調べきれてないので落ちてしまいます

AC方針

50 * 50 の領域を用意して、(20,20) が始点になるようにAを固定する。
Bの貼り付け場所として (0,0) ～ (40,40) を試す。

図3

これのBの貼り付け場所 41 * 41 箇所それぞれについて、Xの始点も 41 * 41 箇所試す

これに直したらいけました

ACコード (コンテスト後)

Submission #42932589 - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307)

HA,WA = map(int,input().split())
A = [input() for _ in range(HA)]
HB,WB = map(int,input().split())
B = [input() for _ in range(HB)]
HX,WX = map(int,input().split())
X = [input() for _ in range(HX)]
c = sum(row.count('#') for row in X)

for si in range(41):
    for sj in range(41):
        Z = [['.']*50 for _ in range(50)]
        for ai in range(HA):
            for aj in range(WA):
                if A[ai][aj]=='#':
                    Z[ai+20][aj+20] = '#'
        for bi in range(HB):
            for bj in range(WB):
                if B[bi][bj]=='#':
                    Z[si+bi][sj+bj] = '#'
        zc = sum(row.count('#') for row in Z)
        if c != zc: continue
        def exist(xi,xj):
            for i in range(HX):
                for j in range(WX):
                    if Z[xi+i][xj+j] != X[i][j]:
                        return False
            return True
        for xi in range(41):
            for xj in range(41):
                if exist(xi,xj):
                    exit(print('Yes'))
print('No')

おわり

こんなの思いつかんわ
AGCだよAGC
解けた人は全員天才！！ (負け惜しみ)

「配列のすべての要素が条件を満たすならtrueを返す」関数に空の配列を渡したら？

アルゴリズム

今日のお話

こんなツイートが話題になっていましたね！

まあ～こうすべきだああすべきだといろんな議論がされていましたが、trueを返すのが正解 だよ、というのと、それについて自分なりの解釈を書こうと思います
ゴリゴリの論理よりは感覚的に理解できる記事を目指します

言い換えてみる

国語の問題っぽく考えてみます。

「配列のすべての要素が条件を満たすならtrueを返す」関数

とあるが、まず暗黙的になっている部分を補完すると

「配列を引数として受け取り、配列のすべての要素が条件を満たすならtrueを返し、それ以外の場合はfalseを返す」関数

と解釈します (これは異論ないよね) 1

で、「それ以外の場合」のところを言語化すると、「すべての要素が条件を満たす」の否定なので、「どれか1つでも条件を満たさない」となります。

どれか1つでも条件を満たさないならば false。

いうなれば 「条件を満たさないもの検出器」 2 を作りましょうというわけです。

真偽値が逆なのでちょっとややこしいですが、条件を満たさないものがあれば false、なければ true を返したいです。

で、この、「条件を満たさないもの検出器」に、空配列を与えたらどうでしょうか？
条件を満たさないもなにも、要素自体がないので、条件を満たさないものは当然ありません。
つまり、上の太字の部分に当てはめると trueが妥当 となります。

DPで考える (DPの超入門)

ちょっと別の解釈です。

たぶんこの記事を読んでいる方の多くは、これくらいの関数なら見た瞬間実装できる方だと思うので、わざわざDPを？と思ったかもしれません

が、これを実装するときに書くロジックはDPの考え方とほぼ変わりないはずなので、あえてDPとして解釈してみます。3

dp 配列を以下のように定義します

dp[i] := 配列の先頭i個までを見たときの途中経過 (true / false)

dp

たとえば、dp[2] は、引数配列 (Aとします) の先頭2個、つまり A[0]とA[1] まで見た時の途中経過です
最終的に求めたい答えは dp[N] です。(N は配列の長さ)

すると、以下のように遷移するはずです
※ f(A[i]) では、A[i] が条件を満たせばtrue、満たさなければfalseが返るとします

&&

dp[i+1] には、dp[i] と f(A[i]) の論理積 (&&) を入れれば良いとわかります 4

なぜ論理積 (&&) で良いかというと、先頭 i+1個までみた途中経過 dp[i+1] の求め方を真理値表にまとめると、下記のようになるからです。

dp[i] f(A[i]) dp[i+1]
true true true
true false false
false true false
false false false

途中経過 dp[i] も trueで、f(A[i]) も true のときに限って、dp[i+1] もtrueにしたいわけで、これは論理積がちょうど使えます。

さて、DPを解くのには、遷移だけでなく初期値を与える必要があるのでした。
このとき、dp[0] はどうあるべき？
と考えると、falseでは正しく動きません。
なぜなら、xとyの論理積 x && y を考えると、xか yどちらかが falseなら 結果もfalseとなってしまうからです。
つまり、 dp[0] が false だと仮定すると、dp[1] は A[0] の値に関係なく falseとなってしまいます。
これだとどんな配列が来ても結果がfalseになってしまい、まずいです。
ところが dp[0] が true だと、このDPのロジックはうまく動作します。
dp[0] とは、「配列の先頭0個までを見たときの途中経過」であったので、これは空配列を与えたときの結果といえます。
やはり、空配列を与えたときの結果は true が妥当だと確かめられました。

単位元

ある演算に適当にまぜたときに、計算結果に影響を与えない値のことをその演算の単位元と呼んだりします。5
今回の、論理積という演算における単位元は true です。
他にも、論理和では false、足し算は0、掛け算は1、minはINF、GCDは0、... など、いろいろあります。
x + 0 = x
で、xに0を足しても確実にxだよね、みたいなイメージです。
結合法則が成り立ってて単位元がある演算 (=モノイド) は、セグ木に乗ることでおなじみです！

おわり

読んでくれてありがとうございます！
ではまた！

  1. 配列じゃなくてiterableでいいじゃん、とかそういうのはぬきで　(もとの問題設定が配列って言ってるので)↩
  2. 575↩
  3. DP配列を陽に持つ必要がない、などの違いがありますね↩
  4. 実用的には、f(A[i]) の falseを検出した時点で falseを返すのが良いです　無理やりDPにしているのでこうなっています↩
  5. このへん感覚で理解しており、詳しくないので石を投げないで～↩

13年つきあった恋人と別れました

自分のこと

びっくりしましたね？
表題の通りです。
うち11年同棲してたので、事実婚とか、内縁の妻って言われる関係でしたかね。
字面で見てもとてつもないな。
詳細は胸に秘めておくことにして、人生のマイルストーンとして書き残します。

本編の前に

当ブログ名は「30歳で競プロに目覚めた霊長類のブログ」でしたが、この度「ごりちゃんがゆく」に変えました
理由はいくつかあって

  • 競プロはじめたのは30歳だったけどもう四捨五入すると30じゃないので
  • 競プロ以外のことも書くかもなーという気持ち

とかそんな感じです
変わらずご愛顧いただけるとうれしいです

では本編

かきます。有益な情報や面白い話はないのであんまり期待しないでください
さらっと書きます

なれそめとか

そんなものは書くわけがないが、
自分が23歳の時に初めてできた彼女でした
うれしかったなあ。舞い上がっていたなあ。
うん。

周りの人を傷つけた

そんなこんなで険悪な関係になっちゃった友人もいて、悪いことしたなと思っている。
一生の傷を負ったできごともあった。
同棲してからの話だが、彼女を守ろうとするあまりに両親を傷つけてしまうこともあった。
これらはすべて自分の立ち回りの悪さが原因だと思っていて、いろいろと学びになったし、反省している。
うん、さらっと書きすぎ。

同棲

25歳の時に就職したので、それとほぼ同時に親元を離れ、同棲を始めました。
彼女側の事情があったのでそれをくむ形で、「それなら一緒に住む？」とすごく軽い気持ちでしたね
将来どうしたいとか、全く考えていなかった。
お互い自分の空間とかは欲しかったので最初から寝室は別々でした。

結婚？

は、話は出ることはあれど、いろんな事情などがあり、結局しませんでしたね
まあこのへんの話は長くなりそうだからまたの機会に (そんなものはない)

競プロとのかかわり

私は30歳のときに競プロを始めました
彼女は競プロと無縁の人でしたが、理解は示してくれて、コンテスト中には話しかけないでいてくれました
青になったときは一緒によろこんでくれたわけではないが、すごいじゃんと言ってくれました
Twitterアカウント等では存在をにおわせないように細心の注意を払っていたので、この記事をみて、このゴリラに彼女がいたんだと初めて知る人も多いのではないでしょうか
(実は、いました、競プロ始める前から)

2人の関係

なんだかんだ基本的に仲は良かったとは思うものの、価値観の違いやささいなきっかけでもけんかすることがしょっちゅうありました
それで別れたい気持ちになることも数えきれないぐらいあったが、大体3日ぐらい経つと仲直りしていた。
変な関係だと思う。よくわからないと思う。
たぶんだけどお互いに弱さがあって、別れるという選択に移せなかったのもあったと思う。
本当に別れるべきタイミングも他にもいくつかあったと感じるが、結局「相手の事情」を汲んでしまい我慢をし続けてしまった。
今思えば、相手のことを本当に好きだったのではなくて、相手にやさしくしてあげている自分がなんだかんだで好きだったのではないかと思っている。
ここは、本当はどうしたかったのかいまもよくわからない。
とりあえず、私の根源的な価値観として、大事に思った人のことは一番大事にすべき、というのがあるので、自分を殺してでも、相手が喜ぶのであればそれで正解なんだろう、と自分を納得させることができていたのだろう。

背負っているもの

が、ありました。相手のプライバシーにかかわるので書けない。
自分が支えなきゃ守らなきゃというプレッシャーと、仕事で成果が出せないことの板挟みで病んでしまったこともあったが、それはそのとき言えなかった。

決断

ずっとがんばっていたけれど、いろいろな面で限界が来てしまいました。
13年たって、相手の事情を汲むことなく、初めて本気で突き放してしまいました。

罪悪感と、感謝

一度は最後まで添い遂げようと思ったぐらいの相手ではあるので、これでも最後までいられなかったことを悪くは思っている。
まあこの話は本人と散々したから、ここに書かなくても良いか。
でも、長い間ありがとう。
こんな理不尽な裏切りを赦してくれて、ありがとう。
自分も感謝されました。私のために我慢してくれて、ありがとう、って。
最後は感謝を伝えあって別れることができたのはよかった。

無駄な時間などなかった

無駄に歳だけはとってしまったが、13年という期間に無駄なんかなかったと思っている。
なんだかんだ楽しかった部分もあったし、幸せな部分もあった。
身をもって学んだ大切なことも、たくさんあった。
これらの歳月は、決して黒歴史とかではなく、糧とか、勲章みたいなものになっていくと、確信している。
きれいごとを言いたくて言っているのではなく、これは本当にそう。

念願の一人暮らし

が、いまはかなっています
36歳になって初めての一人暮らしだと、ツイートでは触れた気がしましたが、そんなわけがありました。
なにも背負わなくて良い解放感を、いまかみしめています。

ごりちゃんがゆく

ここまで読んでくれてありがとうございます！
人生いろいろですね。
痛みをかかえながらも、結局前を向いていくしかないので、前を向いてがんばっていきましょう！
では！！

ABC296-D M<=ab の解き方

ABC Python

先日コンテスト中に緑diffの問題が解けなくて悔しかったので、久々にブログ書いてみます！
どういう思考をたどれば解けた可能性があるのか振り返っていきます。

問題概要

問題のリンク
* 正整数 N, M が与えられる。
* 1 以上 N 以下の整数 a,b を選んだとき、 X=abの積がM以上になるようなものの中で最小の値を求める。
* そのような値が存在しなければ -1を出力する。

制約

  • 1 \leq N,M \leq 10^{12}

結構でかいので工夫が要りそうですね。
計算量を \sqrt{N} や \sqrt{M} ぐらいに抑えたい感じの印象です。

考察

視覚的なイメージ

abの積を扱うので、横a, 縦bの長方形を考えると視覚的にとらえやすい気がしました

図1

で、これがどうなってると良いかというと、面積がM以上になれば良いので、下図の青いらへんのゾーンに (a,b) を選べば良いです！

図2
M = abがボーダーなんですけど、 M = ab を変形すると b = \frac{M}{a} になって、反比例の式 y = \frac{a}{x} と形が一緒ですね。

aを固定する

で、図を描いてみたは良いが、これだけだとまだどこから手を付けて良いか分からなさがありますね
N*N 通り探索するのは範囲が多すぎる！
こういうとき片方を固定すると良いことがあるので a を固定して考えてみます
a の値が決まってれば、 ab \geq M を満たす最小の b だけ考えればよくなって、これって計算で求められそう！
実際に、そのようなb は \lceil \frac{M}{a} \rceil (天井関数) で求められます！

計算量をどうする？

aを固定すれば 最適なbが求まることがわかったところで、まだもう1ステップ考えることがあって、計算量の壁です！
このままだとまだ a を N 通り探索いなきゃいけない気持ちになりますよね。
どうしましょう！
(ここ普通に難しいと思った)
実は a と b は対等な関係なので、 a \leq b と仮定してよいです！ ( a \leq b としても一般性を失わない みたいな表現をされるやつ) です！
a \gt bとなったら探索を打ち切って良いのです！
a*b が大体 M なので、この仮定をいれることによって計算量が大体 \sqrt{M} になるはずです。

ACコード

こちらはコンテスト後に通ったコードです。

N,M = map(int,input().split())

INF = float('inf')
ans = INF
for a in range(1,N+1):
    b = -(-M//a)
    if b > N: continue
    if b < a: break
    ans = min(ans, a*b)

print(-1 if ans==INF else ans)

6行目の -(-M//a) はpythonで使える切り上げテクです！ (M を a で割ったあまりを整数に切り上げています)
とっさに使えると強いです！
8行目の break はTLEしないために大事です。

なぜ解けなかった？

まともな考察が踏めてませんでした　あたまがごりちゃん
Xの値を決めて約数を列挙するみたいな発想しか浮かばなくて沼ってました
間違った方針に行くとかなり沼るやつでしたね。。
こういうのを安定して解けるようになりたい。

おわり

冷えたけど、学びの多い良問でした！
青コーダーだけど ABC-D にも学びがある！

AHC011 参加記

AHC コンテスト参加記

書くか～～！ (書きます)
AHC011に参加しました！！

9日間のコンテストをどう戦ったか、時系列の日記形式で書いていきます！
これを書いてる今はコンテスト終了5日後ですが、メモやツイートを頼りに思考の流れを再現したいと思います。※最後まで書き終えたのはこれのさらに2か月後です 笑
(ぶっちゃけ結構筋がわるくて参考にはならないと思ってるんですが、頑張った証跡として残します)

1日目 5/28(土)

12時からのコンテストだったので、やる気満々、12時に待機しました。
まずは恒例のFA狙いですが、出力例1をコピーしただけの提出はWAに終わりました。
長期コンテストは1度提出すると30分提出できないんですよね。
30分で問題の理解や、ビジュアライザを試したり、ローカル環境を整えたりを目指しました。
幸い問題自体の理解は難しくなくて、概要はこんな感じです

問題概要


こんな感じのスライドパズルを解きます。
もとの図柄は、全域木だそうです。
盤面の縦横のサイズ N は6～10で、 T=2 \times N^{3} 回までスライドできます。
N が 6 なら 432 回、 N が 10 なら 2000 回ぐらいの規模感ですね。
最終的にできた最大の木のサイズが全域木でなければ、サイズが大きいほどスコアが良く、全域木ならば、手数が少ないほどスコアが良いです
特に、ちょうど手数T をかけて全域木を完成させた場合はスコアが 500000になります。

ふむふむ。

正のスコア

とりあえず12:30になったので正のスコアを取っておきます。
空白が左端ならば右に1マス動かし、そうでなければ左に1マス動かします。完璧です。
→ WA
どうやら左右を間違えたようです (てへぺろ)
30分待ちます
左右をなおしてAC。
順位表を見ると、ほとんどの人たちよりスコアが低かったです
あとで知ったのですが、無を出力することでもACできて、そのほうがスコアが良かったようです。

7.92M

さて、30分待ってる間なにもしなかったわけではないです。
スコアを評価するのは難しくありません。
UnionFindで、連結成分の大きさを調べることができます。
とすれば、TL3秒の間ランダムに動かしてみて一番良いやつを採用しましょう。
ここで工夫としては、基本的には4方向からランダムなのですが、直前の動きを打ち消す方向には動かない、を入れました
例: L の直後に R に動かない ...など
これにより 7.92M点を得ました。

これは13:30頃の順位表ですが、なんと6位でした！
しかし1ページ目に居られたのは初日だけでしたね......

はい。
初日は結局そんなところで、次のとっかかりを探しながらハンバーグを食べに行ったり、昼寝をしたり、ABCに出たりしていたようです。

ABC

記事とは関係ないのですが、21時からABCに出ていました。
1級昇級をかけた大一番だったのですが、こけてしまいました...

気を取り直して次へ。

2日目 5/29(日)

8.99M

ABC後で日付がかわったので2日目のところに書きます。
スコアの評価がおかしかったので直しました。
連結成分のサイズを評価していたのですが、閉路になってしまうと「木」ではないので、閉路は計算に入れなくしました。
これにより スコアがちょっと伸びました。
就寝。

12.3M

さて、我々のような多くの社会人には土日しか休みがありません (この記事を書いている社会人の皮をかぶったゴリラも例外ではありません)
貴重な日曜日！ということでやる気に満ち溢れていました
ヒューリスティック問題を解くときに、ぼくの好きなアプローチがありまして、ヒューリスティックの名が示す通りヒューリスティックな関数を定義してヒューリスティックにやるのです。
これが大好きなんです。
何を言ってるかわからないと思うのですがこんなことをしました
これまでランダムな方向に動かしていたのですが、ある種の貪欲法というか、状態にペナルティをつけて、そのペナルティが減る方向へ動かします。
ペナルティは、隣接するマスのbit状態が異なれば1、としました。
たとえばこういうのは、左のマスから右へ線が伸びているが、右のマスから左へ線は伸びていないため、状態が異なり、ペナルティ1です。

こういうのは左右で繋がっているのでペナルティなしです。

これも左右ともに線が伸びていないのでペナルティなしです。
これの各行各列の境目について合計して全体のペナルティを決めます。
なお、盤面の端に向かって伸びている線もペナルティ1としました。

こういう貪欲はたいてい局所最適におちいって最後はループを繰り返すんですが、どうせ全域木はできないので手数は関係ないです。。
これを時間いっぱい回し、スコアの一番高いやつを採用です。

これにより 12.3Mのスコアを得ました。
さらっと書きましたが実装は地味に重かったです。(1手動かしてみて差分計算して戻して、、ペナルティが一番低いやつをえらぶ)

さて、このようなヒューリスティックな方法って最終的なスコアに生きたことがないんですよね...
遠回りとわかっているのですが、やりたくなってしまいました。

ARC

記事とは関係ないのですが、21時からARCに出ていました。
ARC苦手なわりに結果が案外良くて、昨日の冷えがチャラになったどころか、1級昇級までニアピンになります。

AHCとは関係なく、翌日が月曜なのに興奮してなかなか寝付けませんでした。

苦悩の日々のはじまり

さて、日記形式で書こうとしていて悲しいことに気づきました
結論から言うと、これ以降、最終日まで提出がありませんでした。
めちゃめちゃ苦戦してしまいました。

3日目 5/30(月)

眠かったみたいです。
先に完成図を作れるか？というのを考えていました。
つまり問題を2つに分けます。
完成図を見つけるパートと、完成図に向かってスライドしていくパートです。
完成図を見つけるパートは、適当な2マスを選び、swapを繰り返す焼きなましでできたりしないかなあ、などと考えていました。

4日目 5/31(火)

スライドパズルの解き方、けんちょん本2 (下記リンク) にありました。
パズルで鍛えるアルゴリズム力 | 大槻 兼資 |本 | 通販 | Amazon
ここにヒントがあるだろと思い読み返していました。
実際パズルを解くパートでかなり役立ちました。
IDDFS や IDA* といった手法も紹介されていましたが、 N \ge 6 の規模ではさすがに3秒で解けないだろうと思い断念しました。

パズルをある状態まで並び替えるときに、上から1段目をそろえて、2段目をそろえて、...N-2段目をそろえて、次に左から1列目をそろえて、2列目をそろえて... とやると良さそうと分かりました。
これを実装することを考えていくと、少なくとも「あるタイルを目標とする位置へ動かす」という操作が必要になります。
下の図で、「A」というタイルを1つ左に動かすのには、DLLUR の 5手組の操作をすると良さそうです。

3つ左に動かす場合はこれを3回繰り返せば良く、また上に動かす場合は RUULD などと向きを変えれば良さそうです。

なんとなく、パズルを解くイメージが湧いたところで、1つ懸念が上がりました。
仮に全域木が焼きなましで見つかったとして、それを完成させるのに T=2 \times N^{3} よりも手数がかかりすぎてしまうのではないか？という懸念です。
すごく雑に見積もると、 N \times N 個タイルがあって、それぞれ最終的な完成図から Nマス離れていたときに、5手組の操作を N^{3} 回するので、 5 \times N^{3} 回の操作が要るのではないか？
しかもこれに加えて、動かしたいタイルの真横まで空きマスを動かすターン数もかかります。
これだと到底、揃えることができません。
完成図を見つけるパートと、完成図に向かってスライドしていくパートに分けたところで、スライドさせるパートで半分も完成しないのでは、あまりにお粗末です。
方針転換が必要です。

テストケースの生成方法に注目してみました。
要は、ランダムな全域木を生成したあとに、 T=2 \times N^{3} 回ランダムに動かして生成していると。
T=2 \times N^{3} 手で完成するのが保証されているのはもちろん、これだけのランダムムーブでは各タイルは元の位置からさほど動いてないものが多いのではないか？と考えました。
焼きなましをする際、適当な2タイルを選んでswapを考えていたのですが、これだと完成させるのに手数がかかりすぎてしまうと思い、これをやめて適当な1タイルを選んで8近傍とswapし続けることにしました。

とりあえずそんな方針で焼きなましを書きました。
近傍swapしたあとに全体をUnionFindで評価しなおしているので、無駄が多いかもな (というかUndo付きのUnionFindを使うべきかな) と考えたのですが、とりあえず αN^{2} のオーダーなのでひとまず許容しました。。
ちなみに焼きなましを書いたのは今回が2回目なのですが、もうばっちりでした。

↑初めて書いた焼きなましは去年の AHC006。じじいさんのおかげです。

温度とかのパラメータは手元で100ケースぐらい回し、を繰り返しつつ、良さそうなのを適当に決めました。
すると、全域木とまではいかないまでも平均的に 8割程度の全域木 ができました。

↑この頃はうまく動いたので、たのしい～～、という感情でした
この後に地獄が待っているとは知らずに...

5日目 6/1(水)

実装にハマっていたようです。
とりあえず焼きなましの精度を上げる必要もありますが、パズルを解くパートが完成しないことにはスコアも伸びないなと思っていたのでパズルを解くパートを頑張っていました


さっそくナイーブな気持ちになります。

6日目 6/2(木)

あと3日を切って泣きそうになっていたようです。

しかし体調が悪かったのでこの日は早めに休みました。

7日目 6/3(金)

とんでもない誤算を見つけてしまいます。

これは何かというと、ジャッジのテストケースが50ケースだったのを100ケースだと勘違いしていました
上位陣はすでに40Mほどのスコアをたたき出していましたが、ぼくはこの解釈を「全ケースで全域木を完成させてる人はまだ存在してない」と思っていました。
いやいや、彼らは「全ケースで全域木を完成させる」なんていう次元はとうに超えていて、すでにTの半分以下の手数で 手数を削る戦いをしていたのです！！
自分の状況はというと、焼きなましは8割全域木だし、パズルパートはまだ書けてなくて手数もTで足りないかもというレベルで、これでも全域木の6割の盤面ができるならば スコアは300000 の 100倍で 30M出るな、などとのんきなことを考えていました。
見積もりを改めなければ。
平均的に全域木の6割ができるならば 15M。現状からちょっと伸びた程度。
焼きなましで作った8割全域木が T ターン以内に解けたとしても、20M。
つまり現状の手札では、どんなに良くても20Mしか行かないのでは... と悟りました
ここまで苦戦を強いられていたとは。
しかし、他にアイデアもないし、とにかくパズルパートを完成させよう、そしてその先に何かが見えるかもしれない...
と信じて進むことにしました。
目標は漠然と30Mだったのですが、20M行けば良いだろうと、下方修正しました。

8日目 6/4(土)

ツイッターを見る限り、金曜は27:30 まで起きていたようです
が、待ちに待った土曜。気合を入れる。
パズルパートの実装にあたって、この手のルールベースは実装が地獄になりがちなので、一旦ホワイトボードなどを使って整理することにしました
1つ嬉しい性質に気づきました。
「A」というタイルを1つ上、1つ左のマスに動かしたいとします。
下のように、ULDLUR と動かすと、6手で「A」を2マス動かせます。

1マスあたり5手組の操作が必要と思っていたので、うまく動かす順番を工夫すれば1マスあたり3手になるのは、嬉しいです。
嬉しいっちゃ嬉しいのですが、動かしたいタイルと動かす先のタイルの位置関係によって、施策が変わるのは、実装がごちゃごちゃします。

これらを一般化する実装を考えました。
中の実装は省きますが、こういう関数を書きました。

def move_space_to_any(targets, to_avoids):
   # 多点bfsみたいな実装

空白マスを targets のいずれかに最も近づくように1マス移動させる、ただし to_avoids は踏まない
これを呼び出すとき、targets は動かしたいタイルに隣接するマスで、かつ動かす目的の方向と合っているものを指定します。
例えば「A」というタイルを左上の方向に動かしたいとき、とにかく「A」を左か上に動かしたいので、「A」の真左か真上に空白を持っていくことで、次の手で「A」を目的の方向に移動できるようになります。
(そのうち図を描きたい... (けどこれは描かないパターン><))
to_avoids には、すでに位置を確定させた (動かしたくない) タイルのリストを入れます。
詳細は省きますが、これを使うことで、6手で2手動かすのも、5手で1方向に1手動かすのも、区別のないコードで書くことができました！

末尾のつじつま合わせ

ところで、一番上段が 1 2 3 4 6 5 のように揃っているとき、 1 2 3 4 5 6 に直すのがかなり大変でした。

手でこの状態を解消してみたところ、17手かかりそうとわかりました。
私が見つけたのは 5 の真下に空白マスがある状態から、 ULDDRULURDDLURULD とやるととりあえず揃います^^;;
もっと良い方法があるかもしれません。
こういったケースなんかもコードに埋め込んでいます。

長いコードを書くとき、途中で「ありえない状態」になってないかを検知するため、assert 文をよく埋め込んでいるのですが、手元で100ケース回すと、いろんな場所で assert にかかっていて、要はバグり散らかしていた んですね。
残り24時間を切って、この状況、もうダメかも... なんて思ったりしました。

ABC

記事とは関係ないのですが、むしろこちらが本編という説があるのですが、21時からABCに出ていました。
現レート1799、レートが伸びれば1級昇級、伸びなければしばらくお預けの大一番でした。
結果としては大成功して、初の1800台、1級昇級を果たしました！

アルゴ青に到達してから3年半も彷徨っていたのですね。
何度水色に叩き落されたことやら... (12回のようです)
感涙。そして興奮。

最終日 6/5(日)

さて、ABCの興奮も冷めやらぬままに、まだまだやることがあります。
AHCの終了は19時です。
まずは目の前のバグ (先ほど見た大量に引っかかる assert ！) を解消せねばなりません。
ここはもう根性です。
ゴリは1級アルゴリズマーだぞという誇りを胸に戦います。

このようなケースで引っかかっていました
(あとで図をいれる)
(と書いてありましたがこれを編集してる今は8月でもう覚えていません...><)

14.7M

バグ取りをしてたら鳥がチュンチュン鳴き始めて、頭がおかしくなったようです。
気合と根性で、すべてのassert を取りました！
手元100ケースでも引っかからない。
上から N-2 行までを揃えるコードを書きました！
(実は下2行はまだ)
提出。14.7Mのスコアを得ました。
提出時刻は5:49。朝ですね。やっと眠れる。

15.6M

10時におきました。
普段7時間は絶対寝るんですが今日は4時間です。
カラダ持ってくれよ！！
というわけでやることがたくさんあります。
ひとまず、現状のコードは上から N-2 行までを揃えてみて、Tターンを超えていたらT文字で切る、という実装がされていました。
生成された操作列を最後まで終えた時がスコアの最大値ではなく、操作列の途中でスコアが極大になる可能性もあるなと思い、操作列ができた後に操作列のprefixを全部評価するようにしました。
オーダーは αN^{2}T ぐらいでボトルネックにはならないのでokです。
これにより 15.6Mのスコアを得ました。

17.7M

未実装となっていた下2行を左から揃えるパートを実装しました。
これにより 17.7Mのスコアを得ました。
結果的には上から揃えるやつのコードをほぼほぼ流用できたのでよかったですが、それでもタイルが逆転したときの解消が厄介で、結構時間を要しました。
あと、最後に残った2×2マスは、幅優先とかでも良かったのですが、時間がなかったので実装をサボって空白マスをぐるぐる回すだけにしました。
スライドパズルはそもそもパリティが合わないと絶対に揃わないという性質があるのですが、そこは割り切って右下の端がちょっと欠けても良いだろうぐらいに考えて、気にしませんでした。(詰めが甘い)

ちなみに、このときにseed=0 を共有していたのですが、これはうまく揃ったときのやつで、そもそもまだ焼きなましの結果は平均で全域木の8割程度だったので、本当に何を食ったら揃うのかわからん ってレベルでした。
それでもビジュアライザでこれだけ揃ったのは初めてだったので、ちょっとうれしかったです。
ちなみにこの日は 味の民芸の豚生姜焼き弁当を出前していたようです。

ボツ実装

残り7時間となりました。最後まで戦い抜きます。
焼きなましの評価のしかたにマイナーアップデートをしましたがいまいちでした。
どれぐらい連結してるか、みたいな指標をいれてみたようです。

22.0M

ここで大きな無駄を省くことに成功します。
現状は、焼きなましで作る完成図は8割ぐらい、ルールベースでそれを目指してスライドするパートも手数がかかりすぎて最後まで完成しない、って状況でした。
なにが無駄だったかというと、完成図のデータの持ち方です。
これまでは、各タイルをswapしていくときに、そのタイルが最初にどこにいたか を持っていました。
そして、焼きなましで完成図を作ったあとに、完成図の各タイルが最初にいた場所のタイルを律儀にその場所にスライドさせようとしていました。
これは大きな無駄があります。
タイルは15種類しかなくて、種類の出現数に偏りもありますが、同じ種類のタイルはたくさんあります
同じ種類のタイルは同一視したほうがよかった のです！
どこに最初にいたかは関係なく、最寄りのほしい形のタイルをスライドして持ってくる戦法にしました。
これで、手数には割と余裕をもって、焼きなましの完成図通りにスライドできるようになりました！
これで22.0M！
よくて20M、の見積もりだったので、少しほっとしました。

24.8M

焼きなましを改善したくなりました
タイルがもといた場所が重要ととらえていたので、隣接swapしかしてなかったのを、任意の2点をswapするようにしました。
感触はかなり良さそう！


何食ったら揃うか分からなかった全域木も、初めて完成しました！！
22.0M → 24.8M です！！
このとき、終了3時間前にせまっていました！
ありがとう豚生姜焼き弁当！

悪あがき

あと3時間となるとそんなに大きな改修はできません。
手ごろに伸ばせそうなところを考えます。
16:45 の提出では焼きなます前になにかしらの貪欲で配置してから始めることにしましたが、24.4Mで伸びず。
17:15 の提出で添字ミスを見つけて直すも、これも24.45M で意味なし。
18:00 の提出はもはやメモが残ってなくてなにをいじったか分からない。24.3M。
もとのコードに戻します。

最終提出

ラスト1時間は焼きなましのパラメータを色々いじってローカルで改善したやつを投げることをしました
意外と改善があって、 26.7M までいけました！！

記念のGIFも貼ります。意図通りに動いてくれてピッタリ揃う様子が動画で見れるの、気持ちいいですね！！

まとめ

システス後の結果は少し下がりましたが、153位でした。

全体的につらい戦いでしたが、最終日は根性でかなり追い上げました！
アルゴで1級昇級！をこの時期にできたのも根性を後押ししてたような気がします！
いつもながら充実した日々を過ごせていたと思います！
ありがとうございました！！

反省

コンテスト終わってから2か月経っているのですが！？！？
記事を書くなら忘れないうちに書きましょう

明日から

AHC013 始まりますね！！
またこのときみたく根性が出せるかわかりませんが盛り上げていきましょう！！

「カイジ闇の黙示録」で所持金をカンストさせる方法

ゲーム

どうも、prd_xxxです。ゴリ～～。

何かと話題のスマホゲーム、「カイジ闇の黙示録」、やってますか？？
ぼくはもうやってないです。
ちなみに自分の身の回りはポケモンLEGENDSアルセウスか、Wordle系ばっかり流行ってる気がします。
なのであんまり有用ではないですが、ぼくが所持金(エーン) をカンストさせた方法を書き残してみます。

2022/02/02 確認時点 (iOS版バージョン1.3) では、所持金の最大値は INT_MAX ( =2147483647) のようです。

方法

  1. インストールします
  2. 画面下部「GAME」から「HIGH & LOW」を選びます
  3. 「HIGH & LOW」だけをひたすらやります

これだけだとそっけないので補足しますが、
HIGH & LOW はシンプルなゲームで、まず相手がトランプのカードを1枚表にして、
それを見たうえで次に自分が開けるカードが相手より数字が上か下か？を当てるゲームです
同じ数字であれば両者引き直しです。
(なお、「2」より「A」が上です。説明の都合上、以降 (J,Q,K,A) を (11,12,13,14) と表記します)
毎回プレーヤーが掛け金を決めて、勝つと掛け金が2倍になって貰えて、負けると没収です。
そして、勝つと ダブルアップ ができるのですが、これは掛け金を2倍にできて、以降4倍... 8倍... と連続で勝つごとに倍増させられます。もちろん途中で負けると没収です。

そこで所持金を簡単にカンストさせるための鉄則が3つあります

  • 賭け金は毎回maxまでかけること (最大値はプレーヤーレベルによって異なります)
  • 相手が「2～7」ならば「HIGH」、「9～14」ならば必ず「LOW」を選ぶこと。「8」ならどっちでも。
  • ダブルアップは必ず「はい」を選ぶこと。7連勝で強制ストップなので、7連勝での大勝ちのみを狙う。

一時的に負けが続くことがありますが、必ず勝ちを取り返せるのでもくもくと続けましょう
(特に序盤は借金になったりして不安になるかもですが、気にせずmaxを張り続けましょう)
あとはやる気があるかどうかですｗ
なお、この方法で3時間ぐらいあればカンストさせることができます。(合間にポチポチやってたので時間は適当ですが大体そんなもんです)

計算してみた

さて、上の鉄則を守ったうえで、相手がカードをまだ伏せた状態で自分が勝てる確率 p を求めてみます。
相手のカードが k だったときに自分が勝てる確率を p_k とすると、
p = \frac{\sum_{k=2}^{14} p_k}{13} となります。それぞれの p_k は以下のようになります。

  • p_2 = \frac{3p + 48}{51}
  • p_3 = \frac{3p + 44}{51}
  • p_4 = \frac{3p + 40}{51}
  • p_5 = \frac{3p + 36}{51}
  • p_6 = \frac{3p + 32}{51}
  • p_7 = \frac{3p + 28}{51}
  • p_8 = \frac{3p + 24}{51}
  • p_9 = \frac{3p + 28}{51}
  • p_{10} = \frac{3p + 32}{51}
  • p_{11} = \frac{3p + 36}{51}
  • p_{12} = \frac{3p + 40}{51}
  • p_{13} = \frac{3p + 44}{51}
  • p_{14} = \frac{3p + 48}{51}

例えば相手のカードが k = 4 だったとき、p_4 を考えると、トランプ52枚のうち表になっている1枚を除く51枚のうち、「HIGH」を選ぶと「5～14」の40枚で勝ち、「4」の3枚で引き分け、「2～3」の8枚で負けることになります。
引き分けた場合は相手も再度引き直しなので、 p の確率で勝てるわけです。

p = \frac{\sum_{k=2}^{14} p_k}{13} = \frac{39p + 480}{13 \cdot 51} = \frac{39p + 480}{663}
p = \frac{480}{663 - 39} = \frac{480}{624} = \frac{10}{13}
となり、 \frac{10}{13} で勝てることがわかりました。
なんと倍々にダブルアップさせてくれるのに、単発では77%ほどの確率で勝たせてくれますｗ

次に、ダブルアップで7連勝を目指し続けた場合の獲得金額の確率と期待値を求めてみます。
掛けた金額を x とします。

事象 確率 獲得金額 期待値
1回目で負け 1-p = \frac{3}{13} \simeq 23.1\% -x -x (1-p)
2回目で負け p(1-p) = \frac{30}{169} \simeq 17.6\% -2x -2xp(1-p)
3回目で負け p^{2}(1-p) = \frac{300}{2197} \simeq 13.7\% -4x -4xp^{2}(1-p)
4回目で負け p^{3}(1-p) = \frac{3000}{28561} \simeq 10.5\% -8x -8xp^{3}(1-p)
5回目で負け p^{4}(1-p) = \frac{30000}{371293} \simeq 8.1\% -16x -16xp^{4}(1-p)
6回目で負け p^{5}(1-p) = \frac{300000}{4826809} \simeq 6.2\% -32x -32xp^{5}(1-p)
7回目で負け p^{6}(1-p) = \frac{3000000}{62748157} \simeq 4.8\% -64x -64xp^{6}(1-p)
7連勝 p^{7} = \frac{10000000}{62748157} \simeq 15.9\% 127x 127xp^{7}

7連勝のみを勝利としても、およそ 6.3回に1回は勝利できるとわかりました。
(リスクを全部無視した場合、6.3回に1回は掛け金が127倍になって返ってくるわけですね)

そして、いずれかの結果が出た時の獲得金額の期待値 e は、
e = 127xp^{7} - 64xp^{6}(1-p) -32xp^{5}(1-p) -16xp^{4}(1-p) -8xp^{3}(1-p) -4xp^{2}(1-p) -2xp(1-p) -x (1-p) = (127p^{7} - 64p^{6}(1-p) -32p^{5}(1-p) -16p^{4}(1-p) -8p^{3}(1-p) -4p^{2}(1-p) -2p(1-p) -(1-p)) x = (191p^{7} - 32p^{6} -16p^{5} -8p^{4} -4p^{3} -2p^{2} - p - 1) x
= (191(\frac{10}{13})^{7} - 32(\frac{10}{13})^{6} - 16(\frac{10}{13})^{5} - 8(\frac{10}{13})^{4} - 4(\frac{10}{13})^{3} - 2(\frac{10}{13})^{2} - \frac{10}{13} - 1)x
= \frac{191\cdot10^{7} -32\cdot10^{6}13 -16\cdot10^{5}13^{2} -8\cdot10^{4}13^{3} -4\cdot10^{3}13^{4} -2\cdot10^{2}13^{5} -10\cdot13^{6} - 13^{7}}{13^{7}} x
= \frac{748320793}{62748517} x
\simeq 11.9257x

となり、なんと 1回の試行あたり 11.9倍 になって掛け金が返ってくることが期待できるとわかります。

おわり

この誰がやってもボロ勝ちなゲームを止めない利根川さん、無能すぎませんか？
みんなで21億稼いで帝愛をつぶしましょうｗ

f:id:prd_xxx:20220202213016p:plain
表情を変えずにお金を配り続ける利根川さん