geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 287 備忘録

ABC Rolling Hash グラフ

コンテストページ: https://atcoder.jp/contests/abc287
コンテスト中AC: A〜E

C - Path Graph?

パスグラフのとき、両端の次数は1で、それ以外は2です。また、連結成分の数はただ1つになる必要があります。
以上から、以下がパスグラフである条件です。

  • 次数1の頂点がちょうど2つ存在し、その他の頂点の次数は全て2
  • 連結成分がただ1つ

上は、次数をカウントしていくことで判定でき、下はUnion Findにより、判定できます。

実装: Submission #38391709 - UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)

D - Match or Not

S,Tの先頭及び末尾からの何文字目までが一致させられるかをあらかじめ計算しておき、その情報を合体させます。

具体的には、bool型の配列L,Rを以下のように定義します。

L_i:=Sの先頭からi文字目とTの先頭からi文字目までを一致させられるならtrue、一致させられないならfalse

とし、同様に、先頭を末尾に言い換えたものをRとします。
ここで、便宜上L_0 = R_{N+1}=trueとします。

x=kの場合には、一致できるかをL_k \wedge R_{k+1}として判定できます。

L,Rは、先頭または末尾の端から順に調べていき、i番目のS_i,T_iについて、

  • S_i \neq ? \wedge T_i \neq ? \wedge S_i \neq T_i

となったらそれ以降は全て一致させられなくなるので、全てfalseで、それまでは全てtrueとします。

実装: Submission #38402444 - UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)

E - Karuta

少し前の問題でRolling Hashを使っていたので、Rolling Hashで解きました。

S_iのj文字目までのハッシュ値をH_{i,j}とします。

全てのi,j\ (1\leq i \leq N,\ 1\leq j\leq |S_i |)について、H_{i,j}の個数を連想配列でカウントします。

改めて、i番目の文字列について、H_{i,1},\ H_{i,2},\ \cdots ,\ H_{i,|S_i|}の個数が全体で何個あるかを調べていき、ハッシュ値の数が2以上であるものは自分以外にもそのハッシュ値を持つ文字列が存在することを示しているので、その中で最大のものが答えになります。

実装: Submission #38475994 - UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)

(コンテスト後に実装見直し)