人の最大の力を競う数学の大会、優勝してしまった…
— しゃかやみ (@shakayami_) 2023年3月11日
— しゃかやみ (@shakayami_) 2023年4月1日
匿名希望になってもうた pic.twitter.com/PKCkL70Gbe
— しゃかやみ (@shakayami_) 2023年4月1日
匿名希望はわたしです
問題
問1
(i)これはO(HW)のdp
実は斜め移動の回数を固定すると縦・横の移動係数も定まるので多項係数となる。結局$\min(H,W)$個くらいの多項係数の和になる。なので$1\leq H,W\leq 10^5,\mod 998244353$でもいけそう
(ii) (i)の答えが681と比較的少ないので、681回O(HW)のdpして足し合わせたらいけた
もっと効率のいい方法はわからなかった。
問2
(1) とりあえず愚直解を書く
したら規則性は見えた。つまり$(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^n$を展開したときの$x^k$の係数になりそう
(2) 愚直にやったら$O(10^n)$だったけど、規則性が見えたので多項式時間のプログラムになった。なのでn=20とかも楽々に計算することができて、その結果をOEISにぶちこむと以下の数列が出てくる
説明文を見る限り、$O(n)$より計算量の低い表記は未判明っぽかったのでそれ以上の深追いはやめて$G_i$はシグマ表記が残る形にした。
$G_i$が最大になる$i$は$i=\lfloor \dfrac{9m+1}{2}\rfloor $であろうことは実験で察することができたけど証明は間に合わなかった…
問3
ゲーム系は苦手やねん…と思いながら見てたけど、よく見てみるとGrundy数でいけそう。
ここで、状態を$[i_l,i_r)\times [j_l,j_r)$という長方形領域でもって遷移するプログラムを書いた。全部先手必勝になって若干不安になった。
提出したあとで気づいたけど、チョコレートが欠けていない場合はある程度解析できた。
「山に$n$個の石があるときに$n/2$個まで石を取り除けて、操作できなくなったら負け」というゲームのGrundy数は実験してOEISにぶちこむとA025480 - OEISであることがわかるのだが、長方形になると全体のGrundy数は2つのGrundy数のXORとなる。なのでa(H)=a(W)なら後手必勝、そうでないなら先手必勝となる。A025480の第n項は$O(\log{n})$で計算できるので$O(\log{H}+\log{W})$で勝敗判定ができる。長方形なら多くの場合で先手必勝になりそう。後手必勝になるのは正方形の場合や、$n\times (2n+1)$や$n\times (4n+3)$、・・・$n\times (2^k n+(2^k - 1))$みたいな場合のときである。
余談だけど提出するファイル形式（ファイル名）を間違えているのに途中で気づいて時間を少しロスしてしまった。
問4
まず確率を計算するのは簡単にできる
問1 なんもわからんかったんでbit全探索した
問2 これもなんもわからんかったんでbit全探索…と言いたいところだが明らかに間に合わないのでどうしようかといったところ。確率の比の整数が単純だったらナップサックDPで通るけど比は単純じゃない。そうすると多項式時間が厳しそうな匂いがしてくる（今調べたけど部分和問題なのでNP完全。多項式時間は絶望的です）ところで、よく見てみると41回以内に終わるので半分全列挙が使えそうな気がする。なので書くと無事現実的な時間で終わるプログラムが書けた。
時間に余裕があったので、最小値を達成するようなパターンの数を計算するプログラムを書いた。
差の最小値が0になるのでバグってないか少々不安になった
解答
解答として提出したソースコードを公開しています。
賞金
アマギフ2万円
Wolfram Alpha Proの1年間ライセンス
なぜ匿名希望にしたのか
あまり覚えてない。多分参加登録したときに「名前を公開することに同意するか」というところで「同意しない」を答えたからだと思われる。
感想
競プロっぽかった
