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)。

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重ループなんて実装したらダメだよ！

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

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

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

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

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

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

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

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

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

しかーし。

ｸﾞﾌｫｧｧ（死） pic.twitter.com/UkF23tt0lx
— Arc@競プロ (@arcslab123) 2018年2月18日

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

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

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