5完
各問題
A - Find Takahashi
1本目から順番に見ていって、そこまでで一番高いものより高い橋ならそれが回答の候補、を最後まで繰り返します。
A問題にfor使わせるの完全に解禁されたんですね?
B - ABC-DEF
最終的な答えを 998244353 で割るのも、計算途中に割るのも同じことなのでそうします。
具体的な実装としては、全ての数値をac-libraryのmintに突っ込んで計算すればよいです()
C - Counting Squares
頂点 (r1, c1)
とそれと辺をなす頂点の候補 (r2, c2)
(ただし重複して数えることを防ぐため r1 < r2 and c1 < c2
とする)を全探索します。
頂点は反時計回りに決定していくとすれば、正方形なので残りの頂点は一つに定まります。
D - Yet Another Recursive Function
今週の目玉。
メモ化再帰するだけ。
E - Sugoroku 4
x回目の試行でどのマスにいるかは単純なDPで求まります。
各回毎にゴールできる数を求めて確率(の mod 998244353)を計算し(x回目にゴールできる場合の数 / inv(2^x)
)、それを加算していったものが答えです。
F - Erase Subarrays
DPでなんとかする、というところまでしかわからず。
まとめ
苦手意識のある確率の問題が通せたのでよし。