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

ゲーム

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

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

カイジゲーム、INT_MAX でカンストしたｗ
おわりです pic.twitter.com/ycdwqUwrI3
— prd🦍 (@prd_xxx) January 29, 2022

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

方法

インストールします
画面下部「GAME」から「HIGH & LOW」を選びます
「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 — 表情を変えずにお金を配り続ける利根川さん

2022-01-08

Twitterでみかけた論理パズルを勝手に解説してみた

論理パズル

ちょっと前に Twitterで以下のような論理パズルをみかけたので、勝手に解説してみようと思います！！

私の知ってる論理パズルで最高難易度

頑張ったけどお手上げでした。解答知ってすごいと思った。ある程度正解には近づいてたけどもう一段階発想の大転換が必要だった。
チェス版の向きはドアの手前の面、その右、とかで指定可能です
完全に自力で解けた人いたらガチで尊敬する pic.twitter.com/RwBnGuhkNG
— 逢空れい@在野ぴえん系応用数学者になる！ (@rinnarua) January 4, 2022

問題

問題文が画像なんですが、(写経がめんどかったので) 転載しますね

読みましたか？
特に、幼女Aは1. と 2. のいずれかの操作をちょうど1度だけ 行います
(私は最初問題文を誤読してたので大事なところを強調しました)

以下、ネタバレになるので自分で考えたい人は考えてみてください

↓

前提になる知識

排他的論理和 (xor)

解説

幼女たちが事前に決めておくべきことを、4つに分けて書きます

1. 数の置き換え

