デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）に参加しました。
結果
A,B,C,Dの4問正解で、パフォーマンスが719でした。 D問題がいつもに比べてかなり簡単な気がした。全探索でACできるD問題はかなり珍しい気がする。
A - Horizon
指定された計算式で計算して答えを出力すれば良い。平方根がちゃんと計算できるかどうかな問題。
出力する答えの桁数も気をつけないといけないのかも。
B - Integer Division
簡単に答えを計算できる関数があった気がするけど思い出せなかったので地道に処理していった。 基本的に10で割ったものを小数点以下を切り捨てる。あとはXがマイナスなら1引くけど、Xが10で割り切れるときはそのままにする。
C - Knight Fork
賢い方法が思いつかなかったので割と力技で答えた。
距離が程度なので各x,yの前後
のうち整数の値を列挙して、格子状の点としてありえるx,y
を全通り確認した。
あとは2点間の距離が
より大きい場合は条件を満たす点がいないのでNoと答えて処理を終了させる。
D - Prime Sum Game
色々考えてみたけどA,B,C,Dは100以下でとても小さいので、高橋くんが選ぶ整数と青木くんが選ぶ整数全通りを確認すればいい。
毎回整数の和が素数かどうか判定するのは手間なので最初にエラトステネスの篩等で200以下の素数を列挙しておいて、素数の判定をでできるようにしておく。
E - Subtree K-th Max
どうやって解こうかなとずっと考えていた。Q個のクエリに答えないといけないけどQが最大でなので、各クエリは
で答えたい気がする。
だとTLEになるし、妥協して
くらいかなあ。
Kは最大でも20程度なので頂点iが決まったときにiを頂点とする部分木に書かれている整数のリストを事前に求めていればそのリストのデータ構造は何でも大丈夫そう。線形探索でも間に合う気がするのでsetでも使えそう。
各頂点の親と子供が管理したいからデータ構造はUnion-Findで木を作れば良さそうな気がする。
あとは、部分木のリストは葉から作ったほうが良さそうなので深さ優先探索で葉の方から見ていけば良さそう。
ここまで考えて実装して言ってたけど時間が足りなかった。コンテストが終わっても実装してみてたけど今度はランタイムエラーになったのでどこかバグってるっぽい。
解いている人数的にdiffは緑の中盤くらいだと思うからACしておきたい問題だった…
