ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

バイナリ法

Educational DP Contest / DP まとめコンテスト R - Walk

問題 提出コード 解法 与えられた入力をの行列とみなし、これを乗すれば、その行列の値の総和が、長さのパスの総数になります。 あとは、バイナリ法なるものを利用して高速に計算することができれば、答えとなります。 冪乗 - Wikipedia 感想 この計算をする…

Typical DP Contest M - 家

問題 提出コード 解法 bitDPです。だんだん詰め合わせ感が増えてきました。 同じ階層でからに移動するパターン数 とすると、これをの行列に見立てて乗すると、が答えになります。 を求めることさえできれば、あとはこの行列式のを求めていき、程度で答えが求…

AOJ 2372 - IkaNumber

問題 提出コード 自力でなんとか解けました!時間は4時間くらいかかりました… くコ:彡 くコ:彡 くコ:彡 くコ:彡 解法 問題を読んだだけではかなり自由度が高いので、一つ一つ見ていくことにします。 まず、Taroの家の位置を固定します。 Taroの家、にんじん…

ABC009 D - 漸化式

D - 漸化式 提出コード かなり難しいです。ほぼ数学です。 漸化式をうまく行列に落とし込んで表現する方法を考えます。 まず、前提条件として非負整数はXORとANDに関して半環をなす、ということを理解している必要があります。 XORを足し算、ANDを掛け算のよ…