毎日格上の問題を倒すやつの53日目です。*1
コンテストリンク
https://kenkoooo.com/atcoder/#/contest/show/172ff02f-aef7-48c8-8f65-0de9b8643797?activeTab=Standings
結果
道案内...45/100(ooo-)
ドラゴン2...100/100(ooo)
防犯ゲート...12/100(oo--)
合計...157/300
割と良いのでは?
解法
J - 道案内
~小課題2
とりあえず距離を書き込めば1は解けます。
があまりにも意味深なので、これを眺めてみましょう。
すると、 で割ったあまりをとっても判別できることに気づきます。
小課題3
次数が2でないのもめちゃくちゃ意味深です。
これはつまり、「1つだけ違う数字の時、それが一意に定まる」ということです。
なので、うまく進むべき方向だけ数字が違うようにしたいです。
これは、家までの距離を で割ったあまりが なら 、でなければ を書き込めば良いです。
L - ドラゴン 2 (Dragon 2)
え~…
誠に申し訳ございません。
完全に愚直な 解法*2、QCFium法で高速化したら通りました(笑)
なので特にいうことはないです、はい。練習にはよくなかったとだけ。
I - 防犯ゲート (Security Gate)
~小課題2
何もわからないのでかっこを全探索です。
それぞれのパターンに対して、 の耳DPをします。定数倍高速化はしましたが3は通らず。bitsetが想定解らしいです。
提出コード
道案内
ドラゴン2
防犯ゲート
感想
道案内の解説が天才で萎えた