デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280) Fまで。
D 素因数分解
E -2の回数を全探索して二項係数を使って計算。DPでやる方法が分からず苦戦。
F 重みつきUnion-find
G xとyとy-xの最大値・最小値を管理してDPすればいけるが、計算量が間に合わない。

— titia (@titia_til) December 3, 2022

E - Critical Hit

　ACはできたけど期待値DPで立式できなかったのは反省。

　最初DPで解こうとしたのに、DP[i]=i回で倒せる確率　とか考えたせいもあって立式できなかった。

・DP[i]=体力iからの攻撃回数の期待値

　とするとよかったようだ。最初の攻撃がクリティカルかどうかで場合分けして立式することができる。

G - Do Use Hexagon Grid 2

　解説放送を見てAC。

　x, y, x-yを管理すれば二次元でマンハッタン距離を考えたときと同様にできることは分かったが、二次元のバージョンがそもそも分からなかった。

　「x座標の下限、y座標の下限」を固定して考えるのだけど、そのとき、下限上にある代表点を決めれば重複なく数えられる、というのがポイントか。

　これで重複なく数えられるというのは気付きにくかった。

　なお、実装も大変。