2020/11/8に開催されたAtCoder Beginner Contest 182に参加しました。
最近レートの上昇傾向が続いており、そろそろ入緑が見えているところです。
今回も4完以上であれば最悪レート下げが無いかなぐらいの気持ちで臨みました。
AtCoder Beginner Contest 182 - AtCoder https://t.co/ub6eR9Uxvt
— devgenjin77 (@devgenjin77) 2020年11月8日
参加します。ここ最近は緑パフォで安定しているので、今回も4完、できればそれ以上を目標にします。
今回の結果
で、今回は個人的には上出来の5完達成！
そして、レートの方は大幅上昇。念願の入緑を達成できました！
devgenjin77さんのAtCoder Beginner Contest 182での成績：1787位
— devgenjin77 (@devgenjin77) 2020年11月8日
パフォーマンス：1149相当
レーティング：769→816 (+47) :)
Highestを更新し、6 級になりました！#AtCoder #ABC182 https://t.co/7qulu64N1n
5完達成でHighest更新！入緑達成しました😂
これから入水に向けてさらに精進します！
振り返り
序盤で少しつまづきましたが、なんとかギリ5完達成しました。
A問題
を計算すればOK。
問題なくAC。
B問題
のため、2〜1000それぞれについてGCD度の数を求めて、それらの最大値を出せばOK。
の、、はずだったんですが、実戦では、こんなに愚直だとTLEするかもという疑念が頭をよぎり、なんとか効率化できないかというところを検討することに。
で、の最大値の平方根を限度に計算してみたら、これがWA。。
じゃ、を2で割った数を限度に計算してみたら、これがまたWA。。
結局、素直にの最大値を限度に計算して、やっとこさACが取れましたとさ。
C問題
「3の倍数 条件」でググってみたら、どうも各位の数字の和が3の倍数であればOKとのこと。ということで、以下の解法で実装してみることに。
- 各位の数字の和
を計算する。それが3の倍数なら、0が答え。
にあれば、それを引くと3の倍数になるので1が答え。そうでない場合、2,5,8のいずれかが
- これに該当しない場合は-1が答え
という要領で解いたらAC取れました。
因みに、コンテスト後のTLをみると、bit全探索というキーワードが結構でてたんですが、その発想には至りませんでした。
D問題
これは、愚直に計算するとTLEになるやつ。累積和を使って工夫をしていく。
サイズの配列を2つ用意し、それぞれ
まで動いたときに
- 最終的に正の方向にどれだけ動いたか。
- 途中で、最大正の方向にどれだけ動いたか。
という結果をあらかじめ計算しておく。あとは上手い具合に計算してACが取れました。
E問題
残り30分ぐらいで臨んだこの問題。
問題を一読して思いついた解法。とりあえずサイズの2次元マップを作って、そこに電球とブロックを配置。あとは横方向を左右に、縦方向を上下に走査して、光を伝播させる要領でやればOK。
あとは実装してAC。と、、おもったが、なぜかサンプルが通らない。
とりあえずソースを見てみると、横に伝播した明かりが後で下にも伝播する下手くそ実装でバグっていたことが発覚。
もう残り時間も10分切ったぐらいでこの有様。惜しいとこまで行ってるのでなんとかならんかと知恵を絞ってみたら、縦方向に走査する用のマップと横方向に走査する用のマップを作って後で合算すりゃいいんじゃねということに気付く。
あとは時間に追い立てられながら、なんとか実装完了して、投げてみたら一発ACとなりましたーヾ(´∀｀)ノﾜｰｲ
終了3分を切ってのAC。喜びもひとしおです。
F問題
問題は一読しましたが、解法がまったく思いつかないので早々に諦めでした。
これまでの実績
念願の入緑。AtCoder始めてから半年弱でやっとこさここまでたどり着くことができました。
総括
今の自分の実力だと、ABCクラスのコンテストでは全完は厳しいが、5完は現実的な目標になるかなという印象が抱けるようにはなりました。
今回は久々の5完でしたが、今後のABCは安定して5完程度の結果が残せるように精進していこうと思います。
また、次回も頑張ります。
