ARC224--参加記

はじめに

おはようございます。Twil3akineです。

初めてのARCでしっかり A, B, C, E の4問を解いてちゃんと勝ちました。気持ちがいいです。

[ARC224--でしっかり勝った図]

結果サマリ

ARC224
WCPC参加人数: 6人
各問題の最速解答者(ペナルティなし):

問題	参加者名	タイム	言語
A	ShoboiNamae	5:09	C++
B	ShoboiNamae	14:16	C++
C	ShoboiNamae	37:37	C++
D	-	-	-
E	nsubaru	94:18	Java
F	-	-	-
G	-	-	-

今週の出題

A問題

問題ページ: A - Attach 00

問題文を表示

【問題文】

以下の $2$ つの条件を満たす正の整数 $n$ の最小値を求めてください。

$n$ は $K$ の倍数である。
$n$ の十進表記には、0 が $2$ 文字以上連続して現れる。 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

【制約】

$1 \leq T \leq 10^5$
$1 \leq K \leq 10^9$
入力はすべて整数

【入力】

入力は以下の形式で標準入力から与えられる。ここで $case_i$ は $i$ 個目のテストケースを意味する。

$T \\ case_1 \\ \vdots \\ case_T \\$

各テストケースは以下の形式で与えられる。

$K$

【出力】

$T$ 行出力せよ。 $i$ 行目には $i$ 個目のテストケースの答えを出力せよ。

$K \times 100$ は必ず条件を満たします。

ということは、それまで全探索すれば良いです。

1ケースにつき最大100個の倍数を調べればよく、それぞれの桁数は最大12桁です。したがって、 $T \le 10^5$ より、計算量はおよそ $12 \times 100 \times 10^5 = 1.2 \times 10^8$ となり、 $2$ 秒以内に解くことができます。

B問題

問題ページ: B - Adjacent Tiles

問題文を表示

【問題文】

同じ大きさの正方形のタイル $N$ 枚を、平面上に重ならないように配置します。

このとき、一辺を完全に共有している相異なるタイルのペアの個数は最大でいくつになりますか？ただし、タイルのペア $(a,b)$ が一辺を完全に共有するとは、 $a$ のある辺と $b$ のある辺が完全に一致することをいいます。 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

【制約】

$1 \le T \le 2 \times 10^5$
$1 \le N \le 10^{18}$
入力はすべて整数

【入力】

入力は以下の形式で標準入力から与えられる。ここで $case_i$ は $i$ 個目のテストケースを意味する。

$T \\ case_1 \\ case_2 \\ \vdots \\ case_T \\$

各テストケースは以下の形式で与えられる。

$N$

【出力】

$T$ 行出力せよ。 $i$ 行目には $i$ 個目のテストケースの答えを出力せよ。

$X \times Y$ の大きさの長方形が持つ共有する辺の数は $X(Y-1)+Y(X-1)$ 本です。

一辺の長さが $n$ の正方形の場合は、 $2n(n-1)$ 本になります。

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

そこで、 $s=\lfloor\sqrt N\rfloor$ とします。

次に、正方形からそのまま一辺を伸ばすことを考えます。 $q=\left\lfloor\frac Ns\right\rfloor$ とすると、まず $s\times q$ の長方形を作れます。

この長方形が持つ共有する辺の数は、 $s(q-1)+q(s-1)$ 本です。

残っているタイルの枚数を $r=N-sq$ とします。

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

最初のタイルは長方形と一辺を共有し、それ以降のタイルは長方形と一辺、直前に追加したタイルと一辺を共有します。

したがって、追加される共有辺の数は $1+2(r-1)=2r-1$ 本です。

以上より、答えは $s(q-1)+q(s-1)+ \begin{cases} 0 & (r=0) \\ 2r-1 & (r>0) \end{cases}$ となります。

C問題

問題ページ: C - Ascending Labels

問題文を表示

【問題文】

$N$ 頂点 $M$ 辺の連結な単純無向グラフが与えられます。頂点には $1,2,\ldots,N$ の番号が付けられており、 $i$ 個目の辺は頂点 $U_i$ と頂点 $V_i$ を結びます。以下の条件をすべて満たす整数列 $A=(A_1,A_2,\ldots,A_N)$ を $1$ つ構築してください。

