AtCoder Beginner Contest 201

Mynavi Programming Contest 2021(AtCoder Beginner Contest 201) - AtCoder

たびたび参加はしていましたが、リアタイ更新は約一年ぶり。

結果:4AC(1WA)
1020 位。

問題 A

ソートして条件満たすかどうか見て Yes か No 吐いて終わり。

問題 B

ソートして2番目の要素アクセスして終わり。sort 関数に渡す key を自前で用意する必要がある。

問題 C

なんとなーく、o の個数や ? の個数から解析解がありそうな気がしたけれども、「この程度の個数だったら全探索してもよいのでは...?」という悪魔のささやきに唆され、o と ? の数字だけ使ったパスワードを全部生成して、o の数字がすべて入っているかを判定して突破。

解説見たら 0000 から 9999 全探索してましたね。

問題D

色々悩みましたが、木とみて DFS でもよいですし、dp テーブル出現させてゴール側から埋めていくでもよいですけれども、
「右(下)に行ったら勝てる or 負ける → だから右(下)に行こう」をゴール側からぱたぱたやっていく問題でした。

一回目の提出の際、間違えて自分の得点を最大化するように動かしてしまったので WA いただきました。
しかも状態を自分の得点と相手の得点を保持させることになっていたので、計算量も増加したのか一部のテストケースにて TLE。

マスの移動含めて勝ち負けを判定するには、得点差だけ格納しておけばよいので、コード書き換えて AC。

問題E

 dist(i, j) dist(0, i) がすべて求まっていたらすぐ出せるなー、  dist(0, i) 全部埋めるのは BFS 使って  O(n) で出せるなーくらいまでは分かりましたが、
 \Sigma dist(i, j) 愚直に出そうとすると計算量  O(n^{2}) 行っちゃうんですけど...? となってそのまま時間切れ。

解説みました。うぇーん、鮮やか...。

問題F

見てない。

感想

bit 演算はスニペット用意してどうこうするタイプの対策にはならないので、bit 演算絡みで成り立つ諸性質のお勉強ですね...。