AtCoder Beginner Contest 089
Updated:
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 もう少し慣れていきたい。