geam1113’s diary

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

AtCoder Regular Contest 158 備忘録

コンテストページ: AtCoder Regular Contest 158 - AtCoder

コンテスト中AC: A

A - +3 +5 +7

3つの値を同じにする問題は割と良く見る気がします。そして、この系統の問題は、差をどのように詰めるのか、という視点で見ると解ける場合が多いです。

今回、x_2-x_1及びx_3-x_2をそれぞれp,qとおきます。目標は、p=q=0にすることです。

操作によってp,qがどのように変化するか考えます。例えば、(+3, +5, +7)の操作の場合、p,qはそれぞれ+2, +2されます。

操作として考え得る6通りについて、(p,q)がどのように変化するか、その変化量を書き出します。

(+2, +2), (+4, -2), (-2, +4), (+2, -4), (-4, +2), (-2, -2)

ここからわかることとして、p,qは偶数しか変化しません。
そこで、p,qいずれかが奇数である場合、0にするのは不可能です。

以下、p,qが偶数である場合を考えます。
わかりやすくするため、p,q及び操作による変化量を全て2で割っておきます。
変化量は、
(+1, +1), (+2, -1), (-1, +2), (+1, -2), (-2, +1), (-1, -1)
です。

p,qが異なる場合、(+2, -1), (-1, +2), (+1, -2), (-2, +1)のいずれかでp=qにした後、(+1, +1), (-1, -1)のいずれかで0にすることになります。

そこで、次はqpの差を考えます。r=q-pとおきます。

(+2, -1), (-1, +2), (+1, -2), (-2, +1)では、rは3の倍数ずつしか変化しません。そこで、p,qが3の倍数でない場合、0にすることは不可能です。

以下、3の倍数であるとします。
このままだと変化量が多く、ややこしいので、適切に値を入れ替えて、p,qが非負整数かつ、p\leq qとなるようにします。


[補足]
値を入れ替えてもよい理由を説明します。
例えばx_1,x_2,x_3にそれぞれ(+3, +5, +7)するという操作を考えます。

値をx_2,x_1,x_3と入れ替えた場合に、操作についても入れ替えて(+5, +3, +7)にすると、先程の操作を再現できます。

値を入れ替えることで不可能となるような操作が無いことから、値を入れ替えても問題ない、と言えると思います。


こうしておくことで、選ぶべき変化量は(+1, -2), (-1, -1)に限定されます。

r\geq 0になっていることから、最小の操作回数は以下のようになります。

  • (+1, -2)を\frac{r}{3}回してr=0、すなわちp=qにする。
  • (-1,-1)をp+\frac{r}{3}回してp=q=0、すなわちx_1 = x_2 = x_3にする。

実装: Submission #39673899 - AtCoder Regular Contest 158

AtCoder Beginner Contest 292 備忘録

コンテストページ: AtCoder Beginner Contest 292 - AtCoder

コンテスト中AC: A〜D
コンテスト後にE,Fを解説ACしました。要点ををまとめておきます。

D - Unicyclic Components

Union-Findで連結成分の何らかのデータを統合していく問題はよく出題されます。今回は、連結成分に属する辺の個数をデータとして持ちます。

e=(u,v)が与えられた時、u,vが同一の連結成分に属するなら、その連結成分の辺の個数を+1する。そうでないなら、u,vをマージした後に+1すれば良いです。
マージする際は、辺の個数のデータを統合します。

データは常に、Union-Findの各連結成分における根に保持するよう調整が必要なので、その点は注意が必要です。

実装: Submission #39422939 - AtCoder Beginner Contest 292

E - Transitivity

公式解説の要点

  • ある頂点について、その頂点から(元々隣接していない)全ての到達可能な頂点に有向辺を新たに追加する必要がある。

  • ある頂点から辺を新たに追加しても到達可能な頂点の集合は変わらない。(ある辺を追加することで新たに辿り着ける頂点が増えるということはない)

  • 以上から、全ての頂点からBFSして、到達可能であって距離が2以上の頂点をカウントすればよい。

実装: Submission #39524065 - AtCoder Beginner Contest 292

F - Regular Triangle Inside a Rectangle

公式解説では、正三角形の縦の長さはl\sin\thetaとなっていました(2023/3/9現在)が、自分の考え方ではl\sin(\theta + 60^{\circ})だったので、それで書きます。

