2022-09-18

AtCoder Beginner Contest 269 参加記録

ABC 等差数列

コンテストページ：

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,q$ は $A,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)

2022-09-16

AtcCoder Beginner Contest 268 参加記録

ABC 順列全探索少ない状態数 DFS

コンテストページ: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)

2022-09-15

AtCoder Beginner Contest 267 参加記録

ABC グラフ

コンテストページ: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)

2022-09-01

AtCoder Biginner Contest 266 記録

ABC Union-FInd 計算幾何凸包期待値DP メモ化再帰 DP

コンテストページ
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

2022-08-23

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

ABC 少ない状態数メモ化再帰

コンテスト中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

2022-08-09

AtCoder Biginner Contest 263 参加記録

ABC DP 期待値DP

コンテストページ:LINE Verda Programming Contest（AtCoder Beginner Contest 263） - AtCoder

コンテスト中AC: A〜E

E - Sugoroku 3

E - Sugoroku 3

期待値DPが使えます。
サイコロを振ることを操作と呼ぶことにします。

マス $i$ からマス $N$ までにかかる操作回数の期待値を $E_i$ とします。

マス $i$ からは、マス $i,\ i+1,\ \cdots ,\ i+A_i$ に行くことができます。
$m = A_i+1$ とおけば、それぞれのマスには $\frac{1}{m}$ の確率で移動します。

また、マス $j$ に辿りつくと、マス $j$ からは(平均して) $E_j$ 回の操作でマス $N$ に行けます。 $i$ から $j$ に行くのに操作を1回行うので、マス $i$ からマス $j$ を経由してマス $N$ に辿りつくには $E_j + 1$ 回の操作が必要になります。

以上から、以下の式が成り立ちます。

$E_i = \frac{1}{m}(E_i + 1) + \frac{1}{m}(E_{i+1} + 1) \cdots + \frac{1}{m}(E_{i+A_i} + 1)$

さて、この式には右辺・左辺の両方に $E_i$ があるので、左辺に移行します。

$\frac{m-1}{m}E_i = \frac{1}{m} + \frac{1}{m}(E_{i+1} + 1) \cdots + \frac{1}{m}(E_{i+A_i} + 1)$

$E_i = \frac{m}{m-1}\{\frac{1}{m} + \frac{1}{m}(E_{i+1} + 1)+ \cdots + \frac{1}{m}(E_{i+A_i} + 1)\}$

この式より、 $E_{i+1}, \cdots ,\ E_{i+A_i}$ が求まっていると $E_i$ が求められます。
同じマスに戻るような場合、一見無限回の試行が必要なように思えますが、このように式変形すると問題なく求められる場合があります。

次に、期待値を求めていきますが、マスの移動先が少なければメモ化再帰等で愚直に求めていくことができます。しかし、今回は移動先が多いため $O(N^2)$ となってしまうので、もう少し工夫する必要があります。

前述の式を更に整理します。

$E_i$
$= \frac{m}{m-1}\{\frac{1}{m} + \frac{1}{m}(E_{i+1} + 1)+ \cdots + \frac{1}{m}(E_{i+A_i} + 1)\}$

$= \frac{1}{m-1}\{1 + (E_{i+1} + 1)+ \cdots + (E_{i+A_i} + 1)\}$

$= \frac{1 + E_{i+1} + 1+ \cdots + E_{i+A_i} + 1}{m-1}$

$= \frac{E_{i+1} + \cdots + E_{i+A_i} + m}{m-1}$

したがって、

$E_i = \frac{E_{i+1} + \cdots + E_{i+A_i} + m}{m-1}$

となります。 $E_{i+1} + \cdots + E_{i+A_i}$ の部分を高速に求められればよく、連続した区間の和なのでFenwick Treeにより $O(logN)$ で求められます。

以上より、 $E_N = 0$ を初期値として、 $i=N-1,\ \cdots ,\ 2,\ 1$ の順に $E_i$ を求めていくことで、
$O(NlogN)$ でこの問題を解くことができます。

(累積和を用いれば計算量が落ちるかもしれません)

Submission #33834218 - LINE Verda Programming Contest（AtCoder Beginner Contest 263）

2022-08-02

AtCoder Biginner Contest 262 参加記録

ABC 部分和DP DP

コンテストへのリンク:■
コンテスト中AC:A〜D

D - I Hate Non-integer Number

数列の部分和に関する問題なので、部分和DPを考えます。

$dp[i][j]:=$ 数列 $A$ の $i$ 項目までの部分和であって、和が $j$ となるものの個数

今回は、何個選んだかも必要なので、情報を足します。

$dp[i][j][k]:=$ 数列 $A$ の $i$ 項目までの部分和であって、部分和を構成する要素の数が $j$ 個、その和が $k$ であるものの個数

今回、数列の要素数は $N\leq 100$ と少ないですが、 $1\leq a_i \leq 10^9$ であり、和のとりうる範囲が非常に大きく、上記のDPは使えません。

ここで、選ぶ要素数を固定し、 $X$ 個とします。
$X$ 個の要素からなる部分和 $S$ の平均が整数となるためには、 $S$ が $X$ の倍数である必要があります。すなわち、以下の条件を満たせばよいです。
$S\ mod\ X = 0$

つまり、部分和の $mod\ X$ だけわかれば、倍数となるかを判定できます。
そこで、以下のDPが考えられます。

$dp[i][j][k]:=$ 数列 $A$ の $i$ 項目までの部分和であって、部分和を構成する要素の数が $j$ 個であり、その和を $S$ とした時に $S\ mod\ X = k$ であるものの個数

このようにすれば、 $k$ のとりうる範囲も $0\leq k \leq N-1$ となり、 $N$ 個に限定されます。

計算量は、DPテーブルを埋めるために $O(N^3)$ かかり、 $X=1,2,\cdots ,N$ のそれぞれについて計算する必要があるので、 $O(N^4)$ だと思います。
実装はコンテスト後に見直ししたもの。
Submission #33697694 - AtCoder Beginner Contest 262

geam1113’s diary

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