geam1113’s diary

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

AtCoder Beginner Contest 270 参加記録

コンテストページ:https://atcoder.jp/contests/abc270

コンテスト中AC:A〜D
Eはコンテスト中は実装ミスで間に合いませんでしたが、コンテスト後に解けたので書いておきます。

D - Stones

石がX個の状態からは、石がX-A_1,X-A_2,\cdots ,X-A_K個の状態に遷移します。
そのため、石が少ない時の状態から順に高橋くんが取れる石の個数を決定していくことができれば、O(NK)くらいで解けそうだということがわかります。

普通のループを使ったDPでも解けそうですが、コンテストではメモ化再帰を使いました。

メモ化再帰にあたり、

f(X):石が残りX個の状態で、高橋くんが取れる石の最大個数

とおいて計算していきたいところですが、高橋くんのターンか青木くんのターンかで、戦略が異なります。
すなわち、

  • 高橋くんは、高橋くんが取れる石の個数を最大化したい
  • 青木くんは、高橋くんが取れる石の個数を最小化したい

そのため、どちらのターンなのかという情報を持たせます。

f(X,Y):石が残りX個、ターンの状態がYで、高橋くんが取れる石の最大個数。但し、Y=\{0,1\}で、Y=1の時は高橋くんのターンで、Y=0の時は青木くんのターン。

それでは、遷移を考えます。
各ターンにおいて、m1\leq m \leq Kかつ、A_m \leq Xを満たす最大値とします。

  • 高橋くんのターンの場合
    取れる石の個数を最大化します。また、石を取った時に、高橋くんがとれる石の個数に加算できるので、以下のようになります。
    f(X,\ 1) = max\{f(X-A_1,\ 0)+A_1,\ f(X-A_2,\ 0)+A_2,\ \cdots ,\ f(X-A_m,\ 0)+A_m \}

  • 青木くんのターンの場合
    取れる石の個数を最小化するので、以下のようになります。
    f(X,\ 0) = min\{f(X-A_1,\ 1),\ f(X-A_2,\ 1),\ \cdots ,\ f(X-A_m,\ 1) \}

遷移は以上です。
また、再帰の終了条件として、石が0個の時の値、f(0,0)=f(0,1)=0を設定しておきます。

計算量は最初にも書きましたが、各個数においてK回の計算となるので、O(NK)と思います。

Submission #35156369 - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270)
↑はコンテスト後に微修正した実装です。

E - Apple Baskets on Circle

最終的な移動回数をXとし、XNで割った商をq、余りをrとします。これは、q周してから残りr回移動するという風に考えられます。
0\leq r \lt Nであることから、qを求められれば、残りr回はシミュレーションできます。

qを求める方法を考えます。
例としてA=\{5,1,3,3\}を考えます。

  • 1週目
    A=\{4,0,2,2\}となり、食べたりんごの数に4個加算される。

  • 2週目
    A=\{3,0,1,1\}となり、食べたりんごの数に3個加算される。

  • 3週目
    A=\{2,0,0,0\}となり、食べたりんごの数に3個加算される。

  • 4週目
    A=\{1,0,0,0\}となり、食べたりんごの数に1個加算される。

  • 5週目
    A=\{0,0,0,0\}となり、食べたりんごの数に1個加算される。

加算するりんごの数の変化点に注目すると、

  • 最初のAの最小値であるA_2=10となるまで、空でないかごの個数分4個を加算する
  • A_2が空になった時点のAの最小値であるA_3=A_4=2が空となるまで、空でないかごの個数分3個加算する
  • A_3,A_4が空になった時点のAの最小値であるA_1=2が空となるまで、空でないかごの個数分1個加算する

このように、りんごの数が最小となるかごが空になるまでは同じ分だけりんごの数が加算されるので、まとめて考えることができます。
そこで、以下のように操作していくと、食べたりんごの数と現在何周したかを計算していくことができます。

Aから最小値A_iを取得する。ここからA_i周して、合計|A|\times A_i個のりんごを食べる。その後、Ai番目の要素を削除し、全ての要素からA_iを引く。

最小値の取得や値の削除は優先度付きキューにより実現できます。
あとは、A_iを引く操作に時間がかかるので、今までに何周したのかというのをRに記録します。すると、以下のようにできます。