要点

  • 正三角形の頂点のうち1つは、最も左下、右下、左上、右上のいずれかとなる(鳩の巣原理により、証明できる) 。正三角形に平行移動と反転を行うことで、長方形の左下の頂点と正三角形の頂点を一致させることができる。

  • 長方形の下の辺と正三角形の下の辺の角度を\thetaとすると、辺の長さlの正三角形の縦の長さ、横の長さ、角度の制約から以下の条件が得られる。
    0\lt l\cos \theta \leq A
    0\lt l\sin (\theta + 60^\circ) \leq B
    0 ^\circ \leq \theta \leq 30^\circ

  • 上記式に対して二分探索を行えばよい。角度の条件の範囲内において、\cos\thetaは単調減少、\sin\thetaは単調増加なので、0\lt l\cos \theta \leq A0 ^\circ \leq \theta \leq 30^\circを同時に満たす\thetaのうち、最大のものが0\lt l\sin (\theta+60^\circ )\leq Bを満たすか判定する。

自分の補足

0\lt l\cos \theta \leq A0 ^\circ \leq \theta \leq 30^\circを同時に満たす最大の\thetaの求め方
0 ^\circ \leq \theta \leq 30^\circにおいて、\cos\thetaは、\frac{\sqrt{3}}{2}\leq \cos\theta \leq 1です。

0\lt l\cos \theta \leq A0 ^\circ \leq \theta \leq 30^\circを同時に満たす最大の\thetaは、
\frac{A}{l}\lt \frac{\sqrt{3}}{2}なら、解なし
\frac{\sqrt{3}}{2} \leq \frac{A}{l} \leq 1 なら、 \frac{A}{l}
 \frac{A}{l}\geq  1 なら、1
です。

実装: Submission #39504396 - AtCoder Beginner Contest 292

AtCoder Beginner Contest 289 備忘録

コンテストページ: Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 289) - AtCoder

コンテスト中AC: A〜E
コンテスト後にFをAC。WAが出たので、解説を見たが、解法は合っていて実装が間違っていた。

E - Swap Places

高橋くんがいる頂点と青木くんのいる頂点の組について、その状態となるのに最小の操作回数のみを記録していればよく、逆に、同じ状態になるのに、それより操作回数が大きくなる場合は無視できます。

これより、全頂点の組について、その状態になるための最小の操作回数を調べていく解法が考えられます。

状態と遷移の関係を有向グラフとみなすことができるので、BFSにより最小回数を決定していくことができます。

この有向グラフの頂点数は全頂点対となるのでN^2個となるのはわかりますが、辺数はコンテスト中分かりませんでした。(ただ、解法として考えうるのがこの方法しかなかったので、提出しました。)

辺数は、公式解説で見積もり方が書いてありました。こちらにもメモしておきます。

  • あるグラフG=(V,E)の全頂点対について、頂点対から出る全ての辺の合計は4M^2以下となる

実装: Submission #38811108 - Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 289)

F - Teleporter Takahashi

操作をシミュレートすると、下のような感じの各辺がx軸とy軸に平行な長方形領域が得られます。
oxoxoxo
xxxxxxx
oxoxoxo
xxxxxxx
oxoxoxo

上の1文字を長方形領域に含まれる格子点の1つとみなします。
oが(s_x , s_y)が移動可能な場所、xが不可能な場所です。また、この領域の縦と横の長さは問題で与えられる長方形Rによって異なります。

この長方形領域の左端、右端のx座標をそれぞれX_0, X_1、下端、上端のy座標をY_0, Y_1とします。

oが現れるのは、この長方形領域内の格子点であって、格子点(x,y)について、x-X_0が2の倍数かつ、y-Y_0も2の倍数の時となります。

操作終了後に(t_x , t_y)がoの場所に存在すれば、(s_x , s_y)から移動可能ということになります。

i回目の操作終了後のX_0X_0[i]とします。X_1,Y_0,Y_1も同様とします。
i回目の操作終了後に(t_x , t_y)がoであるための条件は以下です。

  • X_0[i]\leq t_x \leq X_1[i]
  • Y_0[i]\leq t_y \leq Y_1[i]
  • (t_x-X_0) \ mod\ 2 \equiv 0
  • (t_y-Y_0) \ mod\ 2 \equiv 0

問題文の条件から、10^6回しても上記条件を満たすものが存在しない場合はNoです。

ところで、操作に従ってX_0[i],X_1[i],Y_0[i],Y_1[i]を計算できる必要があります。
これは、端から端への移動になるので、以下のように計算できます。

