EmK https://blog.hatena.ne.jp/EmK/ C♯の勉強 https://emkcsharp.hatenablog.com/ TopCoder Div2 Div2Hard どういう場合にパターン数が指数関数オーダーになるかというと、それは ある点に対して複数ループが存在する場合 という条件を満たすときになる。ループが１つしかない場合は、線形オーダーでしかパターンが増えないが、２つ以上ある場合はループで戻るたびに選択肢ができるため、指数関数的にパターンが増大することになる。よって、各点からスタートしてもとの点に戻るような経路が２つ以上ないかどうかを探索すればよい。 以下のコードでは、複数ループが存在するどうかの判定にベルマンフォード風の動的計画法を使っている。dp[i] := i にいる経路のパターン数ただし、そのまま適用するとループ２周目以降の経路も重複して数え… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Femkcsharp.hatenablog.com%2Fentry%2FSRM608%2FBigOEasy" title="TopCoder SRM608: BigOEasy - C♯の勉強" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-02-15 10:50:32 rich https://emkcsharp.hatenablog.com/entry/SRM608/BigOEasy 1.0 100%