Aから最小値A_iを取得する。A_i-R周して、|A|\times (A_i-R)個のりんごを食べたことにする。その後、R\leftarrow R+A_iと更新し、Ai番目の要素を削除する。

さて、この操作を繰り返すと、どこかの時点で「次の操作をすると食べたりんごの数がK以上となる」状態になります。
この状態からあと何周必要かを計算します。残りの周回数は、この時点でのAの最小値以下であることが保証されます。

この時点からの残りの周回数をmとおくと、以下の不等式が成り立てばよいです。

|A|\times m \leq K

よって、

m=\lfloor \frac{K}{|A|}\rfloor

です。
よって、先ほどの操作と今回の操作で得られた値を合計すれば、qが求まります。

あとは、q周した状態(元のAのすべての要素からqを引いた状態)からりんごの数がKとなるまでシミュレーションすればよいです。
長くなりましたが、要点をまとめるとこのような流れになります。

  1. Aの最小値が0になるまで周回するという操作を繰り返す
  2. 上記の操作でりんごの食べた数がK以上となる直前で操作を終了し、残り何周必要かを計算する
  3. 全体で何周すれば良いかがわかったので、その分だけ周回した後から、残りをシミュレーションする

Submission #35138460 - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270)

AtCoder Beginner Contest 267 F - Exactly K Steps

最遠点を求めた後にLink-Cut TreeでK回移動する解法で解いてみました。

ここでは、Link-Cut Treeの詳細な説明は割愛し、必要な部分だけを記載します。

詳細は以下のサイトを見るのが良いと思います。

Link-Cut Treeの実装メモ - 日々drdrする人のメモ

Link-Cut 木 - ei1333の日記

Link-Cut木では、以下のような操作ができます。

  • evert(v):頂点vを根にする
  • expose(v):根から頂点vまでのパスをHeavy-edgeで繋ぐ(パス上の頂点から出るその他の辺は全てLight-edgeになる)

頂点sを根とし、頂点tまでのパスをHeavy-edgeで繋ぐと、s-t間に含まれる全ての頂点が同一の平衡二分探索木によって管理されます。

この平衡二分探索木の頂点を通りがけ(in-order)順に並べるとs-t間のパス順になるようになっています。

続いて、平衡二分探索木を通りがけ順に並べた時のk番目の頂点を高速に得る方法を考えます。

まず、平衡二分探索木に部分木のサイズを持たせます。すると、通りがけ順でX番目となる頂点が、今いる頂点vの左部分木か、右部分木か、v自身かというのが、以下の場合分けで判定できます。 なお、1-indexedで並べるものとします。

S=頂点vの左部分木のサイズ+1
とします。+1は頂点vの分です。

  • X = Sの場合
    通りがけ順では、左部分木を全て並べた後、頂点vを並べます。
    左部分木のX-1の頂点を並べた後に、X番目としてvを並べるので、このケースではvを返せば良いです。

  • X \lt Sの場合
    左部分木にX番目が存在するので、vの左の子のX番目を調べます。

  • X \gt Sの場合
    右部分木にX番目が存在するので、vの右の子について、S個の頂点を除いたX-S番目を調べます。

このように根から順に二分探索のような感じで調べていくことでX番目の頂点を得ることが可能です。

計算量は、平衡二分探索木の高さ分の探索をするので、平衡二分探索木であることを考えると、ならしlog時間くらいになると思われます。

以上から、元の問題を以下のように解くことができます。

  1. 頂点iからの最遠点V_iを、すべての頂点について求める
  2. 各クエリで与えられるの頂点U_iをLink-Cut Treeの根とし、最遠点V_{U_i}を根と繋ぐ
  3. U_iからV_{U_i}までのパス上におけるK_i番目の頂点をLink-Cut Treeの平衡二分探索木から求める

計算量を考えます。
最遠点は、全方位木DPにより求めたので、O(N)です。
Link-Cut Treeで行う各処理は、O(logN)で処理できると思うので、O(QlogN)です(おそらく)。
よって、全体でO(N+QlogN)だと思います。

提出コード:Submission #34979495 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)

Link-Cut Treeにはモノイドを乗せるようにしてあるので、構造体等が定義されていますが、この問題を解くにあたっては不要です。

