---
title: "ABC245 E問題を Python+SQL(DB) で解く"
date: 2022-04-10
tags: ["AtCoder","Python","SQL"]
url: https://aruma256.dev/posts/abc245-e-sql
---

[ABC245-E問題](https://atcoder.jp/contests/abc245/tasks/abc245_e)を データベースの力を借りてPython+SQLで解きました。

# 実装方針

[公式の解説配信](https://www.youtube.com/watch?v=GBNyYS8qsaU) の考え方に沿って実装していく。

<div class="video-embed">
  <iframe src="https://www.youtube-nocookie.com/embed/GBNyYS8qsaU" title="YouTube video player" loading="lazy" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</div>

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

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

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

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

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

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

いや、[sqlite3モジュール](https://docs.python.org/ja/3/library/sqlite3.html)がある！！！

# SQLで解く

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

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

箱の追加

```sql
INSERT INTO boxes VALUES (?)
```

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

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

箱のマッチ確定

```sql
DELETE FROM boxes WHERE rowid = ?
```

# 提出コード

* [Python (3.8.2)](https://atcoder.jp/contests/abc245/submissions/30838216)
    * 実行時間 : 1607 ms

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