Fまで六完でした。GとHは解法にかすりもしていなかった。要復習。
G - Three Permutations
snukeさんの解説放送を見てAC。
えー、難し過ぎませんか？ ステップ数が多いし、一つ一つのステップが重い。今は理解できているけど、もう一度まっさらな状態から解けと言われると結構厳しい気がしてしまう……。
以下、（提出コードにも書いたけおｄ）snukeさんの解説放送を聞いたメモ。
順列→グラフの問題と考える。
二つの順列から、サイクルの集合と考える。
各辺について、両端の頂点以外のものを書き込むと考える。
辺を、
・〇（両端以外を書き込むもの）
・×（両端のいずれかを書き込むもの）
・？（上記どちらでも良い）
の三つに分ける。
〇は扱いにくいので、包除原理を使う。
2^N通りのうち、×の箇所を決め打つと、
各連結成分について考えることで答えを求めることができる。
×の個数でDPする。
DP[i][j] = iまで見て×がj個のときの場合の数 とする。
各サイクルごとにDPする。
辺を順々に見ていき、「直前の頂点を使ったか？」をflagに持つ。
サイクルなので、最初の辺については二通り試す。
H - Collecting
解説放送を聞いてAC。
問題を見ても全くフローに思えなかったのでどうしようもないが、最小費用流と言われればなるほど、と思えた。Kが小さいのも、「フローを流す回数が小さい」と考えれば確かに、と。
ただ、
・コストが負の辺があるので、それを解消する工夫が必要
・自分のフローライブラリが遅い
ため、その後も非常に苦労した。
一点目については、snukeさんの記事も理解しておきたいが、なかなか難しい……。
二点目については、毎回距離を初期化して一からダイクストラしているのがまずい気がする。使い回せるところは使い回と高速化できそうな気がするが、よく分かっていない。
0 件のコメント:
コメントを投稿