賢い漸化式
三乗の解法はすぐに出てくるので、それを上手に高速化する! 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…
AtCoder
AtCoder600点
ARC-D
黄色diff
DP
数え上げ問題
入力が定数個
2^K
DP高速化
DP高速化:累積和
賢い漸化式
「総和=K」を扱う
対象を一意に定める操作列を数え上げる
全体を2倍する
いろんな DP が考えられそう! 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て (…
AtCoder
けんちょん自作問題
順列
数え上げ問題
順列の数え上げ問題
挿入DP
箱根駅伝DP
DP
二項係数
特定の場所を決め打つことで単純な場合に帰着する
個数のみわかれば遷移が作れるDP
入力が定数個
包除原理
包除原理:DP
順列をマッチングとして見る
対称性
賢い漸化式
順列の最適化・数え上げ・求解
このセットの writer をしていました 問題へのリンク 問題概要 を並び替えてできる数列 は 通りあるが、そのうち以下の条件を満たすものが何通りあるかを、1000000007 で割ったあまりを求めよ。 を満たすような がちょうど 個 を満たすような がちょうど 個 …
こないだのドワンゴからの挑戦状で、分割数を用いる問題が出題されたので、周辺の話題を整理してみました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。今回は分割数を、…