2020-10-01から1ヶ月間の記事一覧
問題文 : Aizu Online Judge LPの定式化から2つのアプローチができて面白かったのでそれについて説明する。 考察1 先手が初めに各辺に確率を割り振り、後手はそれに応じてを確率で選ぶとする。値 を先手は最大化、後手は最小化する時、Xの値はいくらかという…
問題 https://codeforces.com/contest/1240/problem/D 解法 解説を見た。 各indexについてそこから順にstackに入れていった時に初めて空になるindex nxt[i]が欲しくなる(これが分かればあとはdpで数えるだけ)。 しかし直接nxtを求めるには少し情報が足りない…