1以上64以下というのは、若干都合が悪いので、0以上63以下に置き換えます
つまり、以下のことをします
* 幼女Aは、1以上64以下の数 $n$ を告げられる。
* 幼女Aは、0以上63以下の数 $n'$ をチェス盤に何かしらの方法で残す ( $n' = n-1$ )
* 幼女Bは、0以上63以下の数 $n'$ をチェス盤から何かしらの方法で読み取る
* 幼女Bは、1以上64以下の数 $n$ を回答する ( $n = n'+1$ )

64が都合が悪い理由は、6ビットに収まらない (2進数で7桁ある) のが理由です。
0～63ならばどの数もちょうど6ビットに収まります。

2. 盤に数を割り当てる

盤のマス目に0以上63以下の番号を1つずつ振ります。
以下は1例です

3. 盤で「数」を表す

さて、幼女Aが幼女Bに数を伝えるには、盤面にその数の情報を残さなければなりません。
ここで、ポーンが置いてあるマス目の番号たちの排他的論理和を $x$ とします (1つも置かれていない状態は $x=0$ とします)

例えば、以下のように $(13,34,54)$ にポーンが置かれている場合、
$x=13\oplus34\oplus54=25$ をこの盤面が表す「数」とします。

こう決めることによって、幼女たちは意思疎通の準備ができました！

4. 幼女たちの役目

幼女Aの役目

1以上64以下の数 $n$ を聞き、0以上63以下の数 $n'$ に直します
次に現在の盤面の「数」を読み取ります。つまり、ポーンの置かれているマス目の番号たちの排他的論理和を計算します。これを $x$ とします。( $0 \leq x\leq 63$ )
$x$ と $n'$ の排他的論理和を求め、 $y$ とします。( $0 \leq y \leq 63$ )
$y$ の位置が空きマスならばポーンを置きます。ポーンがあるならば取り除きます。

なぜこれで上手くいくのか気になるかと思いますが、後ほど解説します(☆)

幼女Bの役目

盤面の「数」を読み取ります。つまり、ポーンの置かれているマス目の番号たちの排他的論理和を計算します。これを $z$ とします。( $0 \leq z\leq 63$ )
1以上64の数 $z+1$ を回答します。

なぜこれで上手くいくのか？(☆)

ここが最も大事で、最もおもしろいです。
幼女A は、 $y=x \oplus n'$ となる $y$ を求めました。
$y$ の位置が空きマスだった場合、ここにポーンを置きました。
幼女Bが読み取る、この盤面 $z$ はどうなっているでしょうか？
$x$ を作ったポーンの集合に $y$ を加えるのだから、 $z=x\oplus y$ になるはずですよね。
これに $y=x \oplus n'$ を代入すると、
$z=x\oplus y = x\oplus x\oplus n' = n'$ となり、求めたい数が読み取れました！
なんと初期盤面である $x$ が2回現れて相殺されています。
初期盤面はどんな配置でも良かったことがわかりますね。

また、 $y$ の位置にポーンがすでにあって取り除いた場合も、置いた場合と同じ演算で考えられます。
$y$ の位置のポーンを初期盤面から取り除いたものを $w$ として、 $x=w\oplus y$ ですよね。
両辺に $y$ をxorすると、 $x\oplus y = w\oplus y\oplus y = w$ となり、
結局 $z$ を求めたのと同じ式 $x\oplus y$ で求められます！ ( $w=z$ )

おわり

初期盤面がどんな配置であれ、この方法で解けるのが面白いな～と思いました。
あと、幼女、すごいね。

2021-09-15

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜参加記

AHC コンテスト参加記

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜　に参加しました！ atcoder.jp

1週間の長期コンテストだったのですが、今回はなんと3日分の休暇を使うなど、気合をいれてきました！

結果

最初に結果をドーンするのですが、初の景品圏内に食い込めるなど、自分としては出来すぎの結果でした！
システムテスト後では28位、5033282981点でした！！
祝！！景品ゲット！！！！

日本橋ハーフマラソン2021増刊号、お疲れ様でした！
システス前暫定29位、251089960点でした！景品圏内の快挙です！！うれしい！！

解法はそのうちブログに残しますが、収穫機が常に連結を保つのと、いつ購入を打ち切るかが鍵だった気がします！#R_procon pic.twitter.com/FPpudDv6kR
— prd🦍 (@prd_xxx) September 12, 2021

重要なポイント

今回大事だったことは、だいたい以下の内容だと思います

収穫機の購入をいつ打ち切るか？
- 最終的に持ってるお金でスコアが決まるので、終盤で買っても元が取れないとだめ
- どこかのタイミングから「買えるけど買わない」選択をする必要がある
収穫機が連結しているときのボーナスが強い
- $N$ 個連結していると $N$ 倍になるので、できるだけ連結な状態を保ったままにしたい
評価関数をどうするか？
- 収穫機を配置/移動する際に何を基準として決めるか

以下、時系列順にやったことや考えたことを記していきます

序盤～1.3M

今回サンプルコードが提供されると聞いていたので、ダウンロードしてそのまま提出しました (開始1分、0.23M点)
このサンプルコードが超有難くて、コーディング時間の短縮だけでなく、問題理解の助けにもなりました

そうそう、今回のマラソン、サンプルコードがついてきたのすごくうれしかった #R_procon
整ったGameクラスと、盤面やスコアのシミュレートが書かれてて、それだけで数時間節約された気がする。
最終的に count_connected_machines() くんはリストラしちゃったけど (連結前提のコードなので)
— prd🦍 (@prd_xxx) September 12, 2021

とりあえずサンプルコードを動かしてビジュアライザで見たりしながら、ふむふむしてました
あと、テストケース50個作って、スコアの合計を出すスクリプトを用意しました (AHC003のときの流用)
- 今回これを序盤で用意できたのは個人的に捗りました
収穫機の購入をいつ打ち切るか？の問題には早めに気づいたので、スクリプト何回か回しながらとりあえずサンプルコードで収穫機を12個で打ち切るようにして提出。→1.3M

16.1M

適当に貪欲っぽいのをかきました

44.0M

収穫機の購入を34個で打ち切るようにしました

63.6M

ビジュアライザを見ると、なんか終盤に塊はできてくれてたけどなぜか下側のほうに溜まってく傾向があった
連結成分をもっと戦略的に動かしたい気持ちになりました
- 連結を保ちたい
  - moveはとりあえず置く→取り除くの順で考える
  - いままで置いたやつに隣接してる場所で良いところに置く→そこからマンハッタン距離で一番遠いやつを取り除く
良いところ、の評価はすぐに獲れる野菜があればその価値、そうでなければ盤の真ん中に近いのをほんのり優遇しました
収穫機の購入は37個までに設定しました

107.5M

これまでは隣接してるマスしか考慮していなかったので、遠くのマスも考えたくなりました
まず多点BFSを使って、連結を保ちながらあと何ターンでその場所に収穫機を置けるか (=距離)を求めました
それで、vege.v / 距離の値が一番大きいマスをターゲットとして、ターゲットへ1マス近づく選択を常にしました

164.8M

ビジュアライザを見ると、ちょくちょく連結が切れてしまっているようだった。
moveで置く→取り除くの動きの中で、マンハッタン距離で一番遠いやつを取り除いていたが、置いたマスから連結成分をBFSして一番遠いところを取り除くことにした。→151M ！
収穫機の上限を48個までに設定した → 164.8M

167.1M

序盤のムーブを改善しました
- 収穫機が1個しかないときに、隣接するところにしか動けなくて、2個めをなかなか買えてなかった(笑)
- 収穫機が1個のときは瞬間移動させた

176.5M

ターゲットマスを決める際の評価関数の調整をしたくなりました
おおむねこんな感じ (伝わる？？)

マスごとの評価関数、そこに収穫機があることで将来的にどれぐらい嬉しいか、を考えてて、
いまx日目でy日目にそのマスに収穫機を置けたとして、
Σ(day = y～x+65日) day日めに獲れる野菜のv / (day-x+1)
を評価に使った (獲った野菜は足さない)
— prd🦍 (@prd_xxx) September 12, 2021

(ちなみにこのときは 65日先までではなくて30日でした)
ついでにターゲットに1マス近づける選択をするときも複数のマスから↑の基準を使って選ぶことにしました
さらに取り除く候補が複数あるときのタイブレークも↑の基準が低いのを選ぶことにしました

236.6M

取り除く候補として、置いたマスからBFS的に一番遠いところを選択していたが、そうでなくても連結の切れないマスはたくさんあることに気づいた
グラフで言う関節点でなければ、取り除いても連結が切れないので、関節点を列挙することにした
- 調べた感じLowLinkを使うのが速そうだったが、持ってなかったので一旦UnionFindで自前で書いた
収穫機の上限も48→50へ変更
暫定8位！！
- 今回の問題では、このときの改修と、上述の評価関数の組み合わせが今回うまくハマったのだと思います

うおおおおお！！！
175M → 235M で暫定8位！！きたー！！ pic.twitter.com/A6DqPJJMFf
— prd🦍 (@prd_xxx) September 7, 2021

247.1M

評価関数のなかで、何日先までの野菜を見るかは、えいや！で30に決めてたので、これを調整して65にしました
- たくさんスクリプトを回した結果65日先が良さそうだった
- ターン数や所持収穫機に合わせて動的に変えるのはうまくできなかった
暫定5位！！
- まだ2日目ちょっとなのでこの後どんどん抜かれるんですが、かなり舞い上がってました。

うおおおお！！ 236M → 247M、暫定8位 → 5位！！
とても興奮してしまう pic.twitter.com/s483P0IiBg
— prd🦍 (@prd_xxx) September 7, 2021

ボツ案たち

さて、暫定5位という上振れを引いてしまい、このあたりから有効な改善策がなかなか取れなくて6日目ぐらいまでほとんど伸ばせませんでした。。
このあたりで考えたり試したりしていたボツ案たちを供養したいと思います

passを選択肢に入れる
- これは効果が薄かったので、超極端な場合だけ採用されました (ターゲットマスで獲れる野菜に1ターン以上余裕があり、取り除くマスの評価がやたらと高い場合だけ、passをする)
- ほとんど発動することはない
評価関数の式をいじる
- いろいろいじりました、分母を2乗したり3乗したりいろんな定数を足したり引いたり。→効果なし。
move処理で取り除くマスを選ぶときに、置いたマスは除外していたが、あえて除外せずに、一致した時にpassをする。→逆効果
終盤、この収穫機を買うことで元が取れるか？をすごく考えた
- 1個あたりの収穫機が残りのターン数でどれだけ稼げるかを推定したくなった
  - 野菜の価値はターン数の関数で表せるので、期待されるスコアをその関数で分割して計算したりした
- この作戦、いろんなパラメータを試したがさほど効果がでなかった。

250.0M

収穫機を50個に固定しているのがずっと気にかかっていて、テストケースによっては48個で買うのやめたり53個まで買ったりするのが良さそうと思っていました
これまで幅1でシミュレーションして終わりだったので、終盤をビームサーチ的に複数のシナリオを走らせるのをやりたくなりました
Gameクラスが肥大化してたので、リファクタして小さくしつつ実装がんばりました
幅5で提出したらTLEだったので、50,51,52の幅3で提出しました。これで250.0M！
- 幅3でも1799ms だったので、そろそろPyPyでの実行時間を厳しく感じてきました

251.0M (最終提出まで)

複数シナリオを並行して進めるのではなく、1つずつ終わらせるようにしました。(chokudaiサーチ的？)
- これで、幅を3に固定することなく、高速化の度合いによっては4つや5つのシナリオを走れるかも？
高速化
- UnionFindで書いてた関節点列挙を、LowLinkに書き換えました
- 盤面のシミュレートで使われていた count_connected_machines() くんをリストラしました (どうせ全部連結なので)
時間を計測しつつ回せるようになった
- ただ、手元環境はジャッジ環境よりだいぶ遅く、手元環境のスクリプト回すのがあまり意味なくなってきた。ジャッジに投げていくしかない
提出 → 250.6M
収穫機49個始まりにして提出 → 250.7M
収穫機48個始まりにして提出 → 251.0M (最終提出)

できなかったこと

PyPyをRustとかに書き換えれば速くなってもうちょいスコア伸びたのかな？ (到底まにあわなかった)

おわり

最終的に28位という自分としては出来すぎな順位がでてとてもテンションがあがりました。楽しかったです！！
あと、マラソンを頑張るといつも思うことですが、充実感がすごいですね。(つかれたけど)
今後もやれる限りがんばってみたい気持ちになりました！！

2021-06-01

AHC003 参加記

AHC コンテスト参加記

AHC003、参加しました！！

atcoder.jp

きっと参加記を書きますと言ったので、参加記を書きます！！

#AHC003 お疲れ様でした
94161824540 点でしたシステス前136位ぐらいで個人的に健闘しました！
画像はseed 0です
序盤200ターンは横→縦→横みたいに曲がる回数は高々2回
残り800ターンは毎ターンdijkstraしました
距離の予測に使うスコアは終盤ほど重みをつけました
あとできっと参加記を書きます pic.twitter.com/bBMw91YEpi
— prd🦍 (@prd_xxx) May 30, 2021

↑にも書いていますが、自分としてはなかなか健闘できたと思っています！
誰かの役に立つかは不明ですが、今回は思考の流れを軽くメモしていたので、時系列でやったこと試したことを書いていきます！

問題概要などは割愛します！ (問題文をみてね)

63.1G

縦に動いて横に動くと、このスコアになります！

76.2G

とりあえず横→縦→横と動くことにして、どの縦線を使うかを全探索しました。
(縦座標または横座標が同じ場合は一直線)
基本的に、 $\frac{(得られた距離の合計)}{(通った回数)}$
のような感じで推定をしました
(実際には得られた距離には $\frac{(縦の辺数)}{(縦+横の辺数)}$
を掛けて使用しました。)
そのために、各縦線の得られた距離の合計と通った回数を管理する2つの配列を用意してやりました

81.1G

↑の方針に加え、横線についても管理するようにして、縦→横→縦　の選択肢も加えました。

85.2G

情報の粒度を細かくしました。
横線についてはすべての $h_{*,*}$ 、縦線についてはすべての $v_{*,*}$
について管理するようにしました。
基本の移動ポリシーは変わらず、横→縦→横か、縦→横→縦です
それと、申し訳程度に乱択を加えました。
縦に動く回数を $v$ 、横に動く回数を $h$ とすると、 ${}_{v+h} C_v$ の動き方のうち $100$ 種類程度を毎ターン評価にいれました (しかしあまり意味なかったと思う)

ボツ案

さて、各辺を簡単に評価できるようになったところで、考えました
これは、みんな大好き 最短経路問題 じゃないか！！
グラフのサイズも小さいし、これは Warshall–Floyd が使えるだろ！と思いました
ところが掛け算をしたぼく
「 $30 \times 30 = 900$ 頂点、これは $O(V^3)$ が間に合わない！」
「そうだ頂点を減らそう、 $i, j$ がともに偶数の頂点だけ使えばサイズが $1/4$ になる！」
「 $225$ 頂点なら $100$ ターンごとに $9$ 回の最短距離更新をしても間に合うな」
との思考で改善をたのしみに勇んで書いたコードは
80G 点ほどでした。(ボツ) ¹

89.1G

よくよく考えると、Warshall-Floydはとても無駄が多いことに気づきました
例えば頂点 $(0,0)$ から $(5,5)$ へ移動する場合に、明らかに $(10,10)$ みたいな頂点は経由しないです。
(※ Warshall-Floyd はすべての頂点を経由してみることを試します)
経由するべき点は殆ど、 $(s_i, s_j)$ と $(t_i, t_j)$ を含む長方形に収まるだろうと考えました
そこで思いついた！
例えば左上から右下に動くとして、右か下にしか移動できない場合の最短経路は、dp で求まる！
しかもどのような移動によって最短路を更新したか、記録すれば dp復元 もできる！そして、この dp こそ、 $O(N^2)$ なのでなんと毎ターン求めても余裕で間に合うのです！
また、ビジュアライザをみて気づいたのですが、
同じ縦線 (または横線) に含まれる辺は、値が近い ことにも気づきました。
序盤はあまりクネクネ動かない方が精度よく情報を集められるだろうと考え、序盤200ターンは横→縦→横か、縦→横→縦の移動ポリシーを残すことにしました。
残り800ターンをdpにしたら良い感じでした。

89.8G

移動がdpでうまく書けたので、今度は距離の予測をどうにかしたい気分になりました。
例えば $(s_i, s_j)$ から $(t_i, t_j)$ の(グラフ上の)距離が $3$ で、ジャッジから得られた距離の実測値が $20$ だとします。
このとき、今までは $3$ つの辺に対して、「得られた距離」に $\frac{20}{3}$ を足し、「通った回数」に $1$ を足していました。
これを改良し、「得られた距離」にフィードバックする距離の長さは、予測される距離で按分してあげることにしました。
つまり $3$ つの辺の現時点での予測距離が、 $3, 5, 7$ だとすると、それぞれ、
$20\times \frac{3}{3+5+7}$ , $20\times \frac{5}{3+5+7}$ , $20\times \frac{7}{3+5+7}$
を「得られた距離」として足してあげることにしました。
これによって予測がちょっとだけ改良しました！

90.3G

↑の予測をちょっといじって、ターンが経過すればするほど (=新しい情報ほど) フィードバックを重めにしました。
(純粋に turn / 100 みたいな値を掛けた)
90Gに乗りました！

93.3G

ここで、例えば左上から右下に動く場合は右か下にしか動かないことを仮定して dp をしていたけど、これを疑うことをしました。
(時には一見遠ざかるような移動も役に立つのではないか？？)
そこで気づいちゃったんですね！
dpが間に合うということは、dijkstra も間に合うんでない？？
実際 dpは毎ターン $O(N^2)$ 、
dijkstraは毎ターン $O(E \log V) = O(N^2 \log N^2)$
で、 $\log$ が掛かる程度なんです！
実際書いてみたらPyPyで間に合いました！²
そして、スコアはここで大きく伸びました！うれしい！
上下左右の移動を許すことで、一見遠ざかるような移動でも改善できる移動は見逃さなくなりました！
これで伸びるの、わりと非直感的だなーと思って面白かった。

93.7G

ここで新たな武器を手にしました
ローカルで $100$ ケース実行して集計するシェルスクリプトです！ (書きました)
これまでは手元で数ケース叩いて改善してそうな雰囲気があったら投げていたのですが、 $30$ 分の提出制限はたくさん試すのには向かないと気づきました
いくつかパラメータをいじって猿のように試しまくりました！³
すると、フィードバックに掛けていた値 turn / 100 を (turn-152) / 8 にすることで、試したなかでは一番改善がみられてそうでした
これの意味は、 $200$ ターン付近で得られた情報は序盤 $200$ ターンで集めた情報の $6$ 倍の価値があって、 $1000$ ターン付近では $106$ 倍の価値があることを意味します
なぜこの値で改善するのかは、なぞです

94.08G

序盤 $200$ ターンの横→縦→横か、縦→横→縦の移動に関しても、フィードバックの距離は予測距離で按分して求めてあげることにしました

94.16G

序盤において、一度も通っていない点は初期値を定めて計算に使っていたのですが、これを使う機会をできるだけ減らそうと考えました。
同じ縦線 (または横線) に含まれる辺は、値が近い ことには気づいていたので、初めて通る縦線 (または横線) を記録するとき、直接通っていない箇所にもほんのりフィードバックしてあげました。
がっつりフィードバックでは悪化するようで、ほんのりが良さそうでした (重み 0.01)
微妙に伸びました。
他色々試したけど、結局このスコアは抜かせず、最終スコアとなりました

おわり

今回のコンテストは色々試せて、改善が見えたり見えなかったりしてたのしかった！！
おわり

始点終点が奇数を含む場合や、Warshall-Floydの復元など、実装が大変で丸1日はつぶしました。ショックです。↩
ただし枝狩りはしました　スタート地点より5辺以上遠ざかる移動はしないように↩
ゴリラなんですけどね↩

2021-05-21

CODINGAME SPRING CHALLENGE 2021 参加記

CodinGame コンテスト参加記

www.codingame.com

コドゲ参加しました！参加記を書きます！

結果

全体2069位、シルバーリーグ内235位　でした！！

あわよくばゴールド入りしたかったけど、かないませんでした(><)

工夫したこと

ぶっちゃけあまり有用なことは書けないのですが、六角座標の持ち方は自分なりに工夫したつもりなので下に書きます

六角座標の持ち方

フィールドが六角形の座標系でしたね。
普通の2次元座標 (x,y) みたいなのでも扱えるのですが、今回のゲームでは6方向(3軸)に木の影が影響してくるので、(x,y,z) の3軸になるように座標を振ってみました。

嬉しい性質がありました

外側の座標ほどの値が大きい
- この値が $0$ か $4$ だと richness が $3$
- $6$ か $8$ だと richness が $2$
- $10$ か $12$ だと richness が $1$
座標の値から行(列?) ごとにグループ分けができる
- 横方向 (x軸に沿った方向) はが一定
  - 上から1段目は $y+z=9$ , 2段目は $y+z=6$ , ... 以下3刻み
- 同様に y軸に沿った方向は $x-z$ が一定
- 同様に z軸に沿った方向は $x+y$ が一定
隣接するセルはとなる
- (残念ながら今回この性質は使いませんでした)

今回やったこと

毎ターン possible_action の中から、評価関数が高いactionを選択していました
つまり今回は評価関数しか作ってないです
評価関数の概要
- 基本は COMPLETE → GROW (2→3) → GROW (1→2) → GROW (0→1) → SEED → WAIT の順に優先 (例外あり)
  - COMPLETE 優先とはいえ、刈れるときに刈るという意味ではなく、条件にあえば必ず刈るという意味
  - 条件→ 6本以上生えている or 35点以上負けている or 刈れる木の本数が残り日数以上
- この基本値に加え、上記の六角座標をもとにした位置の評価を加減算していました
- 位置の評価の概要
  - 基本は、自分の木が同じ軸に被らないよう、分散させたい気持ちでした
  - 3軸の行(列?) ごとに、自分の木があれば重みをつける (size + 1 とした)
  - 軸ごとの重みの合計をセルの数で割り、軸の密度とした (上から2段目であれば $6$ で割る)
  - 密度を3軸ぶん足し合わせて定数を掛け、中心からの距離 ( $|x| + |y| + |z|$ ) を足した
  - この値が小さいほど優先度が高い (密度が低いか、中心に近いほど「良い」)

他細かい調整はしたけど大体はこんな感じです！

できなかったこと

先のターンを読んだり、相手の行動を読んだり、探索っぽいこと
相手の状態や木の配置を評価に加える
- 小一時間でやってみた感触は、よくなりませんでした
影の考慮とか

今後の抱負など

秋も出たいです
時間をもうちょっと捻出します
コドゲ3回目ですが、まだゴールドリーグに達したことがないので、次はゴールド入りたいです
ゲーム的な戦略をもっと観察しないと強くなれない気がするので、そこもうちょっと頑張ります

2021-01-10

ARC111-A Simple Math 2

ARC Python

Simple (笑) とは...
コンテスト中に解けなかったので、どうやったら自然に解けるようになるか整理してみます

問題リンク
A - Simple Math 2

問題概要

$\lfloor \frac{10^N}{M} \rfloor \mod M$ を求めよ
( $\lfloor x \rfloor$ は $x$ の整数部分)
$1 \le N \le 10^{18}(クソデカ), 1 \le M \le 10^4$

M=10で題意を理解してみる

まずは題意を感覚で理解しようとしてみます
maspy さんのおっしゃるように、 $M=10$ で一度考えてみることにします。

mod Mの基礎的なことが非自明に感じる方は、mod 10 の場合を考えるのも良いかもしれません。例えば「ab mod M は a mod M, b mod M から分かる」とかM=10だと知っていますよね。

昨日のAも
「(a^b//10) mod 10 を求めよ」であれば、
「a^b mod 100 があればよい」とすぐに分かる方、増えませんかね。
— maspy (@maspy_stars) January 10, 2021

$10^N$ の部分はとりあえず適当に $12345$ とかにしといて、 $M=10$ を代入します
$\lfloor \frac{12345}{10} \rfloor \mod 10$
これの、
$\lfloor \frac{12345}{10} \rfloor$ の部分は、
$1234.5$ の整数部なので $1234$ となります。
したがって
$1234 \mod 10$ となり、 $4$ が得られます。

実はこの問題の題意は、 $10^N$ (クソデカ数) を $M$ 進数で表したときの下から $2$ 桁目を出力せよ と同じなのです。

本当に？

$\lfloor \frac{x}{M} \rfloor$ の意味を改めて考えてみます。
これは、 $x$ を $M$ で割った商です¹
$x ÷ M = a あまり b$ と表されるとき、
$x = aM + b$ となります。商が $a$ 、あまりが $b$ です
整数部分を取る操作は、あまりを無視した商の部分ですので、
$\lfloor x ÷ M \rfloor = \lfloor \frac{x}{M} \rfloor = a$ です。

次に、 $y \mod M$ の意味を考えます。
これは読んでそのまま、 $y$ を $M$ で割ったあまりです。
$y ÷ M = p あまり q$ と表されるとき、
$y = pM + q$ となります。これの、 $q$ の部分が $y \mod M$ です。

さて、求めたいものは $\lfloor \frac{x}{M} \rfloor \mod M$ でした。
$y = \lfloor \frac{x}{M} \rfloor$ として、まず $\mod M$ の式に当てはめます
$y = \lfloor \frac{x}{M} \rfloor = pM + q$
(↑これの $q$ の部分が求めたい答えです)
次に、 $x = aM + b$ 、 $\lfloor \frac{x}{M} \rfloor = a$ を使います。
$a = pM + q$ となるので、
$x = (pM + q)M + b = pM^2 + qM + b$
となります。

ここで、 $M$ 進数とは、 $x$ をこのように分解して表した表現だと言えます。
$x = k_0M^0 + k_1M^1 + k_2M^2 + k_3M^3 + ...$
$k_0$ が $M$ 進数における下から $1$ 桁目、 $k_1$ が $M$ 進数における下から $2$ 桁目... です。
$x = pM^2 + qM + b$ と係数を比較すると、
$k_0 = b, k_1 = q$ となります。
したがって、求めたい数値は $q$ なので、 $x$ を $M$ 進数で表したときの下から $2$ 桁目を出力せよ と言い換えることができました！
なお、残りの部分は $M^2$ で括れるので $k_2M^2 + k_3M^3 + ... = pM^2$ として良いです (が本問では無視して良いです)

実装

Pythonが本領発揮できるところでした
以下でACしました！

N,M = map(int,input().split())
ans = pow(10,N,M*M) // M
print(ans)

ここで、 pow(10,N,M*M) は、Pythonでは「 $10^N$ を $M^2$ で割った余り」を高速に求めてくれます。²
上述の式で、 $10^N = pM^2 + qM + b$ と表せるところの、
$qM + b$ が求まります。
これを // M で $M$ で切り捨て除算することで、求める答えである $q$ が得られます。

おわり

simple (笑) とは... という感じだったけど、分かってしまえばなるほど simpleかもです
しかし 300点緑difficultyとは納得しがたい...
いずれにしても、数式を見て一目で分かるぐらいには慣れていきたい...！

私はこの言い換えすらコンテスト中にできませんでした…↩
愚直に求めるとTLEやMLEを起こすのですが、第3引数にMODの値を入れることで高速にMODをとりながらの累乗を求めてくれます。このような機能のない言語では繰り返し2乗法という手段を使うと思うのですがそのようなライブラリがないと辛いですよね。。↩

2020-08-30

ABC177-E coprime 4つの解法

ABC

ABC177-E coprime のPython or PyPyで間に合う解法を4つ記します

AtCoder Problems では緑difficultyらしいのですが(！？)コンテスト中には解けずに苦汁を飲みました

問題概要

$N$ 個の整数が与えられる
$N$ 個の整数の異なるすべてのペアが互いに素 ( $\gcd(A_i, A_j) = 1$ ) のとき、pairwise coprime と出力する
そうでなくてすべての整数の $\gcd$ が $1$ のとき、setwise coprime と出力する
いずれでもないとき、not coprime と出力する
$2 \le N \le 10^{6}, 1 \le A_i \le 10^{6}$

コンテスト中の思考

not coprime は最初に全体のを取ればok。 ( 以上なら not coprime)
- (追記) 以下紹介する4つの解法は最初に↑の判定を済ませている前提で書きます
本質は pairwise か setwise の判定
の異なる要素に共通の素因数が見つかったら setwise 確定。
- とりあえず全部素因数分解するのが思いつく
- ぐらいかかってしまうと思い敬遠。¹
  - →実は間に合う(解法3)
全部素因数分解、を避ける方法で判定しなきゃいけない！ (←思い込み)
前計算で $10^{6}$ までの素数を求めておいてうまくゴリゴリやろう...！ (←沼の始まり)

解法1 高速素因数分解

writer の kyopro_friends さんの想定解です。
エラトステネスの篩の進化版みたいなやり方で、osa_k法 とも呼ばれているみたいです。²

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

まず配列を用意し
- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, ...] のようにします ³
次にの倍数で書き換えられていないところをで書き換えます
- [0,1,2,3,2,5,2,7,2,9,2,11,2,13,2,15,...]
次にの倍数で書き換えられていないところをで書き換えます
- [0,1,2,3,2,5,2,7,2,3,2,11,2,13,2,3,...]`
次は $4$ ですがすでに $2$ に書き換えられているのでスキップします
次に $5$ の倍数で書き換えられていないところを $5$ で書き換えます
...

のようにして配列を作っておくと、素因数分解がめっちゃ高速にできます！！

tmp = set()
while a > 1:
    tmp.add(sieve[a])
    a //= sieve[a]

素因数の列挙は a > 1 である限り sieve[a] で割り続けるだけ！
(今回は列挙だけなので set でやっていますが、もちろん dict や Counter を使うことで素因数の個数も数えられます)

例えば a=60 として、

sieve[60] == 2 なので $2$ を抽出し、a を $2$ で割る。
sieve[30] == 2 なので $2$ を抽出し、a を $2$ で割る。
sieve[15] == 3 なので $3$ を抽出し、a を $3$ で割る。
sieve[5] == 5 なので $5$ を抽出し、a を $5$ で割る。
a==1 になったのでおわり。 tmp = {2, 3, 5} が抽出された。

計算量は $O(A \log \log A + N \log A)$ のようです
配列の前計算が $O(A \log \log A)$ 、素因数分解が $O(N \log A)$ です
素因数分解めっちゃ速いですね！！

ACコードの全体はこちら Python: 834ms

解法2 等間隔に舐めて調和級数で間に合うやつ

これは解説放送ですぬけさんが説明されていた方法です
詳しくは放送をご覧いただきたいのですが、なんと 素因数分解も素数判定も必要ありません

MAXA = 10**6
B = [0] * (MAXA+1)
for a in A:
    if a==1: continue
    if B[a]:
        print('setwise coprime')
        exit()
    B[a] = 1

まずヒストグラムみたいのを作ります (上記の B です)
同じ数値が2度出現したら setwise 確定で exit() しています。
ただし $1$ が複数個あっても $\gcd(1,1) = 1$ なので setwise とは確定しないことに注意！ (コーナーケース！)
結果として B の要素としては 0 か 1 のいずれかが入る形になります。

for n in range(2,MAXA+1):
    c = 0
    for m in range(n,MAXA+1,n):
        c += B[m]
        if c > 1:
            print('setwise coprime')
            exit()

さてここが肝です。上のコードでは

2,3,4,5, ... 1000000 までのそれぞれを n として、
- n から始めて 2n, 3n, ... (これを mとする) の B[m] をチェックしています
- 各n のどれかで、B[m] が 2回以上カウントされたら setwise 確定です。

一見 $10^{6}$ までのループを2重に回しているので間に合わなそうに見えるのですが、実は間に合います
よく見ると1回の外側のループでは MAXA // n 回ぐらいしか処理されません。
$O(\displaystyle \sum_{i=1}^{A} \frac{A}{i})$ は調和級数という考え方で $O(A \log A)$ になりますよというのが知られています (詳しくは解説放送をご覧ください)

ACコードの全体はこちら(PyPy) 327ms と、こちら(Python) 1320ms※ ⁴

解法3 愚直に素因数分解しちゃう

えー！間に合っちゃうんですか！

愚直に素因数分解を適用しても時間間に合いますよ。
慌てて書いたので変数名が酷いのは見逃してください……https://t.co/ISUmpWtBPC
— ライナス (@Linus_MK) August 30, 2020

ライナスさんにTwitterでリプライ頂きました
なんと愚直に試し割りして素因数分解しても間に合っちゃうみたいです！

計算量を雑に見積もると $O(N \sqrt{ \max A})$ で $10^{9}$ オーダーなんですが、ちゃんと考えると1桁以上落ちるようです
というのも、

$10^{6}$ 以下の素数は $78498$ 個で、 $10^{6}$ に比べて1桁以上少ない
鳩ノ巣原理という考え方を適用すると、(追記) $2$ 以上の $N$ が $78499$ 個以上存在すると自動的にどれかしらの素因数が重複する！ →setwise 確定！！
最悪ケースを一応考えると
- $999983$ のような素数がならぶ → $1000$ までの試し割りでok
- $2$ の $n$ 乗、 $3$ の $m$ 乗、 $5$ の $l$ 乗、、、みたいに ( $l,m,n$ は $\max A$ を超えないような最大の指数) が並ぶことも一応あるけどこれは早く検出できるうえに指数はせいぜい $20$ 以下

となり、 $78499 \cdot 1000$ (追記) $+ 10^{6}$ 程度で $8 \cdot 10^{7}$ に収まるオーダーです
これでPyPyで間に合いました

私も書いてみました(Pythonは間に合いませんでした)
ACコードの全体はこちら PyPy: 678ms

解法4 ゴリゴリスペシャル

きれいな解法ではないのでおまけです
コンテスト中に 2WA までこぎつけたのですがコーナーケースでやられていました
コンテスト後にねちょさんにコーナーケースを見つけていただきました！

1だけのケースでpairwise coprimeにならないのはわかりました
— ねちょ (@netyo715) August 29, 2020

先にコンテスト後のACコードを貼ります (下記2つは同一コードです)
PyPy 425ms、Python 1986ms (！！)

やったこと

全体の $\gcd$ を取って $2$ 以上なら not coprime
重複チェック。 $1$ 以外で つ以上重複している要素があれば setwise coprime
- $1$ 以外で の部分は本番中で見つけられなかったコーナーケースです...
エラトステネスの篩で $10^{6}$ ぐらいまでの素数を検出する。実際に使ったのはそのうちの $10^{3}$ 以下の素数
各について、
- 以下の素数で割れる限り割っていく
  - その過程で割れた素数は記録する
  - 重複していたら setwise coprime
- 以外になったらより大きい素数なので記録する
  - 重複していたら setwise coprime
いずれのチェックにもかからなければ pairwise coprime

という方法を取りました
ちょっとでも試し割りの回数を減らそうと素数を列挙したのですが、結局解法3で述べた鳩ノ巣原理 による影響の方が大きくて結局計算量的には間に合っています (本番中は鳩ノ巣原理も見破っていなかったです)

おわりです！！
1問でたくさん学びがある良い問題でした！！！！

$\sqrt{A_i} \le 10^{3}$ ぐらいまで試し割りする方法しかないと思い込んでしまった。。PyPyは基本的にPythonより速いが $10^{8}$ オーダーは間に合うけど $10^{9}$ オーダーは間に合わない肌感。↩
おさけ？↩
0,1は素数じゃないので扱い注意です (-1などで埋めるのが良い？)↩
リンク先を見ると分かると思うんですが、PyPyと同一のコードではTLEしてしまいました。簡易的なPythonの高速化として「全体を関数で囲む」というのがあるんですが、それをしたらACしました！↩