2020/12/19に開催されたパナソニックプログラミングコンテスト (AtCoder Beginner Contest 186)に参加しました。
前回は惜しいところで緑復帰を逃してしまいました。
そこで、今回こそはなんとか緑に復帰しようと言う意気込みで臨みました。
パナソニックプログラミングコンテスト(AtCoder Beginner Contest 186) - AtCoder https://t.co/TDXzJp9tnn
— devgenjin77 (@devgenjin77) 2020年12月19日
参加します。今度こそ緑復帰できるように頑張ります。
今回の結果
ででで、今回の結果は4完というまたまた微妙な結果。。
ここんとこ4完止まりの壁を超えるのが厳しいです。
パフォーマンスは図ったようにギリギリ緑に届かないところで、結局レーティングは微減。結局緑復帰は来年に持ち越しとなりましたー。
devgenjin77さんのパナソニックプログラミングコンテスト(AtCoder Beginner Contest 186)での成績:2814位
— devgenjin77 (@devgenjin77) 2020年12月19日
パフォーマンス:780相当
レーティング:795→793 (-2) :(#AtCoder #パナソニックプログラミングコンテスト(ABC186) https://t.co/T4WPy4s2XI
また入緑はおあずけ。また来年頑張ります。
振り返り
D問題で手こずり、EF問題は全然ダメでした。
A問題
を端数切り捨てで出力するだけ。問題なくAC。
B問題
ブロックの個数の最小値を求めて、あとはそれぞれの個数から最小値を引いた数を合計するだけ。これも問題なくAC。
C問題
数値を、10進数、8進数で表した文字列に7が含まれるかを判定する問題。
Javaでは数値を8進数の文字列に変換するメソッド、Integer.toOctalString()というメソッドがあるので実装が楽だった。問題なくAC。
D問題
結論からいうと、この問題で45分ほど溶かしてしまった。
数列の全てのペアについての差の絶対値の合計を計算する問題。
制約からみると、愚直にやるとTLEになる感じなので、なんとか工夫が必要なところ。
サンプルケースの計算過程を紙に書き出してみたりして、色々検討すると、何か法則性がありそうだが、絶対値計算があるためどうもスッキリしない感じになっていた。
で、いろいろ考察して20分以上経った後、「ソートすりゃ絶対値外せるんじゃね?」という発想が降りてくる。そっからは、以下のような要領で計算しました。
- 入力された数列を昇順ソートする。
- 2番目からの各要素から、最初の要素を引いた絶対値の配列を作成し、予め累積和を求めておく。
- 数列の1番目の要素とのペアの合計値はそのまま累積和から取得。
- 2番目以降の要素(これを番目とする)とのペアの合計値は、累積和から先頭個分の要素を引き、で求める。
これを、まで繰り返す。
これでなんとか10時前にACが取れました。これでなんとか爆死は避けられたかという感じです。
E問題
一読して、ダブリングかなんか使えるかと思ったが、思った以上に制約がデカすぎるので多分数学的にうまく計算しないと無理だと悟りました。
とりあえず、Fは見た目行けそうだったので、この問題は早々に諦め。
F問題
一読したところ、ちょいと昔にやった何かの問題に似てるなという印象。
で、少し記憶を遡ったところ、ABC182のE問題をちょっと捻った感じという感じだったので、これのACコードをちょこちょこイジればなんとかACできるのでは?という考えが浮かびました。
で、実装を進めたところ、なんとかサンプルが通るコードまではできたので投げてみましたが、これがWAが出るわ、REが出るわで、もうめちゃくちゃな状態。
コードを通読しても、WAはともかくREの原因がよくわからん感じ。で、結局都合3回ほどイジっては投げてREが返ってくるの繰り返しを続けて、結局時間切れとなりました。
コンテンスト終了後に検討してみると、そもそも制約上の最大値の場合、グリッドを2次元配列で宣言するとメモリオーバーになってしまうということに今更気づいてしまいました。
改めて難易度をみてみると青diffだったということで、まだ自分には難易度が高い問題だったというところでした。
これまでの実績
結局今回も、入緑はおあずけ。なんとももどかしい気分です。
総括
Dはソートするという発想に至るまでが遅かった。
次回からはこういう発想が早く浮かぶように、解法リストのようなものを整理しようと思います。
今年の振り返り
来週は参加できるコンテストがなさそうなので、茶色で年を越しそうな感じです。
今年の5月から気まぐれで初めてみたAtCoder。とりあえず毎週のコンテストには顔を出すようなノリで継続してきました。
最初の頃は、ABCで2完終了なんてことも珍しくなかったですが、なんとかコツコツと問題数をこなしていくことですこしづつ成長していき、やっとこさギリ緑レベルにまでにはなれたのかなと言う感じです。
来年もこの調子で継続していけば、もう少し上のレベルに到達できるかもと言う思いで今後も競プロを継続していこうと思います。
というわけで、また、来年も頑張ります。