2022-12-01から1ヶ月間の記事一覧
まずは条件を整理する。 インデックス があって( ) 、 から までで条件が「2」のとき、長さ1に 両方を含むことはできないので明らかに0通り。 から までの条件が「1」で までの条件が「2」のとき までに2種類を含むので0通り。 以上から答えが「0」のとき…
。をの素因数の集合とする。 が答え。 とは互いに素なので両方が、の素因数の倍数であることはない。 またがの倍数なのでがの倍数の場合、もの倍数。 よってとは共にの倍数ではない。 以上からとにある数を足すことで両方をの倍数にできる。 のすべての素因…
にたいしてを最大値として採用できるように、かつをできるだけ小さくするを求めて、これらの最小値が答え。 どうやって計算するか。 2進数で考える。 より30桁考えれば良い。上の桁から決めていきたいので、以下では左から0,1,2..桁目と数えることとする。 …
グラフを作ってからメモ化再帰で答えをもとめる。 数字が大きいところにしか辺を貼れないので、グラフはDAGになる。 あるマスから行または列の、自分の次に数が大きいマス(複数ありうる)に辺を貼る。 「自分の次に数が大きいマス」にだけ辺を貼れば良い。…