AtCoder Beginner Contest 272 参加記

2022/10/8に開催されたAtCoder Beginner Contest 272に参加しました。

atcoder.jp

今週は、ABC、ARCと連続で開催される週。この土日で大きくレートを上げるために、まずはこのABCで水パフォを取っていこうという気持ちで臨むこととしました。

今回の結果

だいぶ苦戦しましたが、なんとか5完を達成することが出来ました!

ABC272結果
ABC272結果

パフォーマンスは水色の後半あたりという望外の結果となり、順位は久々の3桁台!レートは大きく上がって、Highest更新。水色まで後少しというところまできました。

振り返り

E問題がなんとか通ってくれたので、だいぶレートが上がってくれました。

ABC272提出結果
ABC272提出結果

A問題

A - Integer Sum

数列Aの合計を求める問題。とりあえず、読み込んだA_iの値を随時合計に足し込めば良い。

1分0秒で1完。最近のA問題では、だいぶ簡単な方だったかと。

提出コード

https://atcoder.jp/contests/abc272/submissions/35467677

B問題

B - Everyone is Friends

  • attend\lbrack i \rbrack \lbrack j \rbrack :=iと人jが同じ舞踏会に参加したことがあるか。

上記の配列を作成し、あとは各舞踏会に参加した人の内容から、参加した組を全探索し、参加した組をTrueで更新する。全部Trueで埋まっていたら、答えはYes。

ということで、あとは実装して一発でAC。

7分27秒で2完。多少時間が掛かりすぎかもしれません。

提出コード

https://atcoder.jp/contests/abc272/submissions/35474292

C問題

C - Max Even

Aの異なる2要素の和を全探索すると、O(N^2)の計算量が掛かりTLEとなる。

ただし、答えを偶数に限定すると、奇数足す奇数のケースか、偶数足す偶数のケースに限定される。

よって、Aのうち、一番大きい奇数と二番目に大きい奇数の和と、一番大きい偶数と二番目に大きい偶数の和を比較して大きい方を出せば良い。

あとは、偶数、奇数がそれぞれ2つないケースなどに気をつけて実装。一発でACが取れました。

13分46秒で3完。ここまでは、かなり順調にきています。

提出コード

https://atcoder.jp/contests/abc272/submissions/35478453

D問題

D - Root M Leaper

以下の要領で解きました。

  • cost\lbrack i \rbrack \lbrack j \rbrack := マス(1,1)から、マス(i,j)に到達するときの最小の操作回数。

  • 初期値は、 cost\lbrack 1 \rbrack \lbrack 1 \rbrack = 0、それ以外はN^2とする。

  • マス(1,1)から始めて、移動できるマスをBFSの要領で全探索する。移動元の操作回数+1が、遷移先の操作回数より小さい場合、遷移先の操作回数を、移動元の操作回数+1で更新。移動先のマスの情報をキューに突っ込む。

  • iの移動先k1Nの範囲で固定したとき、ぞれぞれのkに対するjの移動先lは、(i - k)^2 + (j - l)^2 = Mという関係になることから、M- (i - k)^2が平方数であり、かつl1Nの範囲内になる時に限定される。

  • 前計算で、\sqrt M以下の平方数を求めておき、Setに突っ込むなりすると、ある整数が平方数かどうかの判定を高速化できる。

とこんな感じで実装したらサンプルが通ったので、提出したら、なんとかACをとることができましたとさ。

41分25秒で4完。これで、なんとか爆死はなさそうです。

提出コード

https://atcoder.jp/contests/abc272/submissions/35490301

E問題

E - Add and Mex

順位表からすると、だいぶむずそうなこの問題。内容をみてみると、確かに手強そうである。

が、F以降はそれ以上に絶望的な難易度のようなので、なんとかE問題を解き切るしかなさそう。

ということで、解法を検討してみるが、うまいやり方が思いつかず。。

が、、よくよく考えてみると、M回それぞれの操作に対して、Mexになり得る値は0Nに限定されることから、Aのそれぞれの要素について、何回目の操作で0Nの値になるかを確認すればよさそう。

ということで、appered\lbrack i \rbrack :=i回目の操作で現れる0Nの範囲の整数の集合として管理しておく。またAのそれぞれの要素について、操作後の値が、0Nの範囲になる操作回数とその値をもとに配列を更新していく。

あとは、1M回の操作をしたときのMexは、上記の配列を0Nまで存在するかどうかを見ていくこととする。

やたら処理時間がかかりそうな実装になったので、提出時はTLEだけが心配。

実際、ジャッジ中はTLEになるかどうかという動きを見せてましたが、なんとか1400ms台で耐えてくれました!

87分17秒で5完。これでなんと順位は830位まで上昇。水色は余裕で突破できそうです!

提出コード

https://atcoder.jp/contests/abc272/submissions/35504135

F問題

F - Two Strings

一応時間はあったので、問題文を見ましたが、なにも思いつかず。ここで時間切れとなりました。

G問題

G - Yet Another mod M

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

Ex問題

Ex - Flipping Coins 2

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

これまでの実績

ここ最近の停滞ムードを抜けて、レートは大幅に上昇!念願の入水までもう少しです。

コンテスト実績
コンテスト実績

総括

最近は、過去のABCの問題の解き直しなどに注力してますが、その成果がいい感じに出てきているように感じます。

ただ、レートの方も、水色間際まで来ましたので、これからのABCでは水色パフォが最低限のノルマになってきますね。そのためには、青Diff程度の問題が本番ACできるように、練習問題のレベルを上げていきたいと思います。

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