ABC292 (2023/03/04)
〇A問題
Yuto.icon 最初，upperをlowerとして提出してしまい，1WA．あほすぎる
TK.icons.upper()
CarpDay.iconupper忘れていたけど，エディタのお助け機能のおかげで候補から選択できました(^^)
おたふく.icon Yuto.iconTK.icon同様
まーす.icon前回の復習（調べたなんていえない）
〇B問題
Yuto.icon yellowとredの個数をプレイヤーごとにdictで数える
TK.icon各プレーヤーの違反点数を辞書で保存。イエローカードは1点レッドカードは2点。2点超えてたらアウト
CarpDay.icon黄色なら1，赤なら2増やして，2点以上ならアウト．私はリストで得点管理
おたふく.icon 黄色なら+1, 赤色なら+2とするとWA。おとなしく赤色なら = 2としておけば良かった。
まーす.icon解法は↑と同じ。私もリストで管理。題意のQとNを間違えてRE。Damn!
〇C問題
Yuto.icon パッと見て数学だったので一旦飛ばした．DのWAが取れそうになかったので戻ってきた．i = range(1,n)として，N = i + (N-i)の各i, (N-i)を作る個数を数えたらいけるんじゃない？と思ってやってみた．iを作る個数はiを素因数分解して約数の個数数えてそれを二つに分ける場合の数にすれば良いかなと思ったけど，「二つに分ける場合の数」を求める部分が上手く実装できなかった．前計算O(N)くらい，各iについて約数の個数求めるのにO(logN)くらいだから計算量的には問題無いはず
Yuto.icon 解説見た．自分は公式解説の下の方に書いてるO(nlogn)解法をやろうとしていたっぽい．
TK.iconぱっと見、一次不定方程式みたいに見えた。ABの組、CDの組の個数を半分まで考えたらその組み合わせだから行けると思ったが自分の実装が悪く当たり前のようにTLE。AB、CDの組み合わせが、仮定した数の約数の個数分だということに気づきこれで行けるかと思ったが、書いているうちに計算量ヤバくねとなった。
CarpDay.iconC問題にしては重いなぁ．．問題タイトルから半分全列挙かと思ったが．．計算量が心配なコードだったためドキドキしたけど，何とかAC
おたふく.icon 半分全列挙かなと思いつつも、計算時間を省略する方法が思いつかずDへ。時間内に考えていた方法のまま計算時間の省略などを考えずに実装すると時間ギリギリながらAC。
まーす.iconAB+DC=N→X+Y=Nに置き換え、Xi（i=1,2,...,N-1）における（A,B）を探し、XiとXN-iの積の総和を出力したが、無事TLE。なんでや...。 P.S.解説確認後、無事AC。やったぜ。
〇D問題
Yuto.icon ぱっと見てUnionFindするだけやんと思い，問題も理解せずに提出してWA．落ち着いて問題文を理解する．今度こそできた！と思ったらまたWA．．．UFで代表根を取得して，連結成分ごとに頂点と辺を数えるだけのはずが解けなかった．．なぜ．．
yuto.icon コンテスト後、CarpDay.iconさんに指摘していただき、uf.find()で得られる代表根がuf.union()によって変化することに気付く。unionしながらfindせず、先に全部unionしてからfindするように変更して無事にAC
https://scrapbox.io/files/64045be24e7431001bfcb905.jpg
CarpDay.iconUnionFindで連結成分作って，各成分ごとの枝数カウント
TK.iconCの方針が決まる前に除いた程度、連結成分ごとに辺の本数を持っておけばよいからUnionFindだろうなと思いつつもCに専念。後で解きます。
おたふく.icon 時間内に解けたはずなのに...。コーナーケースに気を付けよう...。
まーす.icon個人的には、Cより簡単に感じた。UnionFindでその連結成分に含まれる頂点を集合としてまとめ、各(頂点)成分の枝数を数え上げ、それがその頂点成分のサイズ(規模、集合の大きさ、母数といったら分かりやすい？)と一致するかどうか
〇E問題
CarpDay.iconサンプルで熟考．問題サイズを考えて，素直に実装すればいいんじゃね？でも実装しんどそう，と思いF問題へ．戻った時には実装間に合わず．．コンテスト終了後に時間かけて実装するもTLEでしたので，スキップして正解でした．考察大切．
Yuto.icon 最初見た時は最小全域木かな？と思ったけど，図を書いてみるとなんか違うっぽい．難しそうなのでDに戻った．
Yuto.icon 解説見た．実は、最終的なグラフの状態において存在する頂点 x を始点とする有向辺は、初期状態において頂点 x から到達可能な頂点(x を除く)を終点とするもの及びそれに限ります。 [←これをコンテスト中に気付くのはなかなか厳しい．．．
〇F問題
CarpDay.icon解答が実数になるので，あの方法かな？さらにあの方法を組合せて，と頑張って実装してサンプルAC！喜んで投稿したらWA.でも結構ACなのでコーナーケース考えて，対応したらAC！初F問題ACでした！！
Yuto.icon これ以降見てない
おたふく.icon 完全に数学の問題だった。少し解説をカンニングしましたが、概ね自分で解けて嬉しいです。
まーす.icon数学は好きだが、幾何は苦手なんすよ...。まあ、完全に自力で出来たので嬉しいのは間違いない！
REとWAはifの条件を間違えただけ。 以下、解法。 ①中の正三角形の１つの辺が外側の四角形の１辺のいずれかと平行かどうか(ここは簡単) ②①が真あるいは偽のときの三角形の1辺の長さℓを求める。(偽のときの計算が少し煩雑だが、高校生でも解ける。)
↓は詳細(ネタバレ注意)
①が真⇒ℓ＝2*A/(3)^0.5
①が偽⇒ℓ^2＝(2*B - (3^0.5)*A)^2+A^2 かつ ℓ＞０
→2変数の連立方程式を解くとき、普通両方の変数を求めるが、今回は片方だけでよかった。(題意でなにを求められているかを考えることは重要！)