2022/2/5に開催された、モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)に参加しました。
先週のABCコンテストは、体調不良で参加できませんでした。よって、2週間ぶりのABCコンテストですが、今回はなんとかレート上げになるようなパフォーマンスを出せるようにという気持ちで臨むこととしました。
Rated参加します。先週のABCは体調不良で参加できずでしたが、今回はレートを上げられるように頑張ります。
— devgenjin77 (@devgenjin77) 2022年2月5日
モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238) - AtCoder https://t.co/WvT7598tzu
今回の結果
で、今回の成績ですが、なんとか4完を確保することができたというところです。
ただ、E問題以降が難易度的にいつもより高めだったためか、パフォーマンスは緑後半が出てくれて、なんとかHighest更新を達成することが出来ました。
😂😂😂
— devgenjin77 (@devgenjin77) 2022年2月5日
devgenjin77さんのモノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)での成績:1860位
パフォーマンス:1155相当
レーティング:1054→1065 (+11) :)
Highestを更新しました!#AtCoder #モノグサプログラミングコンテスト2022(ABC238) https://t.co/1GBri8FxZy
振り返り
C問題でやたらと苦労しましたが、なんとか4完で収めることができました。
A問題
ここ最近のA問題の中でも、ずいぶんと難し目の問題という印象。を、この制約でまともに計算すると簡単にオーバーフローするので、どうにか工夫が必要なところ。
で、がある程度でかいと、なのは自明なので、最初の部分を手計算してみることに。すると、が2,3,4の場合のみ問題分の条件が偽となる様子。
ということで、が、2〜4の時にNo、それ以外はYesと出力する実装をして、ACを取ることが出来ました。
7分42秒という、やや遅めのタイムで1完。
提出コード
https://atcoder.jp/contests/abc238/submissions/29071203
B問題
三角関数使う問題かと少し考えてみたが、まったくそんな問題ではなかった。
最後に切れ目を入れた角度をとし、次に切れ目を入れる角度はを360で割った余りとする。切れ目を入れた角度を配列で管理し、昇順ソートした後、隣の要素との差分の最大値を取ればいけるかと。
ということで、あとはよしなに実装してACが取れました。
20分49秒という、大分遅めのタイムで2完。
提出コード
https://atcoder.jp/contests/abc238/submissions/29079179
C問題
より桁数が1小さい数の中の最大の数とすると、あとは、以下の整数について、各桁数の数がそれぞれ何個あるかを考えれば計算量もほどほどで抑えられるはず。
ということで、以下の要領で計算することにしました。
以下で1桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。
以下で2桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。また、 × (2桁の数の要素数)を答えから引く。
以下で3桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。また、 × (3桁の数の要素数)を答えから引く。
以上の要領で、対象とする桁数が、の桁数を超えるまで繰り返す。
で、実装までしてサンプルを検証してみたところ、MODの計算がちゃんと出来ていないためか、サンプル3のみが通らない。。
で、いろんなところでMODの余りを計算したり、2で割り算するところを逆元に直してみたりなど、いろいろ悪戦苦闘して、やっとサンプルが通るプログラムになりましたとさ。見返してみると、コードがぐちゃぐちゃになってます。
あとは、提出だけして、無事ACを獲得。
60分0秒での3完。いつもより大分苦戦しています。
提出コード
https://atcoder.jp/contests/abc238/submissions/29091790
D問題
順位表からして、D問題が行ければなんとか下げは喰らわなくて済みそうかなという展開。ということで、なんとしてもこのD問題は取りたいところなので、残り時間全て投入するつもりで考察してみる。
まず、を2進数で考えて、1が立っている桁については、とも1が立っていることが確定する。よってからの1が立っている数を2回引いてみる。
その後、を2回引いた後のをとする。がマイナスになっていたら答えはNo。そうでない場合、の1が立っていないビットの組み合わせでが作れるかがみたい。よって、とのANDを取り、答えが0でない場合はNoという判断で良さそう。
ということで、最後の判定で、0の場合はYesで問題ないかが微妙でしたが、サンプルは通ってくれたのでそのまま提出。なんとかACを取ることに成功しました。
79分51秒で4完。順位も1800ぐらいまで上がったので、なんとか下げは免れそうです。
提出コード
https://atcoder.jp/contests/abc238/submissions/29096640
E問題
残りが20分程度で、なんとか解けるかとE問題を覗いてみましたが、結局何もわからず。ここで時間切れとなりました。
あとで解説を見てみると、なんとグラフ問題に落とし込む必要がある問題だったとの事。うーむ、その発想は全く無かったわ。。
F問題
ワンチャンあるかとチラ見はしましたが、何もわからず。
G問題
問題すら見ておりません。
H問題
問題すら見ておりません。
これまでの実績
僅かながらもHighest更新となりました。これでまた水色に一つ近づくことができました。
総括
今回は、C問題でやたらと時間を取られてしまいましたが、D問題がすんなりと解けてくれたので大怪我をせずに済みました。
今回は相対的に難易度高めの回だったかと思いますが、それでもD問題まで取りこぼしがなかったのは日ごろの精進の結果というところかもしれません。
これまで着実に水色に近づいてこれていますので、なんとか次回は水色パフォ以上が出せるように精進を続けていきたいと思います。
ということで、また次回も頑張ります。