世界一単純な? ソートアルゴリズム。 for i=1..n: for j=1..n: if a[i]<a[j]: swap(a[i], a[j]) 一見バブルソートのように見えるが、if判定の不等号の向きがバブルソートとは逆になっているのに、それでもソートされる。https://t.co/1qSnomUrUR
挿入ソートでは\(i\)番目の要素をそれ以前の要素と見比べて適切な位置に挿入してそれ以降の要素を一つ後ろにずらします。
このアルゴリズムでは\(i\)番目の要素との交換を使って、挿入ソートでいうところの挿入して要素を一つずつ後ろにずらす操作を実現していることになります。 挿入ソート - Wikipedia
SQLiteだと整数列の生成をしてくれるような関数がなさそうなので、WITH RECURSIVEを使って整数列を生成します。 WITH RECURSIVEは最初にデータを生成して、それ以降は生成されたデータに対してある処理をして、更に生成された同じ処理をして、というのを繰り返してデータを生成してくれます。
例えば以下の例だと、最初に0の行を生成して、それに+1して1の行が生成されて、1に対して+1して2の行が生成されて……という感じでデータを生成してくれます。WHEREの条件に引っかかって次の行が生成されなくなったら終了します。
WITH RECURSIVE coin500(i) AS (
SELECT0UNIONSELECT i + 1FROM coin500 WHERE i + 1 <= {A}
)
全体のコード
import sqlite3
con = sqlite3.connect(":memory:", isolation_level=None)
cur = con.cursor()
cur.executescript(""" PRAGMA trusted_schema = OFF; PRAGMA journal_mode = OFF; PRAGMA synchronous = OFF; PRAGMA temp_store = memory; PRAGMA secure_delete = OFF;""")
A = input()
B = input()
C = input()
X = input()
for i in cur.execute(f"""WITH RECURSIVE coin500(i) AS ( SELECT 0 UNION SELECT i + 1 FROM coin500 WHERE i + 1 <= {A}), coin100(i) AS ( SELECT 0 UNION SELECT i + 1 FROM coin100 WHERE i + 1 <= {B}), coin50(i) AS ( SELECT 0 UNION SELECT i + 1 FROM coin50 WHERE i + 1 <= {C})SELECT COUNT(*)FROM coin500, coin100, coin50WHERE coin500.i * 500 + coin100.i * 100 + coin50.i * 50 = {X}"""):
print(i[0])
SELECTSUM(CASEWHEN row_num % 2 = 1THEN n ELSE0END) - SUM(CASEWHEN row_num % 2 = 0THEN n ELSE0END)
FROM (
SELECT
n, ROW_NUMBER() OVER (ORDERBY n DESC) AS row_num
FROM num
)
import sqlite3
con = sqlite3.connect(":memory:", isolation_level=None)
cur = con.cursor()
cur.executescript(""" PRAGMA trusted_schema = OFF; PRAGMA journal_mode = OFF; PRAGMA synchronous = OFF; PRAGMA temp_store = memory; PRAGMA secure_delete = OFF; CREATE TABLE num(n INTEGER);""")
N = input()
A = map(int, input().split())
cur.executemany("INSERT INTO num VALUES(?)", map(lambda x: (x,), A))
cur.execute(f""" CREATE TEMPORARY TABLE ordered AS SELECT n FROM num ORDER BY n DESC""")
for i in cur.execute(f""" SELECT (SELECT SUM(n) FROM ordered WHERE rowid % 2 = 1) - (SELECT SUM(n) FROM ordered WHERE rowid % 2 = 0)"""):
print(i[0])
WITH RECURSIVEを使って、末尾から文字列を取り除いた文字列を順に生成していくクエリを書いたのですが、これはTLEになってしまいました。
import sqlite3
con = sqlite3.connect(":memory:", isolation_level=None)
cur = con.cursor()
cur.executescript(""" PRAGMA trusted_schema = OFF; PRAGMA journal_mode = OFF; PRAGMA synchronous = OFF; PRAGMA temp_store = memory; PRAGMA secure_delete = OFF;""")
S = input()
for i in cur.execute(f""" WITH RECURSIVE str(s) AS ( SELECT "{S}" UNION SELECT CASE WHEN substr(s, -5) = "dream" THEN substr(s, 1, length(s) - 5) WHEN substr(s, -7) = "dreamer" THEN substr(s, 1, length(s) - 7) WHEN substr(s, -5) = "erase" THEN substr(s, 1, length(s) - 5) WHEN substr(s, -6) = "eraser" THEN substr(s, 1, length(s) - 6) END FROM str WHERE s IS NOT NULL ) SELECT CASE WHEN COUNT(*) = 1 THEN "YES" ELSE "NO" END FROM str WHERE s = """""):
print(i[0])