devgenjin77’s blog

AtCoder Beginner Contest 261 参加記

AtCoder 競プロ ABC

2022/7/23に開催されたAtCoder Beginner Contest 261に参加しました。

先週はARCで惨敗してABCで少し取り戻すという展開。今週はARCが無いので、なんとか今回は水パフォを取ってレートを上げれるようにという気持ちで臨むこととしました。

Rated参加します。今回は水パフォ取れるように頑張ります✊

AtCoder Beginner Contest 261 - AtCoder https://t.co/rLPDgovRFS
— devgenjin77 (@devgenjin77) 2022年7月23日

今回の結果

で、今回の結果は4完。時間は十分ありましたが、5完には到達できずでした。

ABC261結果

これでもパフォーマンスは緑上位。水パフォは行きませんでしたが、なんとかレートを上げることはできました。

4完緑パフォでなんとかレート上げ😃
来週も頑張ります。
devgenjin77さんのAtCoder Beginner Contest 261での成績：2149位
パフォーマンス：1081相当
レーティング：1030→1035 (+5) :)#AtCoder #ABC261 https://t.co/lP8d1mFT5b
— devgenjin77 (@devgenjin77) 2022年7月23日

振り返り

E問題を解き切ることができませんでした。

ABC261提出結果

A問題

A - Intersection

A問題にしては、いろんなケースを想定しないとWAを喰らってしまいそうな複雑な問題という印象。

考察した結果、左端を $max(L_1, L_2)$ 、右端を $min(R_1, R_2)$ とし、左端の座標から右端の座標の距離を求めれば解決できそうな感じ。

重複区間が無いケースを想定して実装。提出して問題なくACが取れましたとさ。

4分2秒で1完。少し時間をかけすぎかも。

提出コード

https://atcoder.jp/contests/abc261/submissions/33432347

B問題

B - Tournament Result

いわゆる、やるだけの問題。PaizaのCランクで出てきそうな感じだなあ。

2重ループを使って、勝敗表に矛盾がないかチェック。実装に少し時間がかかってしまいましたが、問題なくACを取ることができました。

9分39秒で2完。

提出コード

https://atcoder.jp/contests/abc261/submissions/33439448

C問題

C - NewFolder(1)

最近のC問題としては、少し単純な問題という印象。

Mapを使って、文字列の出現回数を管理し、2回目以降の場合は、文字列の末尾に出現回数に応じた数字をつければ良い。

こちらも、問題なくACを取ることができました。

15分22秒で3完。ここ最近のABCと比べると、大分ペースが早い方です。

提出コード

https://atcoder.jp/contests/abc261/submissions/33445497

D問題

D - Flipping and Bonus

一読して、解法が全然思いつかず。。

一瞬、今回3完で詰んだかと思いましたが、順位表をみると、やたらとAC数の増加ペースが速いので、そんなに複雑な解法では無いんだろうなという感じがする。

で、色々考察した結果、 $N=5000$ なら、 $N \times N$ の配列が作れそうで、その範囲でできるDPが構築できれば行けるだろうという結論に至る。

そこで、 $\ dp\lbrack i\rbrack \lbrack j \rbrack :=$ $i$ 回目のプレイで $j$ 回連続表が出た時に貰える最大の金額のDPを考える。

$i$ 回目のプレイでは、表を出した時に前回の連続数にプラス１した状態の金額を計算。裏を出した時には、前回のプレイで最も大きい金額を連続数が0の金額として採用する。

あとは、実装して、なんとか提出一回でACを取り切ることができました。

45分6秒で4完。これでなんとか緑パフォぐらいは確保できたかと。。

提出コード

https://atcoder.jp/contests/abc261/submissions/33461060

E問題

E - Many Operations

残りが50分以上あるので、なんとか5完以上は目指したいところだが、問題を一読した感じでは、上手い解法は思いつかず。

当初は、xor,or,andはそれぞれ順番を入れ替えても問題無いのかと思い、それぞれの演算毎に合算したものを演算に使う的なやり方を試してみたが、全然通らず。

あとは、論理演算の公式などをググってみるも、使えそうなものも無いということで、結局時間だけを浪費。。結局、このまま時間切れとなりましたとさ。

で、解説を見ると、bit毎に単独で合成関数を構築すれば解けるとのこと。本番時は全く思いつかずでした。過去に類型などあったんだろうか。。

F問題

F - Sorting Color Balls

ワンチャンあるかと、問題文を見てみましたが、何も思いつかずで撤退。

G問題

問題すら見れておりません。

Ex問題

Ex - Game on Graph

問題すら見れておりません。

これまでの実績

レートは微増しましたが、水色への道はまだまだ遠そうです。

コンテスト実績

総括

今回のEとFは、精進不足で解き切るまでの知識レベルに到達できていなかったという感想です。

しかし、今回もD問題クラスでも緑の下位あたりのDiffになっている点については、参加者のレベルがだんだん上がっているという印象を受けます。

このままでは、精進を重ねても、緑レートを維持するのも大変そうだなあ、という感じですが。とりあえず今回の復習をして次週に備えていきます。

ということで、また次回も頑張ります。