Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)

5完7WA1TLE1RE

通した順番は A -> B -> E -> D -> C

なんだこれ...

各問題

A - Counting Passes

L点以上の人を数えてください。

B - Minimize Abs 1

A が L と R の間にある場合は、X = A とすれば |X - A| = 0 となりいかなる Y でもこれを下回ることがないので、A が答えです。

A が L より小さい場合 |X - A| は X = L の時最小となるので L が答え、A が R より大きい場合は R が答えです。

C - Minimize Abs 2

x は 0 から sqrt(d) + 1 の範囲で全探索しましょう。x * x - D が非負になったら、y は 0 が最適ですし、以後 x * x - D は大きくなる一方なのでそこで打ち切れます。

x * x - D が負の数の場合 sqrt(-(x * x - D)) の切り捨てか切り上げが最適な y となるのでそれを答えます。

long long で計算していたはずが一か所 int になっていることに気づかず トータル7ペナ を叩くという大惨事...。

D - Counting Ls

言い換えると、o で(特定条件の)直角三角形がいくつ作れるか、という問題です。

行と列に o がいくつあるかを最初に数えておきます。

あとは、各 o について同じ行と同じ列にいくつ o があるかを調べて、それをかければその o について、そこが直角の三角形がいくつ作れるかが求まるので、すべての o についてそれを求めて足せばそれが答えです。

E - Mex and Update

mex を求める用のセグ木を持っているのでそれをペタリすれば終わりです。(おい

なおたまにしか使わないので、まいどまいど使い方を思い出すところから始まるのが玉にきず。

まとめ

C がどう考えてもあってるのにはまり続けたのがつらすぎた...。なんとか通し切って事なきを得ましたが。(得てませんが