2023/5/20に開催された、トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)に参加しました。
先週のARCでは、０完爆死を喰らったのでレートがだいぶ下がってしまいました。今回は、その負け分を少しでも取り戻そうという気持ちで臨みました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年5月20日
先週のARCで、だいぶレートを落としたので、できるだけ取り戻したいです。
トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302) - AtCoder https://t.co/JSvWSAjfJX
今回の結果
今回は、久しぶりの５完達成。個人的には、まあまあかなという印象です。
順位的に、今回は緑パフォぐらいかなあと思ってましたが、なんとか水パフォに到達。先週末の負け分には及びませんが、なんとか少し戻す事ができましたとさ。
５完水パフォでした😃
— devgenjin77 (@devgenjin77) 2023年5月20日
devgenjin77さんのトヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)での成績：1444位
パフォーマンス：1256相当
レーティング：1099→1116 (+17) :)#AtCoder #トヨタ自動車プログラミングコンテスト2023#2(ABC302) https://t.co/a2CQZKZDVq
振り返り
超久々に６完取れるかという回でしたが、取り切る事ができませんでした。
A問題
が答え。久々にシンプルなA問題だったなあという印象です。
1分23秒で1完。
提出コード
https://atcoder.jp/contests/abc302/submissions/41538286
B問題
なんか、B問題にしては結構難し目の問題だなあという印象でした。
当初、実装方針でだいぶ迷ってしまい、時間を取られましたが、結局各マスから８方向に最大５文字を取得し、その文字列がsnukeかどうかを判定するという方針で実装することに。
８方向の移動の実装にやたらと手間取り、B問題にしては、結構時間をかけてしまいましたが、なんとか１度の提出でAC。
21分43秒で2完。だいぶ立ち遅れた感じがあります。
提出コード
https://atcoder.jp/contests/abc302/submissions/41550976
C問題
全ての並べ方を試し、隣接する要素間の異なる文字の数が全て１ならYesとなる。
この実装には、いわゆるC++でいうnext_permutationが必要なのだが、Javaには標準で備わっていないので、過去問で作った独自実装を持ってきました。これが無かったら、まただいぶ解答時間も変わってきただろうなあと。
そんな感じで、１度の提出でAC。29分42秒で3完です。Bで作った遅れを少し取り戻しました。
提出コード
https://atcoder.jp/contests/abc302/submissions/41554817
D問題
配列の要素を、全てTreeSetに追加。次に、配列
を全探索し、
以下で最大の要素をTreeSetから取得する。
取得できた場合且つ、その要素との差が
以下の場合、
とその要素の和が答えの候補になる。あとは、同様の要領で、答えの最大値を計算していけば良い。
という感じの実装で、なんとか１回の提出でACが取れましたとさ。
39分16秒で4完。B問題で時間を消費した時はどうなるかと思いましたが、だいぶいい感じまで取り戻せました。
提出コード
https://atcoder.jp/contests/abc302/submissions/41558936
E問題
答えの初期値をにしておく。また各クエリを処理するさいに、頂点の次数を管理する配列、および頂点同士の結びつきを管理する隣接リストを更新する。
具体的には、クエリ１の処理では、頂点、
を結ぶ辺を追加し、次数をそれぞれ１ずつ増加させる。なお、頂点
、
について、増加前の次数が０の場合、それぞれ答えから１ずつ減らす。
クエリ２の処理では、頂点の次数を０にし、頂点
、
を結ぶ辺を削除。なお、頂点
については、削除前の次数が０でない場合は、答えから１減らし、
に隣接していた頂点の次数が１から０に変化する場合は、それぞれ答えから１減らす。
というような感じで実装。初回の提出では、少しバグらせてしまいWAを喰らいましたが、２回目でなんとかACがとれました。
60分31秒1ペナで5完。とりあえず、今回は勝ちかなと思ってましたが、どうも順位表を見るとF問題ぐらいまでがボーダーのような感じ。。6完するまで油断できない感じでした。
提出コード
https://atcoder.jp/contests/abc302/submissions/41566729
F問題
集合云々言っているが、これは、それぞれの集合を頂点と見立てて、頂点グラフとして最短経路問題と捉えた方が良さそうという感じがしました。
それぞれの集合からマージできる集合に遷移できるかを判断して、辺を追加。あとはを含む集合をスタート地点とし、スタート地点の数だけ、ダイクストラ法を回し、
を含むゴール地点までのまでの最短経路を求める感じの実装で、なんとか時間ギリギリでサンプルまで通す事ができました。
が、、これを投げてみると、TLE×1で終了という残念な結果で結局ACを取る事ができず。このまま終了時間になりましたとさ。。
解説を読んでみると、おそらくダイクストラをスタート地点分回すのが良くない感じで、結局スタート地点をまとめる超頂点を作ることができていればACができてたかもという感じ。
惜しいところで6完を逃してしまいましたが、これも仕方なし。次に向けて復習します。
G問題
問題すら見ておりません。
Ex問題
問題すら見ておりません。
これまでの実績
少しレートを戻して、１１００台になりました。
総括
今回も前回も、惜しいところで水Diff問題が解けずでした。
まだまだ、入水に至るまでの実力が不足しているのかなあという感じですが、当面は愚直に各回の復習をこなすことで実力を上げるしかないですね。また次回に向けて準備していきます。
ということで、また次回も頑張ります。
