ARC224-- 参加記

2026/07/12

私です。

ARC224— に参加しました。A, B, C, Eの4完です。

初めてのARC Ratedをしっかり勝てて気持ちがいいです。

$K \times 100$ は必ず末尾に $00$ を持ちます。ということは、 $K, 2K, \ldots, 100K$ を順に見て、十進表記に $00$ を含む最初のものを出せばよいです。

1ケースにつき高々100個の倍数を調べればよく、それぞれの桁数は最大12桁です。したがって、 $T \leq 10^5$ より計算量はおよそ

12 \times 100 \times 10^5 = 1.2 \times 10^8

となります。文字列にして contains("00") するだけで十分間に合います。

$X \times Y$ の長方形に並べたとき、完全に共有する辺の数は

X(Y-1)+Y(X-1)

です。

一辺が $n$ の正方形なら、共有する辺の数は

2n(n-1)

本です。これは $n$ について単調増加するので、まず作れる最大の正方形を作るのが良さそうです。

そこで、

s=\lfloor\sqrt{N}\rfloor

とします。次に、正方形からそのまま一辺を伸ばすことを考えます。

q=\left\lfloor\frac{N}{s}\right\rfloor

とすると、まず $s \times q$ の長方形を作れます。この長方形が持つ共有辺の数は

s(q-1)+q(s-1)

本です。

残っているタイルの枚数を

r=N-sq

とします。 $r>0$ の場合は、長方形の横にタイルを一列追加します。

最初の1枚は長方形と1辺を共有し、以降の1枚は長方形と直前のタイルに接するので、 $r>0$ のとき増える辺の数は $2r-1$ 本です。これを長方形の式に足せば答えになります。

つまり、答えは

s(q-1)+q(s-1)+ \begin{cases} 0 & (r=0) \\ 2r-1 & (r>0) \end{cases}

です。

最初はBFSだと思って実装を投げましたが、嘘解法でした。普通に条件を言い換えたらDFSだなぁとなりました。

BFSの距離を $A_v$ にすると、距離が1小さい隣接頂点が複数存在する場合があります。問題では $A_w=A_v-1$ を満たす隣接頂点がちょうど1つでなければならないため、これでは条件を満たしません。

そこで、頂点1を根としてDFS木を作り、各頂点のDFS木上の深さを $A_v$ にします。

頂点 $v$ の親は深さがちょうど1小さいため、 $A_w=A_v-1$ を満たします。また、無向グラフのDFSにおいて、DFS木に含まれない辺は祖先と子孫を結ぶ辺になります。

$v$ より深さがちょうど1小さい祖先は $v$ の親しか存在しません。したがって、 $A_w=A_v-1$ を満たす隣接頂点もちょうど1つになります。

よって、ただDFSを実装するだけでよいです。

本当に意味がわからないです。日本語の意味がわかりませんでした。

D問題の読解にずっと固執していましたが、ふとEを見ると簡単すぎて悲しくなりました。最初からこっちを見ておけば……。

文字列を後ろから読み、B と C をスタックに積みます。A を読んだときは、次の順番で削除します。

これで、削除しきれず残った B と C の数が答えです。

最後に

ARCはABCに比べて、問題に対する考察の比重が多めなので割と好きです。

では、また。