htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Regular Contest 074 参戦記

ox-- 1295 -> 1305

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder

結果:AC
Submission #1297073 - AtCoder Regular Contest 074 | AtCoder

先にHとWのどちらかが3で割り切れないか確認して(割り切れたら答えは0確定)、

 Wが2で割り切れるなら両方とも W//2*上の高さ
 割り切れないなら W//2*上の高さ と (W//2+1)*上の高さ
+--+---+
|  |   |
|  |   | ← 上の高さ = H-(下の高さ)
|  |   |
+------+
|      | ← H//3*W か (H//3+1)*W か
+------+

下のボックスの高さは前述の確認によりHが3で必ず割り切れないので切り捨てか切り上げかで2通り考え、それぞれ上のボックスもできるだけ真ん中で割って面積を出しmax-minを計算する。さらにこれを90度回転させてHとWを交換したケースでも2通り出し、計4通りについてminを取った。コードがクソきちゃない。

D: 3N Numbers - AtCoder Regular Contest 074 | AtCoder

結果:WA → 終了後にAC
Submission #1300519 - AtCoder Regular Contest 074 | AtCoder

真ん中のエリアの扱いに困って困って悩んだ。でもまあ解説見ながら実装したら境界線をNから2Nの間でずらしていくだけといえばそうなんだけど……。

数列が 8 2 2 7 4 6 5 3 8 の場合、

[8, 2, 2] [7, 4, 6] [5, 3, 8]
             ↓↓
[8, 2, 2] | [7, 4, 6 / 5, 3, 8]  # 最善は sum([8, 2, 2]) - sum([4, 5, 3]) = 0
[8, 2, 2 / 7] | [4, 6 / 5, 3, 8] # 最善は sum([8, 2, 7]) - sum([4, 5, 3]) = 5
[8, 2, 2 / 7, 4] | [6 / 5, 3, 8] # 最善は sum([8, 7, 4]) - sum([6, 5, 3]) = 5
[8, 2, 2 / 7, 4, 6] | [5, 3, 8]  # 最善は sum([8, 7, 6]) - sum([5, 3, 8]) = 5 

と全通り試すのが基本的な考え方で、いちいちsum取ったりソートしたりするとTLEになるので、高速に処理するには先に左と右の合計を出してから、優先度付きキューで出し入れしてうまいことやるといいですよという話。pythonでは普通のリストで持ってheapqで出し入れする。