問題
他の方の解答
作成時間
問題の読み違い(IさんとJさんの処理間違い)をしてハマって、修正時間含めて1時間半くらいかかったと思います。
電車移動中に作成して集中できてなかったとはいえ、現地でやってたとしても間に合わなかったと思います。
解法Pythonスクリプト
time2min = lambda t: int(t)/100*60 + int(t)%100
reserve = lambda r: bin(1<<24*60 | r)[3+10*60:3+18*60].find("1"*60) + 10*60
def solve(data):
A = B = I = J = Z = R = (1<<24*60)-1
for d in data.split(","):
start, end = map(time2min, d[1:].split("-"))
exec(d[0]+" &= "+str(~R>>start | R>>end))
r = min([r for r in map(reserve, (A&B&I&~Z, A&B&J&~Z)) if r >= 10*60] or [-1])
return "-" if r < 0 else "%d%02d-%d%02d"%(r/60, r%60, r/60+1, r%60)
def test(data, correct):
answer = solve(data)
print "xo"[answer == correct], data, correct, answer
0, test( "A1050-1130,B1400-1415,I1000-1400,I1600-1800,J1100-1745,Z1400-1421,Z1425-1800", "1425-1525" );
1, test( "A1000-1200,B1300-1800,Z1000-1215,Z1230-1800", "-" );
2, test( "Z0800-2200", "1000-1100" );
3, test( "A1000-1700,Z0800-2200", "1700-1800" );
4, test( "A1000-1701,Z0800-2200", "-" );
5, test( "A1000-1130,B1230-1800,Z0800-2200", "1130-1230" );
6, test( "A1000-1129,B1230-1800,Z0800-2200", "1129-1229" );
7, test( "A1000-1131,B1230-1800,Z0800-2200", "-" );
8, test( "A1000-1130,B1229-1800,Z0800-2200", "-" );
9, test( "A1000-1130,B1231-1800,Z0800-2200", "1130-1230" );
10, test( "A1000-1130,B1230-1800,Z0800-1130,Z1131-2200", "-" );
11, test( "A1000-1130,B1231-1800,Z0800-1130,Z1131-2200", "1131-1231" );
12, test( "Z0800-0801", "-" );
13, test( "Z0800-1031,Z1129-1220,Z1315-1400,Z1459-1600", "1459-1559" );
14, test( "Z0800-2200,I1000-1600,J1030-1730", "1600-1700" );
15, test( "Z0800-2200,I1000-1600,J1130-1730", "1000-1100" );
16, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1025", "1025-1125" );
17, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645", "1645-1745" );
18, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645,I1735-2200", "-" );
19, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645,J1735-2200", "1645-1745" );
20, test( "Z1030-2200,I1000-1600,J1130-1730", "1030-1130" );
21, test( "Z1035-1500,I1000-1600,J1130-1730,Z1644-2200", "1644-1744" );
22, test( "I2344-2350,A2016-2253,Z1246-1952", "1246-1346" );
23, test( "Z2155-2157,B1822-2032,Z1404-2000,Z2042-2147,Z2149-2154", "1404-1504" );
24, test( "Z2231-2250,Z2128-2219,B2219-2227,B2229-2230,Z0713-2121,A0825-1035,B1834-2001", "1035-1135" );
25, test( "J0807-1247,I0911-1414,B1004-1553,Z0626-1732,Z1830-1905,A1946-1954,A0623-1921", "-" );
26, test( "J1539-1733,J0633-1514,Z1831-1939,J1956-1959,I0817-1007,I1052-1524,Z1235-1756,Z0656-1144", "1524-1624" );
27, test( "Z2319-2350,B0833-2028,I2044-2222,A1410-2201,Z2044-2228,Z0830-2023,Z2242-2306,I2355-2359", "-" );
28, test( "B2001-2118,Z0712-1634,I1941-2102,B1436-1917", "1000-1100" );
29, test( "A0755-1417,B2303-2335,Z0854-2150,Z2348-2356,Z2156-2340,I1024-1307,Z2357-2359", "1417-1517" );
30, test( "A1958-1959,B0822-1155,I1518-1622,Z1406-1947,A1800-1822,A0904-1422,J1730-1924,Z1954-1958,A1946-1956", "1422-1522" );
31, test( "B1610-1910,I2121-2139,A0619-1412,I2147-2153,Z0602-2111,I0841-2031,A1657-1905,A1956-2047,J0959-1032,Z2131-2147", "1412-1512" );
32, test( "Z0623-1900,A0703-1129,I1815-1910,J1956-1957,I0844-1518,Z1902-1935,B1312-1342,J1817-1955", "1129-1229" );
33, test( "J1246-1328,B1323-1449,I1039-1746,Z1218-2111", "1449-1549" );
34, test( "A1958-1959,I1943-1944,I0731-1722,Z0845-1846,J1044-1513,Z1910-1923,B1216-1249", "1513-1613" );
35, test( "A1855-2047,Z0946-1849,Z2056-2059,I1855-1910,B1946-2058,I1956-2025,Z1905-2054,J0644-1800,I0720-1618", "1618-1718" );
36, test( "J1525-1950,Z0905-1933,A1648-1716,I2051-2054,I2015-2044,I0804-1958,B0934-1100,Z1953-2037", "1100-1200" );
37, test( "Z1914-1956,J0823-1610,Z0641-1841,J1800-1835,A0831-1346,I1926-1941,I1030-1558,I1738-1803", "1558-1658" );
38, test( "Z0625-1758,J1033-1351,B1816-2236,I0838-1615,J2247-2255", "1351-1451" );
39, test( "J0603-1233,A1059-1213,I1326-2103,Z0710-1459", "1213-1313" );
40, test( "B1302-1351,J1410-2038,A0755-1342,J0637-0658,Z2148-2159,Z1050-2131,A1543-1844,I1615-1810", "1351-1451" );
41, test( "Z0746-2100,A2122-2156,I1022-1144,J0947-1441,A1333-1949", "1144-1244" );
42, test( "J0718-1243,Z1443-1818,B2055-2057,A0714-1238,Z1045-1344,A1643-1717,B1832-2039,J1623-1931", "1238-1338" );
43, test( "Z1921-1933,A1208-1418,I0827-1940,Z0757-1917,J0653-1554,B1859-1909", "1554-1654" );
解説
reserve = lambda r: bin(1<<24*60 | r)[3+10*60:3+18*60].find("1"*60) + 10*60
10時から18時までのスケジュールの中から、60分間連続した空き時間を探して開始時間を返す reserve 関数定義です。
各人のスケジュールは1分単位のビットマップデータで、各人のスケジュールを論理積したビットマップデータ r が渡されます。
bin関数でスケジュールビットマップデータを2進数文字列化し、スケジュールが空いていれば "1"、予定済なら "0" の1分単位文字列にします。
1<<24*60 を論理和しているのは、0時からスケジュールを予定されるとbin関数で先頭の0が削られて 24時間分の24*60文字にならないので、確実に24*60文字にするために 1<<24*60 を論理和して 24*60+1文字の2進数文字列に変換しています。
2進数文字列は0時0分から23時59分までのビットマップデータなので、[3+10*60:3+18*60] で会議時間の10時～18時の部分を切り出しています。3+ しているのは、bin関数での変換結果の先頭に "0b" が付くのと、1<<24*60 で余計に付く "1" の合計3文字分を読み進めています。
find("1"*60) で 60分間連続でスケジュールが空いている部分を探します。見つからないと -1 になります。
10時00分以降を切り出した2進数文字列から find しているので、10時00分から60分間見つかった場合には 0 が返り、+ 10*60 して 10時00分 の時間データを返します。
空き時間が見つからなかった場合には -1 + 10*60 で 9時59分 を返します。
A = B = I = J = Z = R = (1<<24*60)-1
(1<<24*60)-1 は、1のビットが 24*60 個並んだビットマップデータを作成しています。1ビットが1分間の予定を表しています。
Aさん、Bさん、Iさん、Jさん、Zさんのスケジュールを、24時間空いていることを表す 1 が24*60個並んだビットマップデータで初期化しています。
R は各人の予定済み時間部分を 0 にする計算で使います。
exec(d[0]+" &= "+str(~R>>start | R>>end))
入力データが "A1050-1130" であれば、A &= (~R>>(10*60+50) | R>>(11*60+30)) を計算します。
Aさんのスケジュールビットマップデータの 10時50分 から 11時30分 の範囲の各ビットが予定済みを表す 0 になります。
r = min([r for r in map(reserve, (A&B&I&~Z, A&B&J&~Z)) if r >= 10*60] or [-1])
A&B&I&~Z で、AさんとBさんとIさんの空き時間と、Zさんの予定済時間(ビット反転) を論理積しています。これで4人分の都合のいいスケジュールビットマップデータが求まります。
IさんとJさんはどちらかが最初から最後まで出席すればいいので、A&B&J&~Z のスケジュールビットマップデータも求めます。
min(reserve(A&B&I&~Z), reserve(A&B&J&~Z)) と同等の min(map(reserve, (A&B&I&~Z, A&B&J&~Z))) で開始時間が早い方を求めます。
ただし、空き時間が見つからなかった場合には reserve関数から 9時59分 のデータが返ってきて9時59分が選ばれてしまうので、内包表記を使って if r >= 10*60 で 10時以降のデータだけを抽出しています。
両方とも空き時間がないと空リスト [ ] になってしまい、 min([ ]) はエラーになるため、空リストだったら min([-1]) を計算させるように or [-1] しています。