全完で四位と良い出来だったと思う。
Fみたいな問題がABCで出ることはあるんでしょうか。
コンテストへのリンク
CROSS†SOUL
「逆順が最適」だけど、全探索でも解けるように作られている教育的問題。
解説スライドにある通り、この最適性の証明は競プロにおいて重要ですね。
DEATH†ZIGOQ ～怒りの高速爆走野郎～
最小全域木の作り方、もしくは、ダイクストラ法といったあたりを知っていれば解けると思う。
何でもダガー打ちゃいいってもんじゃねぇぞ†2020
「部分文字列を走査するDP」を使う問題。これ系の問題は何度も解いているはずなのに、出題されると結構時間がかかってしまう……。
"✝"
十字架の区間はの管理は、縦パートと横パートで分けてimos法を使えばできそう。（解説スライドでは正方形に対して操作しているけど、縦横で分けた方が考えやすくないですか？）
あとは、駒の種類だけど、どうするか→駒をHash化すればいけそう。
計算量の見積もりはしていないけれど、Pythonだと計算時間が厳しそうなので、雑に二次関数でHashを作ったらWAが出て困った。最終的にはACできましたが、13回も提出した。
こういう問題はAtCoderよりもCodeforcesで出やすいと思うのですが、CodeforcesだときちんとHashをrandom化しないとHackされやすい。だけど、乱択系の問題は制限時間が短く設定されていることが多いためPython/PyPyだと辛くなってしまいやすい……。
Hackがなければどうにかなることが多いのですが。
0 件のコメント:
コメントを投稿