geam1113’s diary

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

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