すべての頂点 $v$ について、 $0 \le A_v \le N$ である。
$A_1=0$ である。
頂点 $1$ 以外のすべての頂点 $v$ について、 $v$ に隣接する頂点 $w$ のうち $A_w=A_v-1$ を満たすものがちょうど $1$ つ存在する。

なお、本問題の制約下で、上記の条件をすべて満たす整数列が少なくとも $1$ つ存在することが証明できます。

また、条件を満たす整数列が複数存在する場合、どれを出力しても正答とみなされます。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

【制約】

$1 \le T \le 3 \times 10^4$
$1 \le N \le 3 \times 10^5$
$N-1 \le M \le 3 \times 10^5$
$1 \le U_i < V_i \le N$
$i \neq j$ ならば $(U_i,V_i) \neq (U_j,V_j)$
与えられるグラフは連結
ひとつの入力における $N$ の総和は $3 \times 10^5$ 以下
ひとつの入力における $M$ の総和は $3 \times 10^5$ 以下
入力はすべて整数

【入力】

入力は以下の形式で標準入力から与えられる。ここで $case_i$ は $i$ 個目のテストケースを意味する。

$T \\ case_1 \\ case_2 \\ \vdots \\ case_T \\$

各テストケースは以下の形式で与えられる。

$N \; M \\ U_1 \; V_1 \\ U_2 \; V_2 \\ \vdots \\ U_M \; V_M \\$

【出力】

$T$ 行出力せよ。 $i$ 行目には $i$ 個目のテストケースの答えを出力せよ。各テストケースについて、条件を満たす整数列 $A$ を以下の形式で出力せよ。

$A_1 \; A_2 \; \dots \; A_N$

見た感じ、BFSで通りそうだったのでまずBFSで出してみました。嘘解法でした。

BFSの距離を $A_v$ とすると、距離が一つ小さい隣接頂点が複数存在する場合があるため、条件を満たしません。

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

頂点 $v$ の親は深さがちょうど一つ小さいため、 $A_w=A_v-1$ を満たします。

また、無向グラフのDFSにおいて、DFS木に含まれない辺は祖先と子孫を結ぶ辺になります。

$v$ より深さがちょうど一つ小さい祖先は、 $v$ の親しか存在しません。

したがって、 $A_w=A_v-1$ を満たす隣接頂点は、DFS木上の親のちょうど一つになります。

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

D問題

問題ページ: D - Angst for All Pairs

解けなかったので割愛させてもらいます。

条件文が本当に何を言っているのか分かりませんでした。悲しい。

E問題

問題ページ: E - ABC|AB|A

問題文を表示

【問題文】

A, B, C からなる文字列 $S$ が与えられます。

以下の操作を $0$ 回以上何回でも行えます。

$S$ から A または AB または ABC である部分文字列 (連続部分列) を $1$ つ選択して削除する。残った文字は順序を保って連結される。

最終的な $S$ の長さとして達成可能な最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

【制約】

$T$ は $1$ 以上 $10^5$ 以下の整数
$S$ は A, B, C からなる長さ $1$ 以上 $10^6$ 以下の文字列
ひとつの入力における $|S|$ の総和は $10^6$ 以下

【入力】

入力は以下の形式で標準入力から与えられる。ここで $case_i$ は $i$ 個目のテストケースを意味する。

$T \\ case_1 \\ case_2 \\ \vdots \\ case_T \\$

各テストケースは以下の形式で与えられる。

$S$

【出力】

$T$ 行出力せよ。 $i$ 行目には $i$ 個目のテストケースの答えを出力せよ。

ずっとD問題の読解に齧り付いていたのですが、ふとE問題を一切見ていないことに気付き、見に行くと簡単すぎてとても悲しくなりました。

最初からこっちを見ておけば…

文字列を後ろから見て、まだ削除されていない文字をスタックで管理します。

B, C はスタックに追加します。
A が来たら、スタックの先頭が B なら AB として削除し、さらに次が C なら ABC として削除します。A はスタックに追加しません。

最後にスタックに残った文字数が答えです。

最後に

今回のARCはなかなかの早解き回で、序盤にはAtCoder Predictorも壊れていて焦りましたが、しっかり勝つことができたので良かったです。

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

それでは。