Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 272

4完1WA。

各問題

A - Integer Sum

足すだけです。え、でもA問題なのにがっつりforループ使わせるんだ?!

B - Everyone is Friends

星取表みたいなのを作って埋めていけばよいです。N, M ともにたかだか100なので、三重ループしても余裕です。

C - Max Even

解の候補は「一番大きい偶数+二番目に大きい偶数」か「一番大きい奇数+二番目に大きい奇数」の二通りしかないので、その4つだけ保持して計算すればよいです。偶数と奇数を別の配列に入れてソートすれば楽です。

偶数も奇数も1つずつしかない場合は足しても奇数なので解なしです。

D - Root M Leaper

(1, 1) から、他の全てのマスへの距離を実際に計算して、距離がちょうど √M であるマスについて (1, 1) からの位置関係を記録しておきます。

次に、(1, 1) から(N, N) までの全てのマスについて、先ほど保存した位置関係を使ってグラフを作ります(マス目を一次元に展開する必要あり)。90, 180, 270度回転する場合も忘れずに。

あとはダイクストラ法をするだけです。

デバッグコードを消し忘れて1WA。懲りない。

E - Add and Mex

Mexに関与するのは値が[0, N]にあるときだけなので、どうにかしてその場合だけ計算対象にすればいけそうだとは思ったのですが、具体的にどう管理したら効率よく必要な項目だけを相手に出来るのかがわからず...。(どうがんばってもN*Mになりそうな気がした)

まとめ

レート微減ですが、水パフォ維持なのでまあ...。