ganmo::cout

競技プログラミング始めました

エクサウィザーズ 2019

AGC032でのレート初下落のショックから立ち直ってブログ書く気が起きたのでブログ再開です
今回はなんとか青パフォ(1747)出ました

A - Regular Triangle (100点)

問題: A - Regular Triangle
三角形」なのでA=B=Cかどうか判定すればAC。O(1)

拙解 (C++14): Submission #4763656 - ExaWizards 2019

B - Red or Blue (200点)

問題: B - Red or Blue
'R'と'B'の数を数えて'R'のほうが多いかどうか判定すればAC。O(N)

拙解 (C++14): Submission #4765199 - ExaWizards 2019

C - Snuke the Wizard (500点)

問題: C - Snuke the Wizard
いきなり飛んで500点。愚直で出してTLEしたので考察するも半分くらいのケースしか通らずに4WAを重ねた。
二分法も区間が単調じゃないから使えないよな~~~とか思いながら結局は

  • 生き残りのゴーレムはとびとびにならずに区間で表せる
  • ゴーレムは1マスずつしか動けない

ということに気が付いて、落ちうるゴーレムの範囲を左右の端からとることにして、落ちないゴーレムをよけつつ遷移するとAC。O(Q)

拙解 (C++14): Submission #4773744 - ExaWizards 2019

…が、コンテスト後に色々調べるとはるかに簡単な発想で解けることが分かった。左に落ちるやつ右に落ちるやつと別々に考えると二分法が使えて、あるマスのゴーレムがどの座標に行き着くかはO(Q)でわかることから、O(QlogN)でTLEせずにACできるそうだ。

(2019.4.24 追記) 拙解 (C++14, コンテスト終了後, O(QlogN)解): Submission #5110421 - ExaWizards 2019

D以降

Cに時間をかけ過ぎたのと誤読を重ねて解けず…Dは黒板に全部数字が書いてあるものと思い込んでた。
最小を更新したときにしか変わらないよなーって気づいた時点で時間切れ。

まとめ

いつか*1に書いた「400点まではぱぱっと解いて500点をコンスタントに解く」が最近できている!