2017-09-08から1日間の記事一覧
問題ページ ぴょんぴょん川渡り | Aizu Online Judge 考えたこと 制約が色々小さくて最小コストを求めるので拡張dijkstraやDPを考える。 dp[i][j][k] = (i行目j列目まででk回一行飛ばしをしたときの最小滑りやすさ) としてDPを考えるとO(NMmax(k)^2)で計算量…
問題ページ タクシー | Aizu Online Judge 考えたこと 最短距離と言われたのでdijkstraを考える。遷移先が距離r[i]以下の頂点であるdijkstraをすればよさそう。全頂点からそれぞれdijkstraをしてある頂点から距離がr[i]以下の点を全列挙しておけば、あとはdi…
問題ページ 魚の生息範囲 | Aizu Online Judge 考えたこと 3次元imosすればよさそうだけど制約的に無理。領域木とかを考えてもわからないので解説を見たらただの座圧ではい。O(N4)で解ける これくらいは思いつきたかった… //#define __USE_MINGW_ANSI_STDIO …