モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)参加記

2022/2/5に開催された、モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)に参加しました。

atcoder.jp

先週のABCコンテストは、体調不良で参加できませんでした。よって、2週間ぶりのABCコンテストですが、今回はなんとかレート上げになるようなパフォーマンスを出せるようにという気持ちで臨むこととしました。

今回の結果

で、今回の成績ですが、なんとか4完を確保することができたというところです。

ABC238結果
ABC238結果

ただ、E問題以降が難易度的にいつもより高めだったためか、パフォーマンスは緑後半が出てくれて、なんとかHighest更新を達成することが出来ました。

振り返り

C問題でやたらと苦労しましたが、なんとか4完で収めることができました。

ABC238提出結果
ABC238提出結果

A問題

A - Exponential or Quadratic

ここ最近のA問題の中でも、ずいぶんと難し目の問題という印象。2^nを、この制約でまともに計算すると簡単にオーバーフローするので、どうにか工夫が必要なところ。

で、nがある程度でかいと、2^n \gt n^2なのは自明なので、最初の部分を手計算してみることに。すると、nが2,3,4の場合のみ問題分の条件が偽となる様子。

ということで、nが、2〜4の時にNo、それ以外はYesと出力する実装をして、ACを取ることが出来ました。

7分42秒という、やや遅めのタイムで1完。

提出コード

https://atcoder.jp/contests/abc238/submissions/29071203

B問題

B - Pizza

三角関数使う問題かと少し考えてみたが、まったくそんな問題ではなかった。

最後に切れ目を入れた角度をPとし、次に切れ目を入れる角度は(P + A_i)を360で割った余りとする。切れ目を入れた角度を配列で管理し、昇順ソートした後、隣の要素との差分の最大値を取ればいけるかと。

ということで、あとはよしなに実装してACが取れました。

20分49秒という、大分遅めのタイムで2完。

提出コード

https://atcoder.jp/contests/abc238/submissions/29079179

C問題

C - digitnum

f(x):=x - (xより桁数が1小さい数の中の最大の数)とすると、あとは、N以下の整数について、各桁数の数がそれぞれ何個あるかを考えれば計算量もほどほどで抑えられるはず。

ということで、以下の要領で計算することにしました。

  • N以下で1桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。

  • N以下で2桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。また、9 × (2桁の数の要素数)を答えから引く。

  • N以下で3桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。また、99 × (3桁の数の要素数)を答えから引く。

  • 以上の要領で、対象とする桁数が、Nの桁数を超えるまで繰り返す。

で、実装までしてサンプルを検証してみたところ、MODの計算がちゃんと出来ていないためか、サンプル3のみが通らない。。

で、いろんなところでMODの余りを計算したり、2で割り算するところを逆元に直してみたりなど、いろいろ悪戦苦闘して、やっとサンプルが通るプログラムになりましたとさ。見返してみると、コードがぐちゃぐちゃになってます。

あとは、提出だけして、無事ACを獲得。

60分0秒での3完。いつもより大分苦戦しています。

提出コード

https://atcoder.jp/contests/abc238/submissions/29091790

D問題

D - AND and SUM

順位表からして、D問題が行ければなんとか下げは喰らわなくて済みそうかなという展開。ということで、なんとしてもこのD問題は取りたいところなので、残り時間全て投入するつもりで考察してみる。

まず、aを2進数で考えて、1が立っている桁については、x,yとも1が立っていることが確定する。よってsからaの1が立っている数を2回引いてみる。

その後、aを2回引いた後のss^{\prime}とする。s^{\prime}がマイナスになっていたら答えはNo。そうでない場合、aの1が立っていないビットの組み合わせでs^{\prime}が作れるかがみたい。よって、s^{\prime}aのANDを取り、答えが0でない場合はNoという判断で良さそう。

ということで、最後の判定で、0の場合はYesで問題ないかが微妙でしたが、サンプルは通ってくれたのでそのまま提出。なんとかACを取ることに成功しました。

79分51秒で4完。順位も1800ぐらいまで上がったので、なんとか下げは免れそうです。

提出コード

https://atcoder.jp/contests/abc238/submissions/29096640

E問題

E - Range Sums

残りが20分程度で、なんとか解けるかとE問題を覗いてみましたが、結局何もわからず。ここで時間切れとなりました。

あとで解説を見てみると、なんとグラフ問題に落とし込む必要がある問題だったとの事。うーむ、その発想は全く無かったわ。。

F問題

F - Two Exams

ワンチャンあるかとチラ見はしましたが、何もわからず。

G問題

G - Cubic?

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

H問題

Ex - Removing People

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

これまでの実績

僅かながらもHighest更新となりました。これでまた水色に一つ近づくことができました。

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

総括

今回は、C問題でやたらと時間を取られてしまいましたが、D問題がすんなりと解けてくれたので大怪我をせずに済みました。

今回は相対的に難易度高めの回だったかと思いますが、それでもD問題まで取りこぼしがなかったのは日ごろの精進の結果というところかもしれません。

これまで着実に水色に近づいてこれていますので、なんとか次回は水色パフォ以上が出せるように精進を続けていきたいと思います。

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