AtCoder Beginner Contest 269 参加記録

コンテストページ:

UNICORN Programming Contest 2022(AtCoder Beginner Contest 269) - AtCoder

コンテスト中AC:A〜E
Fがあと一歩だったので、書いておきます。

F - Numbered Checker

長方形領域の列は以下の2つに大別されます。 ?には整数が入ります。

  • 0 ? 0 ? 0 ? ...
  • ? 0 ? 0 ? 0 ...

ここから0を抜いたものを考えます。

(1) 0 ? 0 ? 0 ?...の場合
行数をs、項数をp、1行目の最初の値をaとすると、以下のs個の数列の和を求める問題となります。

A_1 = \{a,\ a+2,\ a+4,...,\ a+2(p-1)\}
A_2 = \{a+2M,\ a+2+2M,\ a+4+2M,\ ...,\ a+2(p-1)+2M\}
... A_s = \{a+2(s-1)M,\ a+2+2(s-1)M,\ a+4+2(s-1)M,\ ...,\ a+2(p-1)+2(s-1)M\}

それぞれ和S_{A_i}以下のように考えます。

S_{A_1} = ap + 2\{1+2+...+(p-1)\} = ap+2\frac{p(p-1)}{2} = ap + p(p-1)
S_{A_2} = ap + 2\{1+2+...+(p-1)\}+2pM=ap + p(p-1) + 2pM
 ...
S_{A_s} = ap + 2\{1+2+...+(p-1)\}+2(s-1)pM=ap + p(p-1) + 2(s-1)pM

というわけで、ap + p(p-1)は、s個含まれ、\{ap + p(p-1)\}sです。
これを分離すると、残りの求めるべき和は、

2pM + 4pM + ... + 2p(s-1)M = 2pM\{1+2+...+(s-1)\} = 2pM\frac{s(s-1)}{2} = s(s-1)pM

となるので、長方形領域の求めるべき和S_aは、

S_a = \{ap + p(p-1)\}s + s(s-1)pM

です。

(2) ? 0 ? 0 ? 0 ...の場合
先ほどと全く同じです。
行数をt、項数をq、1行目の最初の値をbとすると、求めるべき和S_bは、

S_b = \{bq + q(q-1)\}t + t(t-1)qM

となります。

以上を求めれば、当初のクエリで求めるべき答えはS_a + S_bです。 後は、各クエリの長方形領域におけるs,t,p,q,a,bさえ求めれば答えを得ることができます。

まず、p,qA,Cに依らず、以下の通り計算できます。

  • p = \lfloor \frac{(D-C+1)}{2} \rfloor
  • q = \lceil \frac{(D-C+1)}{2} \rceil

その他は場合分けが必要です。

(1) (A+C) \ mod\ 2 = 1の場合

0 ? 0 ? 0 ? ...
? 0 ? 0 ? 0 ...
...

というケースになります。

よって、

  • s = \lceil \frac{(B-A+1)}{2} \rceil
  • t = \lfloor \frac{(B-A+1)}{2} \rfloor
  • a = (A-1)\times M + C + 1
  • b = (A-1)\times M + C + M

(2) (A+C) \ mod\ 2 = 0の場合

? 0 ? 0 ? 0 ...
0 ? 0 ? 0 ? ...
...

というケースになります。

よって、

  • s = \lfloor \frac{(B-A+1)}{2} \rfloor
  • t = \lceil \frac{(B-A+1)}{2} \rceil
  • a = (A-1)\times M + C +M+ 1
  • b = (A-1)\times M + C

以上で各クエリをO(1)で解けます。

ちなみにコンテスト中は以下のミスで解けませんでした。
- 1+2+...+m = \frac{m(m-1)}{2}にしてしまっていた。
- a,bを逆にしていた。
- mod\ 998244353をとり忘れた。

Submission #34954104 - UNICORN Programming Contest 2022(AtCoder Beginner Contest 269)

AtcCoder Beginner Contest 268 参加記録

コンテストページ:UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268) - AtCoder

コンテスト中AC:A〜D

D - Unique Username

文字列の並べ替え方がN!通りです。

