ABC186の感想（バーチャル）
先ほど、パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）にバーチャル参加してきました。
問題はこちらから。
バーチャル参加（後日参加）なので結果は推定ですがこんな感じでした。
abcdの4完（0wa）
でした。1000点（34:13）をコンテストの順位表と照らし合わせると、
2176位 / 6205人
パフォーマンス：968
ぐらいになると思います。
しかし、後日参加だとレーティングの変動がないため、参加する際の精神面が結構違いました。「別に失敗しても落ちないし」という気持ちでしたので、レートがかかったコンテストの結果と比較するのは適切ではないのかもしれないですが、一応このくらいだよという目安程度に。
結果は「相変わらず」の一言ですね。伸びもなければ、落ち込みもなしです。変化がないのは少々面白くありませんが、結果を安定させながら、いつか上振れる期待しながら取り組んでいきます。
さて、感想を書いていきます。
A問題
n/wでおしまいです。結果を切り上げるのか、切り捨てるのか20秒ぐらい悩みましたが、まあ切り捨てでいいでしょう。
B問題
問題文が頭に入ってこずに焦りました。でも、理解できてしまえばなんてことはありません。全体の最小値を求めて、各マスに関してその最小値との差分の総和が答えになります。
制約もまだまだ緩いので、愚直にやれば通りました。
C問題
これは逆に一瞬で問題を理解しました。7を憎んでいます。
解法としてはかなり単純で、%10 /10と%8 /8で判定をするだけです。
が問題は計算量です。制約を見ると、n <= 10^5でした。各桁の判定でwhile文を回すのですが、最大5桁でそれを2回やるので、10桁分判定ですね。そのため、全体で10^6程度になります。
これならば行けると思い、そのまま実装。テストケース2が最大ケースでしたので、間に合うことを確かめたのち提出。とっても親切でした。
D問題
数値の差の絶対値の総和を取ります。
さすがにDともなると、愚直解法では間に合いません。
図を書いたり、グラフを書いたり色々と考えました。最大値を最小値の差の区間が3個できるからー、みたいなことをずっとやってました。
結局、ソートしたのち累積和を取得すれば、各数字に関してO(1)で総和が求まります。それをn個分やれば答えです。負の値が入ってきても大丈夫です。
おそらくですが、計算量はソートがボトルネックなのかな？O(nlog n)で解けると思います。
E問題
玉座に座る問題です。
似た問題は何問か見たことはありましたが、本問は1ループが非常に長かったです。ループ長nはn<=10^9でした。
ｎが小さければ、mod n として余りの出現をメモしていくことで答えが求まるのですが、、、
余りが0付近を探索みたいなこともやりましたが、kも大きい際には1手で反対側まで行けてしまって、全然、付近の探索になりませんでした。
完全にお手上げでした。精進します。
今回は過去最速でDまで解くことができたので、E問題をじっくりと考えることができました。こういう小さな成長を噛みしめつつ、いつか5問正解することを夢見て生きていきます。
この記事が気に入ったらサポートをしてみませんか？