110. AtCoder参加記録(AtCoder Beginner Contest 250)
17回参加でレート 1037 です。
今回はパフォーマンス 883 です。
ABCを通して、EFGExは未解答です。Dは通せず。久々に3完で終わってしまいました。
各問題の感想など。
A
3分5秒。
イメージを捉えるのが面倒だったので、すべてのマスで条件式を確認して個数を数えました。
B
6分50秒。
Bにしてはやや難しい?
こちらは作りたい盤面のイメージを捉える方が楽な問題でした。分かれば後は構成するだけ。
C
9分36秒。
配置を表す配列と、ボール番号からインデックスへの辞書を用意して操作するだけ。初め、右端のボールが「左端」とループすると誤読していて入力例が合わず不思議に思っていました。デバッガでループを追っているうちに、誤読に気づきました。変な設定の問題だな…と思います。
計算量は 。
D
初回提出6分54秒。
少し前似たような問題が出ていたので、 の隠れ制約があることにはすぐ気付きました。この範囲の素数列挙は なので十分間に合って、あとはとりあえず全探索で間に合うか?と方針を立てました。
最初の回答を通してみると、TLEはしないので全探索で間に合うと判断。ただし、大量の WA が出ていてどう考えてもオーバーフロー。簡単なオーバーフロー検知は入れていましたが、不十分でした。その後色々足掻いたものの、上手い回避方法が無くて撃沈。
解説を見て、浮動小数点数で大まかに見積もる手法を知りました。これを入れるだけで普通に通りました…。
仮にオーバーフロー検出方法を知っていて、初回提出で通せていればパフォは 883 から 1358 まで上がっていたようです。Eも通せていた可能性があるので、実際はより痛いです。
E
スキャナをそれぞれ持たせるイメージで、しゃくとり法的なやり方で解けそうだと思いました…が、Dの失敗もあって集中力が持たず、20分ほど実装してみて入力例が合わず、諦めました。
F, G, Ex
見てないです。
連休最終日でしばらく競プロに触れていなかったということもあるのか、恐ろしく集中力が無くて終始フワフワと解いてました。Eを解いている途中で完全に集中の糸が切れて、Dのオーバーフロー検知をグダグダこねくり回す虚無タイムに入っていました。
とりあえず ABC に参加して競プロへの意識が戻ってきたので、また明日から頑張りたいです。