X_0[i] \leftarrow min(|a-X_0[i-1]|,|b-X_0[i-1]|,|a-X_1[i-1]|,|b-X_1[i-1]|)
X_1[i] \leftarrow max(|a-X_0[i-1]|,|b-X_0[i-1]|,|a-X_1[i-1]|,|b-X_1[i-1]|)

Y_0[i],Y_1[i]についても、a,bc,dに変えて同じように計算できます。

では、Yesの場合に操作の列の構築方法を記載します。
前準備として、操作終了までのX_0[i],X_1[i],Y_0[i],Y_1[i]を全て記録しておきます。

i番目の操作の直後の点を(x_{i},y_{i})とします。i番目の操作でR上の格子点(m_x,m_y)を選んだとします。
操作前の点(x_{i-1},y_{i-1})

x_{i-1} = m_x + m_x  - x_i = 2m_x - x_i

同様に、

y_{i-1} = m_y + m_y  - y_i = 2m_y - y_i

と計算できます。
ここで、(x_{i-1},y_{i-1})が満たすべき条件は、

X_0[i-1] \leq x_{i-1} \leq X_1[i-1]
Y_0[i-1] \leq y_{i-1} \leq Y_1[i-1]

なので、

X_0[i-1] \leq 2m_x - x_i \leq X_1[i-1] \Rightarrow \lceil \frac{X_0[i-1]+x_i}{2} \rceil \leq m_x \leq \lfloor \frac{X_1[i-1]+x_i}{2} \rfloor

同様に、 \lceil \frac{Y_0[i-1]+y_i}{2} \rceil \leq m_y \leq \lfloor \frac{Y_1[i-1]+y_i}{2} \rfloor

ここで、a\leq m_x \leq bc\leq m_y \leq dも満たす必要があります。従って、(m_x,m_y)が満たすべき条件は、

max(a,\ \lceil \frac{X_0[i-1]+x_i}{2} \rceil) \leq m_x \leq  min(b,\ \lfloor \frac{X_1[i-1]+x_i}{2} \rfloor)
max(c,\ \lceil \frac{Y_0[i-1]+y_i}{2} \rceil) \leq m_y \leq  min(d,\ \lfloor \frac{Y_1[i-1]+y_i }{2} \rfloor)

です。この条件内ならどの点を選んでも良いので、x,yいずれも最小の座標を選ぶと、

m_x \leftarrow max(a,\ \lceil \frac{X_0[i-1]+x_i}{2} \rceil)
m_y \leftarrow max(c,\ \lceil \frac{Y_0[i-1]+y_i}{2}\rceil)

とできます。
この計算を繰り返していくと操作の列を構築できます。

実装: https://atcoder.jp/contests/abc289/submissions/38933851

AtCoder Beginner Contest 291 備忘録

コンテストページ: https://atcoder.jp/contests/abc291
コンテスト中AC:A〜E
Fは大方の解法まではコンテスト中に辿りついたが、最後の詰めと実装が間に合わず。コンテスト後に自力AC。

D - Flip Cards

カードの状態は表か裏かの2通りしかなく、状態数が少ないです。また、先頭(または末尾)から順に表裏を決めていくことができます。これより、DPが使えます。

dp[i][j]:=i番目のカードの状態がjの時の、i番目までのカードの表裏の状態の総数。但し、j=\{0,1\}であり、j=0の時はカードは表向き、j=1の時はカードは裏向き

イメージとしては後述する数列Tの個数を数え上げる問題とみなすと良いです。

数列Tについて、T_i=0ならi番目のカードは表向き、T_i=1なら裏向きとします。例えば、1〜4番目のカードについて、表、裏、裏、表ならT=\{0,1,1,0\}です。

この状態で、5枚目のカードを表向きにしたとすると、T=\{0,1,1,0,0\}となり、裏向きにしたとすると、T=\{0,1,1,0,1\}となります。

この考え方で遷移を考えると、例えば、A_{i-1}\neq A_iなら、i-1番目が表の全ての数列について、数列の末尾に0を追加(すなわち、A_iを表向きに)して新たな数列ができるので、
dp[i][0] += dp[i-1][0]
という感じで遷移できます。

初期値は、i=1の時、\{0\}\{1\}の2つの数列があるので、dp[1][0]\leftarrow 1,\ dp[1][1]\leftarrow 1とし、あとは0にします。

