G - Jumping sequence
解説放送を聞いてAC。
45度回転すればx軸、y軸を独立に考えることができ、部分和問題に帰着できる。
マンハッタン距離を扱うときに45度回転はよく登場するけれど、こういう風に使うことがあるとは知らなかった。
bitset高速化の方針でACしたけれど、MLEなども気を付けねばならず結構大変だった。
解説放送後半にある、部分和問題のもっと計算量の良い解法はこれから理解したい。→解法は一応理解したけど、実装が大変そうなので放置します。
H - Count Multiset
解説放送を聞いてAC。
ヤング図形との対応に気付けばDPへ持ち込むことはそれほど難しくなさそう。
また、分割数と似ていると思えれば、（分割数の求め方を知っていれば）ヤング図形との対応を考えるのは自然だった。
というわけで、「写像12相」をちゃんと理解していれば解ける問題、と言えそうだけど、ちゃんと理解するのは結構大変。
0 件のコメント:
コメントを投稿