noteレッドコーダーへの道のりは遠い。Respawn問題1からNまで番号がついたN頂点M辺の有向グラフが与えられる。頂点1から頂点Nまで辺を辿っていくことを考える。辺iは通過するのに1分かかり、通るたびにコインがCi枚もらえる。頂点Nにたどり着いておいてあるボタンを押すと「それまで回収したコインの総数から経過時間*P枚を引いたコイン枚数」が得られる。(コインが足りない場合は0枚になる)得られるコインが最大になるように行動した場合、何枚得られるか?最大値が存在しない場合は-1を返せ。辺のコストの正負を逆転させることで最短経路と同じ要領で求められる。ループがあると最大値が無限に大きくできてしまうため、それを検出できるベルマンフォードで適用を考える。単純に適用しようとすると、サンプルにある通り、「頂点1からたどり着けない頂点」、「頂点Nにたどり着けない頂点」も含めて閉路を検出してしまう。上記のたどり着けない頂点をチェックして、その頂点を除いたグラフで適用すれば良い。N-1->NのようなグラフでTLEになってしまう。HxWのグリッドにコインがいくつか置かれている。辺に正の重みがある連結なグラフが与えられる。»プロフィールid:phyllo_algoレッドコーダーへの道のりは遠い。)はてなブログをはじめよう!phyllo_algoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。