AtCoder Beginner Contest 005

 2つ目。

結果

 400/400 47:59 21位相当

 

 開始時刻 2017/07/22 17:03:00 提出履歴

A: おいしいたこ焼きの作り方 - AtCoder Beginner Contest 005 | AtCoder

 0:36(AC)

 y/xするだけ。整数値の割り算は有能ね!

B: おいしいたこ焼きの食べ方 - AtCoder Beginner Contest 005 | AtCoder

 2:17(AC)

 最小値を更新していくだけ。

C: おいしいたこ焼きの売り方 - AtCoder Beginner Contest 005 | AtCoder

 25:24(AC)

 実装がちょっと面倒くさい。基本方針としては、お客さんの満足できる一番古いたこ焼きを売りつけていって、売れなかった時はnoを出力する。

 AもBも、ソートされていることが保証されてるので、どちらも前から順番に処理していけばいい。

D: おいしいたこ焼きの焼き方 - AtCoder Beginner Contest 005 | AtCoder

 47:59(AC)

 クエリのパターンが2500(N^2)しかないので、初めからクエリの答えを用意してO(1)で答えちゃうのが良さそう。

 基本的には二次元累積和を取って、領域の和をO(1)で求められるようにするのが良さそう。ちなみに入力でやってる処理はD[i][j] = B[i][j] - B[i-1][j] - B[i][j-1] - B[i-1][j-1]を軽く式変形して、B[i][j]の式にしただけ。

 累積和の準備ができたら、あとは長方形全パターンについて全探索をして最大を更新していくだけ。ただ、サンプルケースにもあるように、返すべき値はP以下の値における最大値なので、そういう風になるように最後に微調整する。

感想

 結構いいペースで解けた。さっきやったABC004も割といい感じだったし、今日は指が乗ってるみたい。

 たこ焼き食べたい。