答えは、dp[N][0]+dp[N][1]です。

実装: Submission #39251335 - AtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS)

E - Find Permutation

小さい順に数列の値を決定していくことを考えると、問題で与えられる大小関係に従って、決定順序を規定できます。そこで、この順序関係を有向辺とみなし、X_i \rightarrow Y_iという有向辺がある有向グラフを考えます。

まず、閉路を含む場合は矛盾が生じるため解なしとなりますが、制約上このケースはありません。(余談:この記事を書いているときに制約に気づきました。)

次に、順序が同列のものが存在すると、どちらから先に値を決定してもよくなるので、Aを一意に特定できなくなり、Noとなります。
順序が同列のものが存在する例として、最もシンプルな形が入力例2です。

順序が同列のものが存在することの判定方法ですが、トポロジカルソートが利用できます。トポロジカルソートの詳細な説明はWebなどで検索すると出てくるため、ここでは割愛します。

トポロジカルソートで入次数0の頂点をキューに追加する際、同時に2つ以上の頂点がキューに入った場合、それらの順序を規定できません。従って、トポロジカルソートにおけるキューのサイズが2以上となったら、その時点で答えをNoにすれば良いです。

実装: Submission #39259983 - AtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS)

F - Teleporter and Closed off

自分より番号が大きい頂点にしか辺が無く、更に辺が各頂点で最大でも10本しかないことを利用します。

頂点kを通らないことにした場合、kを飛び越えるような移動は、大雑把に考えてもmax(k-10,1) \leq u \lt kの範囲の頂点uから、v\gt kとなるような頂点vへの移動に限定されます。つまり、

1uvN

という移動経路を考えれば良いです。この際の1からNへの最短距離を

1からuへの最短距離+uからvへの移動距離+vからNへの最短距離

と分解すれば、

  • 頂点1から各頂点への最短距離d^1_i
  • 頂点Nからの最短距離d^N_i

を予め求めておくことで、

求めたい最短距離をd^1_u + 1+d^N_vとして、O(1)で計算できます。

d^1は元のグラフをBFSする事で求められ、d^Nは元のグラフの有向辺を全て逆向きにしてからBFSすることで求められます。

kを固定した時の最短距離はuuから出る辺を全探索すればよいです。
この計算量はM=10のときがワーストケースですが、それでも10^2であり、2\leq k \leq N-1の全てについて調べても10^7くらいなので、間に合います。

コンテスト中は大雑把に考えていましたが、正確にはuの範囲はmax(k-M-1,1) \leq u \lt kだと思います。辺数もMなので、計算量はO(NM^2)になると思います。

実装: Submission #39279264 - AtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS)

AtCoder Beginner Contest 288 備忘録

コンテストページ: Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288) - AtCoder
コンテスト中AC: A〜C
コンテスト後自力AC: D〜F

D - Range Add Query

0-indexedとします。
Xを愚直に全て0にできるか試すときどうするかを考えると、端から順に0にしていく方法が思い浮かびます。

例えば、n=8, K=3としてシミュレートしてみます。
まず、i=0を0にするため、i=0,1,2-X_0を足します。

X=\{0,\ X_1-X_0,\ X_2-X_0,\ X_3,\ \cdots \}

次はi=1,2,3-(X_1 - X_0)を足す…としたいところですが、足される項が増えてややこしいので、まず、X_0i=1,2,3に足しておきます。

X=\{0,\ X_1,\ X_2,\ X_3+X_0,\ \cdots \}

それでは先程と同様に、i=1,2,3-X_1を足し、i=2,3,4X_1を足します。

X=\{0,\ 0,\ X_2,\ X_3+X_0,\ X_4+X_1,\ \cdots \}

これを繰り返しと、最終的に以下のようになります。

X=\{0,\ \cdots ,\ 0,\ X_0+X_3+X_6,\ X_1+X_4+X_7,\ X_2+X_5+X_8\}

このようにシミュレートしてみると以下がわかります。

  • X_{i+K}X_iが足され、末尾K項にi\ mod\ Kが等しいものの累積和が構築される

最終的に末尾K項が等しい場合には、Xを0にすることが可能です。

これより、各クエリのA_{l_i},\ \cdots ,\ A_{r_i}について、mod\ Kが等しいiの累積和が全て同じかを判定すればよいです。

i\ mod\ Kが等しいものについてのAの累積和を予め計算しておけば、区間の累積和はO(1)で求められます。

