Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 275

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でなんとかする、というところまでしかわからず。

まとめ

苦手意識のある確率の問題が通せたのでよし。