脳log[20230315]

2023年03月15日 (水) [AtCoder] 精進。ABC041-D「徒競走」(青 diff)。先月(20230228)にトポロジカルソートがわからんから解けないと書いた問題。どこで手が止まっていたかというと、サンプル３の答えが 10461394944000 とべらぼうな大きさになるにもかかわらず、停止するときに１を返す再帰関数を書いたところ。１ずつ数えて間に合う数ではない。■提出 #39755560 (AC / 237 ms)。すでにゴールしたウサギの集合をキーにしてメモ化再帰をすると何が起こるかというと、前後関係のない無関係なウサギ A と B のどちらが先にゴールしたかという経路情報がいい感じに無視される。順列総当たりが許されない制約(N≦16)だけど、A<B、A>B を区別せずに２回目以降の数え上げがサボれるなら許される。■１つだけ桁違いに速い提出がある>18 ms (#1290069)。45 行目に割り算と掛け算がある(自分は足し算しかしていない)。再帰の停止条件で 1 ではなく順列を数えて返してる。入力の受け取り方も違う。自分があるウサギをキーにして先行ウサギを記録しているところ、逆に後続ウサギをメモしている(とはいえそのことに実質的な違いはないかな)。