Fまで六完。
コンテスト後のツイート
AtCoder Beginner Contest 254
— titia (@titia_til) June 4, 2022
B 二項係数
C mod Kでそれぞれソート
D 平方数x*xのxの約数から、x*xの約数を調べた
E DFS
F 差分計算、gcdでセグ木
EX binary trieかと思ったが、実はいらないことに気付いた。（あまり自信がないがジャッジ待ち）
G - Elevators
解説放送を見てAC。
確かに一つ一つのステップは典型なので難問ではないと思うが、実装は非常に大変。
特に、
・各ビルについてのエレベーターをマージする
・ダブリングするために、エレベーターをまとめ、使う必要のないエレベーターは削除
をする際、どう処理すべきかで迷った。
両方、低い階の方でソートする（これも、区間スケジューリングが頭にあると、高い階でソートしたくなり間違う）のだが、その後の処理は少し違う。（後者ではマージするわけではないので）
時間をかけられ、また、サンプルが強ければ解けなくてはいけない問題だろうが、今回解き切るのはかなり難易度が高かったのでは。
さらに、ダブリングの実装でミスり、デバッグにかなりの時間を要したのは良くない。ダブリングは大きいステップで行けるかどうか調べて（つまり、1<<i進むこのiを大きい方から見る）更新していくのが良いのですね。なるほど。
Ex - Multiply or Divide by 2
大きい方から貪欲にやれば良いということにはコンテスト中に気付いたが、Bについては、(2x+1)→xの遷移ができないことに気付かず。
惜しかった。
0 件のコメント:
コメントを投稿