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

2022-04-10

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

実装方針

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

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

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

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

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

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

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

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

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