アンダーバーの入れ方ですが、まず、アンダーバーを入れる残り個数Rは、文字数の合計をsumとすると、R=16-(sum+N-1)です。

アンダーバーの入れ方は、区別のないR個のボールと区別のないN-2個の仕切りを並べる方法の総数に一致するので、_{R+N-2}C_{R}通りです。

以上から、ありうるユーザー名の個数は、N!\times _{R+N-2}C_{R}通りですが、いずれか一方が大きいともう一方は小さくなるので、少なそうだと予測できます。

厳密に全て確かめたい場合は、S_iの文字数が全て1の場合に最も個数が多くなるはずなので、N=1,...,8まで計算してみればよいかなと思います(コンテスト中はそこまでしませんでした)。

というわけで、全探索して問題なさそうです。(書いていて気づきましたが、個数が少ないとか関係なく、鳩の巣原理からO(M)になりそうです。)

あとは、ユーザー名の生成方法です。
実装としては、順列全探索で文字列の並べ替え方を全部試し、その全てについてDFSでアンダーバーを付けていきました。詳細は実装を見てもらった方が早そうです。
Submission #34748520 - UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268)

AtCoder Beginner Contest 267 参加記録

コンテストページ:https://atcoder.jp/contests/abc267

コンテスト中AC: A〜D
コンテスト中にもう少しのところでACできなかったEについてコンテスト後に解けたので書きます。

E - Erasing Verticles 2

とり得る値の最小値を求める問題では、二分探索できないか疑います。今回の問題の場合、

  • コストをX以下にすることは可能か?

という問題を考えると、あるコスト以下は全て可能で、それより大きいコストは全て不可能という境界が存在することが言えます。

後は、コストXを定めたときに、この問題について高速に判定できればよいです。

判定方法について考えます。

コストX以下の頂点があればとにかく消した方がよいです。なぜなら、そうすることでその頂点と隣接する頂点のコストを減らすことができるからです。

というわけで、以下の貪欲法が考えられます。

未削除の頂点のうち、コストX以下の頂点を1つ選び、削除する。削除した頂点と隣接する頂点のコストを減らす。これを削除可能な頂点が無くなるまで繰り返す。

この貪欲法について、例えば、削除対象を毎回全頂点から選び出しているだけでもO(N^2)になってしまいます。

ある頂点を削除した時、次に削除対象となる可能性があるのは、その頂点と隣接する頂点だけです。
従って、削除可能な頂点集合Sを管理することで、以下のように処理できます。

頂点を1つも削除していない初期状態で、削除コストがX以下の頂点をSに追加する。その後、Sが空になるまで以下を繰り返す。

Sから頂点を1つ選び、削除する。
削除した頂点に隣接する頂点のコストを減らし、X以下ならSに追加する。

Sが空になった時点で、全ての頂点が削除されていれば、達成可能です。そうでないなら、不可能です。

この方法は、すべての頂点のN回の削除処理において、頂点を削除した時にその頂点から出る辺を1回ずつ辿るので、辺を辿るのは合計2M回となります。
よって、O(N+M)です(多分)。

これにより、高速に判定できることがわかりました。

従って、初期状態でのコストの最大値をC_{max}とすれば、元の問題をO((N+M)log{C_{max}})で解くことができます。

コストが最大となるのは、おそらく全ての頂点に10^9が書かれた場合の完全グラフだと思われます。
その場合でも2\times 10^{14}は超えないはずなので、二分探索も十分高速です。

また、コストの下限は0になることに気をつけなければいけません(これに気づけず、コンテスト中にACできませんでした)。

Submission #34576881 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)

AtCoder Biginner Contest 266 記録

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

コンテスト中AC:A,B,D
コンテスト後にC,E,Fを自力(AtCoderの解説を見ず)AC

C - Convex Quadrilateral

下のサイトに判定方法がありました。
第6回 多角形の幾何(前編) | gihyo.jp

多角形上を半時計周りに並ぶ任意の3点A,B,Cが与えられた時、\vec{AB}に対して\vec{BC}が半時計回りの位置にあればよいようです。
Submission #34484140 - AtCoder Beginner Contest 266

#E - Throwing the Die
期待値の問題が最近いくつか出題されていますが、考え方の核となる部分は同じように思います。

