パナソニックプログラミングコンテスト (AtCoder Beginner Contest 186) 参加記

2020/12/19に開催されたパナソニックプログラミングコンテスト (AtCoder Beginner Contest 186)に参加しました。

atcoder.jp

前回は惜しいところで緑復帰を逃してしまいました。

そこで、今回こそはなんとか緑に復帰しようと言う意気込みで臨みました。

今回の結果

ででで、今回の結果は4完というまたまた微妙な結果。。

ここんとこ4完止まりの壁を超えるのが厳しいです。

ABC186結果

ABC186結果

パフォーマンスは図ったようにギリギリ緑に届かないところで、結局レーティングは微減。結局緑復帰は来年に持ち越しとなりましたー。

振り返り

D問題で手こずり、EF問題は全然ダメでした。

ABC186提出結果

ABC186提出結果

A問題

A - Brick

N / Wを端数切り捨てで出力するだけ。問題なくAC。

B問題

B - Blocks on Grid

ブロックの個数の最小値を求めて、あとはそれぞれの個数から最小値を引いた数を合計するだけ。これも問題なくAC。

C問題 

C - Unlucky 7

数値を、10進数、8進数で表した文字列に7が含まれるかを判定する問題。

Javaでは数値を8進数の文字列に変換するメソッド、Integer.toOctalString()というメソッドがあるので実装が楽だった。問題なくAC。

D問題

D - Sum of difference

結論からいうと、この問題で45分ほど溶かしてしまった。

数列の全てのペアについての差の絶対値の合計を計算する問題。

制約からみると、愚直にやるとTLEになる感じなので、なんとか工夫が必要なところ。

サンプルケースの計算過程を紙に書き出してみたりして、色々検討すると、何か法則性がありそうだが、絶対値計算があるためどうもスッキリしない感じになっていた。

で、いろいろ考察して20分以上経った後、「ソートすりゃ絶対値外せるんじゃね?」という発想が降りてくる。そっからは、以下のような要領で計算しました。

  • 入力された数列Aを昇順ソートする。
  • 2番目からN番目の各要素から、最初の要素を引いた絶対値の配列を作成し、予め累積和を求めておく。
  • 数列の1番目の要素とのペアの合計値はそのまま累積和から取得。
  • 2番目以降の要素(これをi番目とする)とのペアの合計値は、累積和から先頭N - 1 - i個分の要素を引き、|A_i - A_{i-1}| \times (N - i)で求める。
    これを、i=N-1まで繰り返す。

これでなんとか10時前にACが取れました。これでなんとか爆死は避けられたかという感じです。

E問題

E - Throne

一読して、ダブリングかなんか使えるかと思ったが、思った以上に制約がデカすぎるので多分数学的にうまく計算しないと無理だと悟りました。

とりあえず、Fは見た目行けそうだったので、この問題は早々に諦め。

F問題

F - Rook on Grid

一読したところ、ちょいと昔にやった何かの問題に似てるなという印象。

で、少し記憶を遡ったところ、ABC182のE問題をちょっと捻った感じという感じだったので、これのACコードをちょこちょこイジればなんとかACできるのでは?という考えが浮かびました。

で、実装を進めたところ、なんとかサンプルが通るコードまではできたので投げてみましたが、これがWAが出るわ、REが出るわで、もうめちゃくちゃな状態。

コードを通読しても、WAはともかくREの原因がよくわからん感じ。で、結局都合3回ほどイジっては投げてREが返ってくるの繰り返しを続けて、結局時間切れとなりました。

コンテンスト終了後に検討してみると、そもそも制約上の最大値の場合、グリッドを2次元配列で宣言するとメモリオーバーになってしまうということに今更気づいてしまいました。

改めて難易度をみてみると青diffだったということで、まだ自分には難易度が高い問題だったというところでした。

これまでの実績

結局今回も、入緑はおあずけ。なんとももどかしい気分です。

コンテスト実績

コンテスト実績

総括

Dはソートするという発想に至るまでが遅かった。

次回からはこういう発想が早く浮かぶように、解法リストのようなものを整理しようと思います。

今年の振り返り

来週は参加できるコンテストがなさそうなので、茶色で年を越しそうな感じです。

今年の5月から気まぐれで初めてみたAtCoder。とりあえず毎週のコンテストには顔を出すようなノリで継続してきました。

最初の頃は、ABCで2完終了なんてことも珍しくなかったですが、なんとかコツコツと問題数をこなしていくことですこしづつ成長していき、やっとこさギリ緑レベルにまでにはなれたのかなと言う感じです。

来年もこの調子で継続していけば、もう少し上のレベルに到達できるかもと言う思いで今後も競プロを継続していこうと思います。

というわけで、また、来年も頑張ります。