すごい面白い問題だった。 ビームがx, y方向に打たれるので頑張って最小の動きで逃げようという問題。 ビームがx方向に打たれるものとy方向に打たれるものがあるが、結局動きのコストはマンハッタン距離なのでx,y独立に考えてもいいよね、というのが根幹とな…

うーむ くだらないミスを2つしていて随分と時間がかかってしまった…解き方は簡単で、グラフと言えども、距離順に上から決めてしまえばよい。 同じ距離の頂点に関しては結んでも結ばなくてもよい。(ここの式が少し間違ってて悩んだ) あと、無意味にmapを使っ…

久しぶりに暇だったのでやってみた。 桁DPなるものを初めてやったのでメモdigitDPはこのサイトが驚くほどわかりやすいtatanaideyo.hatenablog.com考え方はいわゆるdigitDP dpの配列を、dp[何桁目を見ているか][今見ている桁までで1が何回出ているか(桁の数以…