2023/3/11に開催されたAtCoder Beginner Contest 293に参加しました。
先週のABCは所用のため不参加だったので、２週間振りの参加。とりあえず、レートを伸ばすため、５完以上目標で臨むこととします。
２週間振りのRated参加。５完以上目標でがんばります✊
— devgenjin77 (@devgenjin77) 2023年3月11日
AtCoder Beginner Contest 293 - AtCoder https://t.co/R6IlbWJ43t
今回の結果
力及ばす。４完でした。
パフォーマンスは、ギリギリ水色に届かずでしたが、なんとかレートを上げることはできたという形です。
４完緑パフォでレートは微増しました。
— devgenjin77 (@devgenjin77) 2023年3月11日
明日も頑張ります。
devgenjin77さんのAtCoder Beginner Contest 293での成績：1783位
パフォーマンス：1188相当
レーティング：1125→1132 (+7) :)#AtCoder #ABC293 https://t.co/91BiJOGyNA
振り返り
E問題はともかく、G問題が解けそうで結局解き切ることができずでした。
A問題
問題文を読んでも、すぐには題意が分かりませんでしたが、サンプルをみると先頭から隣同士を交換する的なことをするらしいなあと。
ということで、あとは実装して提出。問題なくACが取れました。
1分48秒で1完。
提出コード
https://atcoder.jp/contests/abc293/submissions/39600647
B問題
人が呼ばれたかどうかのboolean配列を作成し、あとは前から順に、人
が呼ばれていない場合に、人
を呼ぶようにする。
こちらも、少し実装に手間取りましたが、問題なくACが取れました。
6分43秒で2完。
提出コード
https://atcoder.jp/contests/abc293/submissions/39606697
C問題
全探索になりそうという感じのC問題。
とりあえず、右に行く操作を1で表現したbit全探索で行けるかという感じで実装開始。
途中bit計算のやり方があやふやになってしまったので、過去の実装例などを見返しながらになってしまいましたが、なんとかサンプルが通せたので、そのまま提出。無事ACを取り切ることができました。
19分57秒で3完。少し時間をかけすぎの感があります。
提出コード
https://atcoder.jp/contests/abc293/submissions/39615603
D問題
連結成分を管理するということで、Union-Findを使うぐらいしか思いつかないが、今回の問題が辺の両端という感じになっているのがすこしいやらしい感じ。
が、、考察してみるとロープ自体をグラフの頂点として問題なし。Union-Findで連結成分の全ての頂点の次数が２になれば、ひとつながりと判定する感じで実装。途中余計な入力があるせいで軽くバグらせてしまいましたが、修正してなんとかACを取り切りました。
38分18秒で4完。最近ABCでのUnion-Find出題率が高めのような気がします。
提出コード
https://atcoder.jp/contests/abc293/submissions/39623341
E問題
計算式だけみれば、等比数列の和を計算すれば良いという感じだが、懸念点としては、余りをとるが素数とは限らないというところ。
とりあえず、等比数列の和であるを
で計算したが、サンプルは通るものの提出したらWAの嵐。。
どう対処したら良いか、すぐには思いつかずというところで、結局この問題は諦め。順位表を見てると、FよりGが解かれてそうな感じだったので、G問題を見ることにしました。
F問題
問題文すら見ておりません。
G問題
一読しただけでは、解法がパッと思いつかずでしたが、よくよく考えると、これってMo's Algorithmを使って解くやつでは？という直感が働きました。
ということで、過去に精進で解いたことのあるMo's Algorithmの類題を参照してみると、まさしくこれを改造すれば行けると確信。
しかし、、だいぶ前に解いたやつなので中身がどうだったのか理解があやふやだったり、今回求められている３つの索引の集合の数を求めるのもどうやるか考えないと行けない。
結局、いろいろごにょごにょしてみて、それっぽい実装ができたのが終了間際。とりあえずテストせずにダメもとで投げてみましたが、WAもREも出るという散々な結果でした。。
Ex問題
Ex - Optimal Path Decomposition
問題文すら見ておりません。
これまでの実績
一応、レートは上昇。負けるよりは随分ましです。
総括
E問題もG問題も、もう少しという所でしたが、精進不足で解くことができずでした。
Eはともかく、Gは学んだことの整理ができていれば解けていた問題ですね。次回本番で同類の問題が出ても解けるように、しっかりと復習しておこうと思います。
ということで、また次回も頑張ります。
