2023/4/1に開催されたAtCoder Beginner Contest 296に参加しました。
先週は所用で不参加だったため、２週間ぶりの参加となります。
直近のARCでの爆死なんかもあり、現状レートが低迷しているので、なんとか今回は水パフォを取ってレートを上げていこうという感じで臨みます。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年4月1日
今回も、とりあえず水色パフォ目標で頑張ります✊
AtCoder Beginner Contest 296 - AtCoder https://t.co/xJ5G1IQFtI
今回の結果
なんとか５完を達成することができました。
そして、堂々の水色パフォーマンスを達成。レートの方は、再度1100台に戻すことができましたとさ。
５完水パフォで、レートの方もだいぶ戻すことに成功しました😆
— devgenjin77 (@devgenjin77) 2023年4月1日
来週も頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 296での成績：1078位
パフォーマンス：1396相当
レーティング：1077→1113 (+36) :)#AtCoder #ABC296 https://t.co/hETA3Fz1Cb
振り返り
D問題でつまづいてしまいましたが、なんとかE問題でリカバリすることができました。
A問題
文字列の中に、
FFかMMがあればNo。それ以外はYesという実装でACがとれました。
1分24秒で1完。
提出コード
https://atcoder.jp/contests/abc296/submissions/40207487
B問題
盤上の*の位置を0-indexedで検索し、適切に変換するだけ。
すこし時間がかかりましたが、問題なくACが取れました。5分29秒で2完。
提出コード
https://atcoder.jp/contests/abc296/submissions/40213425
C問題
の場合は、必ず
Yesとなる。
上記以外の場合、配列の全要素をSetに突っ込んでから、
となる値がSetに存在すれば
Yesとなる。
これも、実装に少し時間がかかってしまいましたが、問題なくAC。12分16秒で3完。
提出コード
https://atcoder.jp/contests/abc296/submissions/40221134
D問題
制約から察するに、か
を上限として全探索するやつかという印象。
まず、の場合は、
が作れるのが確定しているので答えは
。
上記以外の場合は、と定義したとき、
の下限を
、上限を
とし、その区間を全探索。
以上となる
を求め、その中の最小値が答えとなる。
と、、いう感じで実装すべきだったのですが、当初はの上限を
にしていたため、６WAを喰らってしまい、その後も見当外れの修正を投げ続けたため、ペナルティを喰らいまくってしまいました。
結局、探索の上限が怪しそうだということにやっと気づき、探索上限を少し緩めるという緊急回避的な実装でなんとかAC。
50分56秒4ペナで4完。ペナ分も含めて40分程度損している計算になるので、なかなか痛いミスです。
提出コード
https://atcoder.jp/contests/abc296/submissions/40243445
E問題
問題の意図が捉えづらく、要点を掴むまで、10分程度を要してしまいましたが、要は操作回数として、どんなを指定されても、その回数分遷移した後で作れる
が何通りあるかという問題の模様。
当初は、ダブリングっぽいかなあと思いましたが、実装のイメージがつかず。。
が、よくよく考えてみると、有向グラフの強連結成分が活用できるかなあという感じがしてきたので、とりあえずSCCライブラリに突っ込んで見ることに。
このとき、複数の頂点で強連結成分を構成している場合、その頂点全てが作れるとなる。単一頂点で強連結成分になっている場合は、自己ループしている頂点であればOK。
という感じで実装したら、見事当たりだったみたいで、なんとかACを取ることができましたとさ。
82分10秒4ペナで5完。この時点で、3桁順位に乗ったので、なんとか今日は勝てたかなという感じでした。
提出コード
https://atcoder.jp/contests/abc296/submissions/40256650
F問題
とりあえず、時間があるので問題文をのぞいて見ましたが、なんかARCかAGCに出てきそうな問題という印象。
これは多分、転倒数を見て、できるかできないかを判別するやつだという直感があったのですが、実際のところ解法まで落とし込むことはできず。ここで時間切れとなりました。
結局、コンテスト後の解説をみると、やはり転倒数が絡む問題だったとのこと。実は、まだ転倒数のライブラリすら作ってない状態なので、これを機に整備を進めていきたいと思います。
G問題
とりあえず、チラ見をして見ましたが、何も思いつかず。早々に撤退しました。
Ex問題
問題文すら見ておりません。
これまでの実績
とりあえず、レートは1100台まで回復。今度こそ、この調子で入水まで一気に行きたいですね。
総括
今回はD問題で結構やらかしたのですが、なんとかE問題で解法が降りてきてくれたので水パフォが達成できました。
これでレートは少し回復しましたが、ここからさらに上げきることができるかどうかが肝心。次の土日はARCとABCがあるので、直近の過去問の復習をこなしながら、次回に向けて準備していきたいと思います。
ということで、また次回も頑張ります。