f(i)iターン目で得られるスコアの期待値とすると、以下のように計算できます。

  • i = N
    f(i)=\frac{1+2+3+4+5+6}{6}=3.5

  • i\lt N
    f(i)=\frac{max(1,f(i+1))+max(2,f(i+1))+max(3,f(i+1))+max(4,f(i+1))+max(5,f(i+1))+max(6,f(i+1))}{6}

Nターン目は特に説明不要かと思いますので、それより前のターンについて書きます。
状態遷移を伴う期待値は、遷移先の期待値とその発生確率の積の総和をとると、遷移元の期待値を計算できます。
今回の場合、iゲーム目におけるスコアが遷移先であるi+1ターン目の期待値より高い場合に遷移しない選択をすることができます。
従って、出た目と遷移先の期待値のmaxをとればよいです。

というわけで、i=N,N-1,...,1の順にDPやメモ化再帰で問題を解くことができます。
Submission #34436150 - AtCoder Beginner Contest 266

F - Well-defined Path Queries on a Namori

N頂点N-1辺の単純連結グラフは木になります。そこに一辺足されると、閉路をただ1つ含むグラフになります。

閉路の異なる任意の2頂点v_i,v_jを通るパスを考えると、閉路の進行方向によって2種類のパスが存在します。
よって、閉路に属する辺を通るようなパスは問題の条件を達成できません。

以上から、以下の解法を考えました。
1. 与えられたグラフGから閉路に属する辺集合CをDFSで得る
2. GからCに属する辺を除いたグラフG'を得る
3. G'からUnion-Findで連結成分を得る
4. 各クエリを処理する。クエリiについてx_i,y_iが、同一連結成分に属するならYes、そうでなければNoと判定する

これでACすることができました。
Submission #34413373 - AtCoder Beginner Contest 266

AtCoder Begginer Contest 265 E - Warp (兼参加記録)

コンテスト中AC:A〜D
A〜Dで特に書くことがないので、コンテスト後に解いたE問題について書いておきます(解説AC)。

問題
E - Warp

公式解説
Editorial - AtCoder Beginner Contest 265

コンテスト中に考えていた誤りの解法

コンテスト中は、全体の移動方法から、壁に経由する移動方法を引こうと思いました。
まず、全体の移動方法は3^Nです。

次に、壁を経由する移動方法を考えます。 ワープの方法を上から移動1,2,3と呼ぶことにします。

原点から移動1をp回、移動2をq回、移動3をr回行った後に到達する座標を(s,t)とすると、

s = pA+qC+rE
t = pB+qD+rF

という風に計算でき、一意に決定されます。

この座標が壁であるとした時に、(0,0)から前述の移動回数で(s,t)を通るような移動方法が何通りあるか数え上げてみます。

まず、(0,0)から(s,t)に移動する方法の総数ですが、それぞれp個、q個、r個ある3種類のボールを1列に並べる方法の総数に等しいので、

\frac{(p+q+r)!}{p!q!r!}

通りです。
(s,t)に到着後の残りは、どのような移動方法をとってもよいので、3^{N-p-q-r}通りです。

従って、求めたい移動方法の総数は、

\frac{(p+q+r)!}{p!q!r!}\times 3^{N-p-q-r}

です。
あとは、p,q,rを全探索して、上記を計算し、全体から引いていけば良い、と思いましたが、これは 誤りです。

なぜなら、(s,t)の他にも壁を通過している可能性があるため、重複して数え上げている可能性があるからです。

正しい解法

公式解説を参考に、座標ではなく各移動方法の移動回数を情報として持った、メモ化再帰で解きました。

f(p,q,r):移動1をp回、移動2をq回、移動3をr回行った場合の移動方法の総数

とおきます。

f(p,q,r) = f(p-1,q,r)+f(p,q-1,r)+f(p,q,r-1)

という式でf(p,q,r)を計算できるので、f(N,N,N)から開始してメモ化再帰することで、O(N^3)で全て計算できます。

p+q+r=Nとなるようなf(p,q,r)を全て足せばそれが答えとなります。

操作回数が同じなら辿り着く座標が同じであることから状態がO(N^3)と少ないことがポイントでした。

https://atcoder.jp/contests/abc265/submissions/34257627