Arc's Laboratory

プログラミングとかの研究室

AtCoder Beginner Contest(ABC) 088 レビュー

2/18に行われたAtCoder Beginner Contest (ABC) 088のレビューです。

問題はこちらのAtCoder公式からどうぞ。

A - Infinite Coins

N÷500の余りが一円硬貨で払う必要のある額。

x=N%500として、x<=AならYes、違うならNo

B - Card Game for Two

「残っているカードのうち、数が最大のものを取る」ことが双方にとっての最適な戦略。

C++なら降順にsortしたりpriority_queueに入れたりして、先頭の要素から順番に取っていけばいい。計算量はO(N log N)

sort priority_queueが無い言語でも、カードの数の情報を配列に保持して、「要素のうち最大の数を得点に追加」→「その要素を0に書き換える」という操作を繰り返せばACできる。計算量はO(V^2)

C - Takahashi's Information

diff(1,1)=c(1,1)-c(2,1)diff(1,2=c(1,2)-c(2,2),という風に、diff(x,y)=c(x,y)-c(x+1,y)と定義する。

すると、情報が正しいときは、少なくともdiff(1,1)==diff(1,2)==diff(1,3) && diff(2,1)==diff(2,2)==diff(2,3)が成立する。

上下方向の差の他に、左右方向の差も同じように計算して、条件が成立することを確かめる。

間違えても6重ループなんて実装したらダメだよ!

D - Grid Repainting

(1,1)から(H,W)までの最短路以外のマスを塗りつぶせばスコアが最大になる。

つまり、「初期状態の白マス数」-「最短路を通る時に通過するマス数」が答え。

「初期状態の白マス数」は、単に'.'を数えるだけで良い。

「最短路を通る時に通過するマス数」は、

struct{
    int h //h方向の位置
    int w //w方向の位置
    int grid //通過マス数
}

という感じに構造体を作って幅優先探索をかけて、(H,W)に到達したときのgridの最小値を求めれば良い。

到達済みのマスを再度探索しないように、bool型の配列などで到達済みかどうか管理しておくこと。計算量はO(H*W)

まとめ

C問題でアホコード書いたり、D問題で深さ優先探索のコードを書いてしまったりして時間をロスしてしまいました。

でも「初めてWA無し全完」「全完タイム自己ベスト」「パフォーマンス自己ベスト」を達成できました。

しかーし。

こうなったんですけどね。惜しかった。

次回は絶対に緑レート行きます。AGCですが頑張ってパフォ稼ぎたい。

JOI終わってしまいましたが、やっぱり競プロは面白いですね。今日はこの言葉を書きたかった。