AtCoder ABC228
ABC228参加しました。
今回はC,Dだけ解説します。
C - Final Day
解説 - AtCoder Beginner Contest 228
提出 #27385698 - トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)
4日目、ある人(Aさんとします)だけが満点(300点)を取り、Aさん以外の人が0点を取ると、Aさんの点の上がり幅は最大となります。この状態でAさんの順位が何位になるかを計算しました。
二分探索で、Aさんが300点を取った状態の合計得点Sが、配列のどの位置に来るのかを調べました。
ただ、公式解答通り、 K番目の順位の人の点を調べておいて(上の仮定どおりやれば、Aさん以外の順位は不動のはずです)、その点よりSが上か下かを判断するだけでも十分です。二分探索なんていらなかった。
D - Linear Probing
解説 - AtCoder Beginner Contest 228
提出 #27418742 - トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)
提出プログラムに詳しく書きました。公式解説の「解法2」に準じています。
Aに伴って変わる配列Pを考えP=(0,1,2,3..., N-1)とします。
また、A[m] = -1となる場所mを「Aの空き枠位置」と表現します。
P[h] には、A[h%N]==-1となるh%Nの値が入っています。
問題のcase1の手順2の部分で、A[h%N]==-1となるhを探すためにhをインクリメントしてますが、そのようなhがなかなか見当たらない場合に計算時間を消費します。
よって、A[h%N]==-1となるh%Nの値を求めるために、場所hから辿れる次のAの空き枠位置を配列Pで覚えておきます。
配列Pからh番目の次の空き場所を探す場合に使うメソッドがp(h)です。
また、A[h%N]が変化したら、空き枠も1つ消費されるので、次の空き枠位置を(h+1)%Nから探し手求めておきます。
pの内部で経路圧縮としてp()を再帰的に呼ぶのがミソでした。
感想
Dは空き枠管理という考え方は思いついたが、union-find的な考え方までは至らなかった。
