ABC245 E問題を Python+SQL(DB) で解く

ABC245-E問題を データベースの力を借りてPython+SQLで解きました。

実装方針

公式の解説配信 の考え方に沿って実装していく。

要点は、平面走査によって2次元的な集合を 1次元+状態 として管理する、というところ。
ここでは、チョコレートと箱の情報を混ぜたリストを用意し

1. 横の長さ降順
2. 縦の長さ降順
3. 箱が先

でソートしてから順に見ていき、チョコレートと箱のペア作成をシミュレーションする。

この実現のため、下記の条件を満たすデータ構造が必要となる。

• 重複を含む整数の集合を扱うことができる
• 以下の操作を 十分高速に（実行時間制限 4 sec 以内に収まるように）行える
  • 要素の追加
  • ある値以上の数が存在するか判定
    • 存在する場合、その数を（1つ）削除

Pythonで解こうとすると、組み込みのデータ構造にそのまま使えるものは無さそうなので、自力で平衡二分木を実装するしかない…？

いや、sqlite3モジュールがある！！！

SQLで解く

テーブル・インデックスの作成

CREATE TABLE boxes (height INTEGER NOT NULL);
CREATE INDEX height_index ON boxes (height);

箱の追加

INSERT INTO boxes VALUES (?)

利用可能な箱の存在判定と最適な箱の取得 （rowidはSQLiteによる）

SELECT rowid FROM boxes WHERE height >= ? ORDER BY height ASC LIMIT 1

箱のマッチ確定

DELETE FROM boxes WHERE rowid = ?

提出コード

• Python (3.8.2)
  • 実行時間 : 1607 ms

Python部分ではチョコレートと箱の情報をまとめてlistに入れてreverseせずにソートし、popしながら処理する実装とした。