Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ABC142反省会

初の5完!!!うおおおおおおおおおおおお!!!!!!

ずっと惜しい時が続いていたので苦しかった。

といっても今回のEはどちらかというと簡単だったと思う。

最初にパラパラとEまで見て、解けると思ったのでEから解き始めた。20分くらいでAC。最近教育DPをやりまくってるのもあって楽に見えた。最初はグラフの問題かと疑っていたが、N=12からのビットDPを信じることにした。

Dも行ける感じだとは思っていたが、解法が完全に見えていたわけではなく、やってみたらREとTLEが出た。(REはキャストエラーだと思われる)想定解法は最大公約数を出してエラトステネスの篩をやるというものだろうけど、自分はエラトステネスの篩をしてからその結果を使って素数を見つけるという方針を立てていて、これは数学的には正しいけど、実際には計算量が高すぎる。

はぁ・・・また4完か。とため息をついて、焦っても意味ないのでとりあえずAからCまで解くことにして、これらはいつもにも増して簡単なので、楽にAC。

この前のABCで、「時間があったので別の解法を実装してみればよかった」と反省していたのを思い出して、同じような方針だが別の実装をやってみたが、やっぱりだめ。結局、2WAのあとふつうにエラトステネスをやることにして、AC。もったいないことをした。

Fは時間があったのでやってみようかと思った。ループを探すという話だと理解した。その上で、NMの積が6乗程度なので、仮にグラフを強連結分解してその中で連結関係を精査すると行けるのではと予想したが、絵を描いてみるとだめなケースを見つけてしまい、悩んだ挙げ句投了。全完はお預けとなった。

引き続きDPをやっていく。教育DPが終わったら典型DPも網羅しようと思います。そしたらまた500埋めに戻ろうかな。CFやLeetも典型問題を学ぶには良いので、これも続けていく。

f:id:akiradeveloper529:20190928204654j:plain

これはABC前の栄養補給。これとYoutubeの視聴者から送ってもらったアイスコーヒー。