AtCoder Beginner Contest 089

Updated:

AtCoder Beginner Contest 089

Source codes

Solutions

A - Grouping 2

$N/3$。

B - Hina Arare

S[i] のうち Y が含まれるかを調べる。

ポイント

cin >> N; をしていなかった。慌てすぎ。てへへ。

C - March

真面目にカウントして 3 重ループを回す。

実装のポイント

カウントの仕方、ループの回し方がよくなかった。 string S = "MARCH" として、 if (S[j] = T[i][0]) cnt[j]++ とするべきだった。この方が実装早い。

D - Practical Skill Test

問題文が少々分かりにくい。 $X$ が書かれている点を $P_X$ と表記する。

$Q \leq 10^5$ なので、それぞれのクエリには $O(1)$ や $O(\log (HW))$ で応答したい。大事なのは $P_X$ と $P_{X+D}$ と距離なのであって、グリッドではない。そこで $X\%D$ ごとに隣りの点との距離を vector<ll> V[100010] で持っておく。あとは vector<ll> sum[100010] を imos 法で作ると、 $sum[L[i]\%D][R[i]/D] - sum[L[i]\%D][L[i]/D]$ でもとまる。計算量は $O(HW + Q \cdot 1)$ である。

ポイント

最後油断して $R[i]$ を $L[i]$ にしてしまった。

実装のポイント

2 次元配列を用意する必要はない。 1 次元配列で十分。

$DP[i] = i$ から $+D$ していき「限界」まで飛んだ時にかかるコスト

として、メモ化再帰すれば十分。実装量が減る。

Others

50 位でした。 Emacs より提出遅いなまだ。 VSCode もう少し慣れていきたい。