トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが855でした。
D問題があと10分くらいあればACできた...コンテスト後にデバッグして提出したらACだったのが悲しい...

A - On and Off

日付を跨る場合がちょっと面倒。図でも書いて場合分けすればわかりやすいけど、毎日電気をつけて消してをしているのを見落として1WAだった。日付を跨っているかどうかに注意して問題文の通りに実装すれば良い。

B - Takahashi's Secret

$i$ が秘密を知っているかどうかを確認して、知っていなければ次は $A _ {i}$ が知っているかどうかを確認して・・・をひたすら繰り返す。秘密を知っていれば処理を打ち切る。人数は $10 ^ {5}$ 程度で二重ループじゃなければ時間に間に合うので、処理を打ち切ったあとN人の内何人が秘密を知っているのかを数えて出力する。

4日目の得点が自分だけ満点。他の全員は0点だとした場合に自分が何位になるのかを数えて、K位以内かどうかを判断すれば良い。
入力を受け取りつつ各生徒の3日目終了時点の合計得点を計算する。それと別に合計得点のリストを作ってソートしておく。生徒の合計点＋300点したときの値がリストのどの位置に入ることになるのかを探して何位になるのかを計算する。リストのどの位置に入るのかを線形探索するとN人 $\times$ リストの長さで $O(N ^ {2})$ になってTLEになるのでこの部分を高速化する必要がある。ソート済みの配列で閾値を探すことになるので二分探索が使えるので、二分探索を使って高速化する。

D - Linear Probing

問題文がややこしくて内容を理解するのに結構時間がかかった。
要するに $h　mod　N$ 番目の要素から順番に $A _ {i}$ が-1になる要素を探して、その要素をxに置き換える問題。※mod Nを取っているので0～ $2 ^{20}-1$ を循環するのが注意する点。
h MOD Nをもとに高速に $A _ {i}$ =-1となるiが求めたい。
はじめはsetを使って、処理した要素番号の集合から次はどこを処理すれば良いのか求めようとしたけど、上手くできそうになかったので考え直してUnionFindが使えそうだったので実装した。
提出してみるとWAが1ケースあってコーナーケースで躓いていそうだったので見直してたけどACできなかった。
コンテスト後にコードを見直して提出してみたらACしたのでちょっともったいない。