よって、各クエリO(K)で判定できます。

実装: Submission #38649675 - Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)

E - Wish List

まず、

  • 状況が変化していき、複雑なこと
  • Nが小さいこと

から、貪欲法よりもDPっぽいなと当たりをつけます。

A_iをとることを考えたとき、iより前が何個取られているかで、どのC_iとなるか変化します。また、前に取られた個数が同じなら、どれが取られていても状況は同じなので、情報をひとまとめにできます。

ここから、以下のようなDPを考えます。
dp[i][j]:=A_iまでをj個取った時の金額の最小値

dp[i][j]を更新することを考えます。
iより前は既にj-1個取られていたとしたら、A_ii-(j-1)番目に移動しているはずなので、A_i + C_{i-j+1}の金額が必要なはず、と思ってしまいますが、これは誤りです。
なぜなら、iより前が0,1,\cdots ,j-2個のいずれかが取られた直後にA_iを取ることも可能だからです。

ここが重要なポイントで、i番目より前に0,\ 1,\ \cdots ,\ j-1個とられているような状況について、どのタイミングでA_iを取ったことにしてもよいです。

理由は直感的になりますが、まず、A_iをとるタイミングを変えてもiより前のとる順番には影響を与えません。
次に、A_iをとることで、iより後ろがずれて、とりたい位置でとれなくなってしまうのではないかと心配になります。
その場合は、先に後ろのものをとっておけば良いです。その後ろのものをとることで、その後ろより更に後ろがずれるなら、更にその後ろを先に取れば良いです。これを繰り返せば、最終的に一番後ろになるので、いつかは矛盾なくとれるはずです。

以上から、i番目まででj-1個取られている状況で、A_iを取ってj個取られている状況にする場合、かかる金額は、

A_i + min(C_{i-j+1},\ C_{i-j+2},\ \cdots ,\ C_i)

とできます。
これはSegment TreeでRMQを処理すればよいです。

以上から、DPテーブルをi=1,2,\cdots Nの順に以下のように更新できます(初期値は、dp[0][0]が0でそれ以外は\infty)。

  • A_iをとる場合
    dp[i][j] \leftarrow min(dp[i][j],\ dp[i-1][j-1]+A_i + min(C_{i-j+1},\ C_{i-j+2},\ \cdots ,\ C_i))

  • A_iをとらない場合
    dp[i][j] \leftarrow min(dp[i][j],\ dp[i-1][j])

但し、iXに含まれる場合はとらない選択をできません。

実装: Submission #38728052 - Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)

F - Integer Division

説明のため、乗算の×を挿入することを仕切りを挿入すると表現します。
例えば、12|3|45は、12\times 3\times 45です。

X_{j+1}\cdots X_iを10進数とみなしたものをb_{i,j}とします。これは、X_jの後ろに仕切りを入れ、その後i番目まで仕切りがない場合の10進数と捉えることができます。

i=1,2,\cdots , Nの順に見ていくとき、最後に仕切った場所が同じものについては、同じ10進数をかけることになります。

具体例を示します。X=12345として、i=5を考えたとき、最後にj=3の後ろで区切ったものを考えます。
j=3の後ろで区切った時のそれ以前の区切り方は、
123,\ 12|3,\ 1|23,\ 1|2|3の4通りとなりますが、それより後の区切りが無いためこれらには全て45が掛けられることになります。

今回は、総和を求める問題なので、以下のように解釈できます。

123\times 45 + 12\times 3 \times 45 + 1\times 23\times 45 + 1\times 2\times 3 \times 45

これを式変形すると、

(123 + 12\times 3 + 1\times 23 + 1\times 2\times 3) \times 45

カッコ内は3番目まででできる全ての区切り方の積の総和です。そこで、

a_i :=i番目までできる全ての区切り方の積の総和

とおけば、

a_3 b_{3,5}

と表現できます。

例示したXで最終的に求めたい値は、

a_5=a_0 b_{0,5}+a_1 b_{1,5}+a_2 b_{2,5}+a_3 b_{3,5}+a_4 b_{4,5}+a_5 b_{5,5}

です。なお、a_0X_1の前に区切りを入れたと考え、便宜上a_0 = 1とします。また、b_{k,k} = 0と考えます。

ところで、
a_4 = a_0 b_{0,4}+a_1 b_{1,4}+a_2 b_{2,4}+a_3 b_{3,4}+a_4 b_{4,4}

