2021/3/14に開催されたAtCoder Regular Contest 114に参加しました。
前回のARCはAのみの1完という残念な結果だったため、今回はなんとかレートを落とさないようにという気持ちで臨みました。
参加します。レートを落とさないように頑張る。ただそれだけです。
— devgenjin77 (@devgenjin77) 2021年3月14日
AtCoder Regular Contest 114 - AtCoder https://t.co/AfyB8ubSs6
今回の結果
と、意気込んではみたものの、結果はBのみの1完という残念な結果に。。
が、しかし！なんとBのみの1完でも緑中盤程度のパフォーマンスがでており、なんとHighestを少し更新することができました！
1完で死亡かと思いきや、なんとか緑パフォでレート上げを達成しました。次も頑張ります！
— devgenjin77 (@devgenjin77) 2021年3月14日
devgenjin77さんのAtCoder Regular Contest 114での成績：1546位
パフォーマンス：1010相当
レーティング：856→873 (+17) :)
Highestを更新しました！#AtCoder #ARC114 https://t.co/PkxOgYDBZT
振り返り
Bのエスパー一発のみの回でした。
A問題
一読して、素数が絡みそうな問題ということで、エラトステネスの篩のようなもので解けないかと考えてみる。
そして、実装したのが、2〜50の整数について、それに対応する一番小さい素数を最初に計算しておき、あとは各について、それに対応する素数を答えに掛けるというもの。
これでサンプルは通ったが、いざ提出してみるとWAを喰らってしまう。。
よくよく考えてみると、この方法では、5と15が入力された時に、15が答えとして返ってくることが判明。そこで、をソートして計算途中の答えと、これから参照する
とのGCDが1の場合のみ、
に対応する最小の素数を掛けるということをやってみるが、こいつもWAを喰らってしまう。。。
結局、色々とこねくり回してみて何回か提出したのものの、WAは取れずじまい。B問題が奇跡的に解けて戻ってきた後も検討を継続しましたが、結局時間切れとなりました。
B問題
AのWAが取れない状態で1時間以上浪費したので、とりあえずB問題を覗いてみる。
一読して、なんかグラフっぽいのか、なんなのかよくわからん問題だと思いました。
しかし、よくよくサンプルなどを見た感触で、最初にUnion-Findを作って各と
をマージして何種類かのグループに分けて、そのグループを1つ〜全部の選ぶ方法の組み合わせ数が答えではないかとエスパーする。
で、半信半疑でこのやり方で実装してみると、なんと一発でACが取れてしまいました！
AのWAで相当心がやられつつあったので、とりあえず1つACが取れて少し安心しました。
C問題
チラ見したけど、早々に諦め。
D問題
問題すらみれておりません。
E問題
問題すらみれておりません。
F問題
問題すらみれておりません。
これまでの実績
なんだかんだで、Highest更新となりました。
総括
今回たまたまエスパー一発でレート更新となりましたが、やはりA問題の考察が至らなすぎてWAが取れなかったのが悔やまれます。ちょっとこの問題は解説なしで自力ACしようということで、現在も取り組んでおります。
ということで、また、次回も頑張ります。
