2023/6/3に開催された、東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 304)に参加しました。
先週のARCでは、２完獲得したものの、茶パフォで惨敗。今回は、その負け分を取り戻すべく、頑張ろうという気持ちで臨みます。
Rated参加します。先週のARCの負け分を取り戻せる様に頑張ります。
— devgenjin77 (@devgenjin77) 2023年6月3日
東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304） - AtCoder https://t.co/p9wIIKR6ql
今回の結果
今回は、ABCEの変則４完で終了です。。Dで、えらくハマってしまいました。
今回も負けかなと覚悟してましたが、ジャッジ詰まりのトラブルがあった影響で、今回はUnraedになりました。結果としては、レートを下げずに済むことになり、助かったという感じです。
Dでハマったので、負け確の回でしたが、Unratedで救われました😅
— devgenjin77 (@devgenjin77) 2023年6月3日
次、頑張ります。
devgenjin77さんの東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）での成績：2232位#AtCoder #東京海上日動プログラミングコンテスト2023（ABC304） https://t.co/lRt1IfvBxs
振り返り
初っ端にサーバアクセス不能になったり、ジャッジ詰まりがあったりなど、トラブルの多い回でした。
A問題
まず、回ループして、最小の
を求める。あとは、求めた最小の
の位置を起点として、順番に
を出力するだけ。
あとは提出してＡＣ。。とおもったら、提出ページが全然開けなくなってました。。またDDos攻撃か？？
とりあえず、数分経過待ってると、アクセスできるようになったので提出。問題なくＡＣが取れました。5分23秒で1完です。
提出コード
https://atcoder.jp/contests/abc304/submissions/41936423
B問題
これ、全部IF文で書くと結構大変でバグを埋める可能性も高いと思ったので、なんとか効率的に書けないかと考えました。
結局、を
回
で割って、同じ回数
を掛けたらいいだろうという感じで実装。
提出して、問題なくACがとれましたとさ。9分3秒で2完。
提出コード
https://atcoder.jp/contests/abc304/submissions/41940315
C問題
Union-Findを使う典型問題みたいな感じ。
在りうる人のペア全てについて、ユーグリット距離が以下であれば連結させておく。最後に、各人について、人
と連結しているかを見ればよい。
あとは、実装して提出。問題なくACでした。17分37秒で3完です。
提出コード
https://atcoder.jp/contests/abc304/submissions/41946599
D問題
当初は、全然解法が分からず。。
解法っぽいものとして思いついたのは、まずケーキを縦に個に分割する際、二分探索でどのピースに、どの
座標のイチゴが存在するかを振り分け、あとは横に
分割するときに同じ要領で二分探索をすることで、各ピースについて何個イチゴがあるかを見分ける方法でした。
が、これを組んでみると、サンプルすら通らずで苦しい展開。。順位表を見ると、E問題が大分希望がありそうだったので、一旦E問題に着手することにしました。
E問題をなんとか提出したので、再度Ｄ問題に取り組むことに。結局、最初に考察した順で実装したプログラムにバグがあり、直したところでなんとかサンプルが通ったものの、計算量的にTLEが心配になりました。
が、、時間も無いので、とりあえず提出。WJのままだったので、結果は見ずに放置してましたが、終了間際に確認すると、案の定TLEでした。。
E問題
Dを一旦諦めて、E問題を考察することに。
考察を進めてみると、パスが通ってはいけない各点について、グラフ
上の、どの連結成分に属しているかを判別する必要がありそう。
あとは、個の各クエリの
の連結成分について、各
の連結成分のペアに含まれるものがあれば
No、なければYesという感じで答えればよい。
ということで、まずはUnion-Findを使って、グラフの各頂点の連結を管理し、
leader関数を使って、各について連結成分のグループを求める。
あとは、各クエリのの連結成分を同様に求めるのだが、ここで、別のUnion-Findを使って各
の連結を管理し、そのUnion-Findで
の連結成分が連結しているかという判定をしてしまったため、サンプルすら通りませんでした。。。
このバグで大分時間をつぶしてしまいましたが、なんとか時間内に気付いて修正することに成功。
で、これが提出してみると、延々とWJが続いてしまい、終わり際までACするかどうか分らんかったのですが、なんとかACだったようで助かりました。
90分8秒で4完です。
提出コード
https://atcoder.jp/contests/abc304/submissions/41971542
F問題
一応、20分延長時間があったので、問題文を覗いてみましたが、何もわからず。ここで時間切れになりました。
G問題
問題すら見れておりません。
Ex問題
Ex - Constrained Topological Sort
問題すら見れておりません。
これまでの実績
今回は、確実にレート下げを喰らう展開でしたが、Unratedになったので、変動なしです。
総括
今回は、運よく？Untatedになったものの、D問題で大きな考察ミスをするなど、反省点が大分多い回でした。
最近、仕事が忙しい関係で、なかなか精進の時間が取れていない状態ですが、なんとか次週巻き返しを目指して、今回の問題の復習をして、次回に備えようと思います。
ということで、また次回も頑張ります。