なので、

b_{0,4},\ b_{1,4},\ b_{2,4},\ b_{3,4},\ b_{4,4}

から、

b_{0,5},\ b_{1,5},\ b_{2,5},\ b_{3,5},\ b_{4,5}

に変化させることができれば、a_4からa_5を計算できます。

この方法ですが、b_{j,i-1}からb_{j,i}を計算する場合、

b_{j,i}\leftarrow b_{j,i-1}\times 10 + X_{i+1}

として計算できます。
例の場合、X_5 = 5であることから、

a_5 = a_0 (b_{0,4}\times 10+5)+a_1 (b_{1,4}\times 10+5)+a_2 (b_{2,4}\times 10+5)+a_3 (b_{3,4}\times 10 + 5)+a_4 (b_{4,4}\times 10 + 5)

式変形すると、

10(a_0 b_{0,4}+a_1 b_{1,4}+a_2 b_{2,4}+a_3 b_{3,4}+a_4 b_{4,4})+5(a_0 + a_1 + a_2 + a_3 + a_4)
=10a_4+5(a_0 + a_1 + a_2 + a_3 + a_4)

aの累積和をSとすれば、

a_5 = 10a_4 + 5S_4

となります。

一般化すると、

a_{i} = 10a_{i-1}+X_{i}S_{i-1}

となり、この漸化式を解いていけば、答えを求めることができます。

実装: Submission #38705016 - Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)

AtCoder Beginner Contest 287 備忘録

コンテストページ: 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_ij文字目までのハッシュ値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)

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

AtCoder Beginner Contest 286 備忘録

コンテストページ: UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder
コンテスト中AC: A〜E

D - Money in Hand

公式解説とは異なる方法でO(NX)とする方法を書いておきます。

Sliding Window Agrregationを使います。

DP遷移の一例を示します。
A_i = 4, B_i = 2, X=24の時、i-1番目のj\ mod\ 3 = 0のDP値を集めて配列とします。
C=\{dp[i-1][0],\    dp[i-1][4],\ dp[i-1][8],\ dp[i-1][12],\ dp[i-1][16],\ dp[i-1][20],\ dp[i-1][24]\}

同様にi番目のj\ mod\ 3 = 0のDPテーブルの更新を考えると

dp[i][0] \leftarrow C_0

dp[i][4] \leftarrow C_0 \vee C_1

dp[i][8] \leftarrow C_0 \vee C_1 \vee C_2

dp[i][12] \leftarrow C_1 \vee C_2 \vee C_3

dp[i][16] \leftarrow C_2 \vee C_3 \vee C_4

dp[i][20] \leftarrow C_3 \vee C_4 \vee C_5

dp[i][24] \leftarrow C_4 \vee C_5 \vee C_6

このように、j\ mod\ A_iが等しいものだけを集めると、最初の方を除いては値を求めるための区間は、長さが一定のまま1つずつ右にずれていくだけということがわかります。

そのため、スライド最小値を一般化したSliding Window Agrregationが使えます。
半群やモノイドが乗せられるはずだったと思いますが、実装はモノイドにしました。モノイドの型はbooleanを、二項演算は論理演算のORを、単位元はfalseにしておけば良いです。

コンテスト中の実装: Submission #38204795 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)
Sliding Window Agrregationの実装: Submission #38292225 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)

E - Souvenir

Nが小さいので全点対間最短経路をワーシャル・フロイド法によって求めることが可能です。
お土産の価値も最短経路の求め方と似たような感じで求めることができます。
二次元配列Cを、

C[i][j]:=i,j間のお土産の価値

とおきます。
初期値として、

  • 頂点u,v間に有向辺があるなら、C[i][j] \leftarrow A_v
  • 頂点u,v間に有向辺が無いなら、C[i][j] \leftarrow 0

このようにして求めていくと、ワーシャル・フロイド法の最短距離のテーブルdistの更新の際、

  • dist[i][j] \gt dist[i][k]+dist[k][j]なら、C[i][j]\leftarrow C[i][k] + C[k][j]

  • dist[i][j] = dist[i][k]+dist[k][j]なら、C[i][j]\leftarrow max(C[i][j], C[i][k] + C[k][j])

と更新すれば良いです。
なお、このままだと始点の価値が足されていないので、s_i,\ t_iの始点の価値を足して、C_{s_i,\ t_i}+A_{s_i}が求める価値です。

実装: Submission #38211470 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)