デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）参加で久しぶりの更新。

A - Horizon (100点)

素直に \sqrt{H(12800000+H)} を出力すればいいですが、int型でルートの中身を計算するとオーバーフローするのでlong long型や浮動小数型を用いましょう。

B - Integer Division (200点)

C++では整数商X / 10は"0方向への丸め"であるため、X < 0 かつ X が 10 で割り切れないときに 1 だけ大きくなってしまうので、 それを条件分岐させればいいです。
また、Pythonでの整数商X // 10は"切り捨て"即ち"負の無限大への丸め"であるため問題文のものに合致するためこちらで実装すれば条件分岐は必要ありません。

C - Knight Fork (300点)

格子点 (x,\,y) から距離が \sqrt{5} の格子点は (x \pm 2,\,y \pm 1), (x \pm 1,\,y \pm 2) (複号任意) の8点であるため、(x_1,\,y_1), (x_2,\,y_2) のそれぞれからの距離が \sqrt{5} である点の集合の両者に共通する要素があるか、がこの問題の答えとなります。

D - Prime Sum Game (400点)

A \leq x \leq B であり、x + C から x + D までの全ての整数が合成数であるような整数 x が存在するとき、そのような x を高橋君が選べばいいので、このとき高橋君の勝ちとなります。そうでないとき、どんな数を高橋君が選んでも青木君は2数の和を素数にできるので、青木君が勝ちます。
予め B + D までの数についてΕρατοσθένηςの篩をしておくといいでしょう。

E - Subtree K-th Max (500点)

全ての頂点についてその部分木についての全ての整数を調べるのは O(N^2) となり、TLEが発生します。しかし、各頂点について大きい方から最大でも \displaystyle\max_i K_i 個の数さえ分かればよく、K_i \leq 20 であるため、DFSで十分高速に求めることができます。ある頂点について、その子頂点についての数列と自分自身の整数を併せて大きい方から最大 \displaystyle\max_i K_i 個をその頂点での数列となります。
クエリ回答では該当する頂点に対応する数列の K_i 項目を出力すればいいです。

F - Construct Highway (500点)

あともう少しで通せたのに...タイプミスほんまにどうしたら直るんでしょうね...

最終的に木にしたいので \displaystyle \sum_{i=1}^{N} D_i = 2N-2 であることが必要です。また、初期状態で、閉路があってはいけません(Union-FIndで検出)。また、すでに次数が D_iよりも大きな頂点が存在してはいけません。
そののち、グラフの連続成分ごとに次数と D_i の差の合計(ここで \delta とする)を出します。元のグラフでの連結成分を頂点に、次数を対応する \delta とする木を構築することができれば、ここで作った木の各辺に対応して元のグラフに辺を追加していくことでこの問題を解くことができます。

後半の木の構築については \delta が一番大きな連結成分と一番小さい連結成分を結んで併合するということを繰り返します。このとき、併合でできた連結成分の \delta が 0 になったり、連結成分が1個だけになったりしたのが最後以外の瞬間であった場合、木を構築することができず、元の問題も解なしになります。そうでない場合、最後まで操作を行うことで木になります。

G - Builder Takahashi (600点): 未提出

最小カットを勉強したらいけそう

Ex - Dice Product 2 (600点): 未提出

やっぱり確率とか期待値とかは苦手だなぁ...

結果、感想

f:id:Flkanjin:20220221200509p:plain
レートが上がったのはいいのですが、F問題を通せたら青に復帰できたのかなと思うともっと早く組めてたらなぁと...