オフラインには参加していませんが Pythonで解いてみました。
問題:http://nabetani.sakura.ne.jp/hena/ordf07chairs/
実装リンク集:https://qiita.com/Nabetani/items/de5b9d3230603033ed74
座席の評価は、そのときの全席(seats)の各席(seat)毎に、
- その席が空いていれば1、空いていなければ0
を基本点にして、その席が空いているときは更に、
- 左隣(left)が空いていれば +1
- 右隣(right)が空いていれば +1
として 0~3 の評価点にし、最高点の席の中から、座る人の名前によって一番小さい座席番号か一番大きい座席番号を選択します。
プログラムでは評価点を以下の算術式で計算しています。
(その席が空いてれば1、空いてなければ0) * (左隣が空いていれば1 + その席が空いていれば1 + 右隣りが空いていれば1)
Pythonは、Trueは1、Falseは0として演算できるので、以下の式に置き換えられます。
(その席 == '-') * (左席 == '-' + その席 == '-' + 右席 == '-')
その席 == '-'
が2回登場しますが、左側が0であれば全体も0になるので、左側が1だったときだけ右側を考えればよく、左側が1なら右側も1なので右側は常に1にしておくことができます。
SEATS = (1, 3, 5, 7, 9, 8, 6, 4, 2)
def sit_down(seats, someone, prefer):
left = seats[-1:] + seats[:-1]
right = seats[1:] + seats[:1]
valuation = {number: (s == '-') * ((l == '-') + 1 + (r == '-'))
for number, l, s, r in zip(SEATS, left, seats, right)}
top_value = max(valuation.values())
number = prefer(seat for seat in valuation if valuation[seat] == top_value)
seats[SEATS.index(number)] = someone
def solve(data):
seats = ['-'] * len(SEATS)
for someone in data:
if someone.isupper():
sit_down(seats, someone, someone < 'N' and min or max)
else:
seats[seats.index(someone.upper())] = '-' # leave away
return ''.join(seats)
def test(data, expect):
answer = solve(data)
print(answer == expect and "OK" or "NG", data, expect, answer)
test( "NABETanI", "I-E--T-B-" );
test( "A", "A--------" );
test( "Aa", "---------" );
test( "Z", "----Z----" );
test( "Zz", "---------" );
test( "AaB", "B--------" );
test( "ABa", "-------B-" );
test( "ABCDEFGHI", "AGCEIDHBF" );
test( "OPQRSTUVW", "WSQUOTPVR" );
test( "F", "F--------" );
test( "L", "L--------" );
test( "Mm", "---------" );
test( "JQ", "J---Q----" );
test( "ACP", "A---P--C-" );
test( "GgS", "----S----" );
test( "USLE", "L-E-U-S--" );
test( "XJZY", "J-Y-X-Z--" );
test( "NnJXx", "J--------" );
test( "AJjQa", "----Q----" );
test( "HGThgQ", "----T-Q--" );
test( "NJRErI", "J-E-N--I-" );
test( "ZzWwDYG", "D---Y--G-" );
test( "ZGgKQHM", "K-H-Z-Q-M" );
test( "OZYSAsHP", "A-Y-OPZ-H" );
test( "VNnEISAW", "E-S-VWAI-" );
test( "HhYAKkCOE", "A-O-Y-EC-" );
test( "KAkHJTSWV", "H-JWTSVA-" );
test( "WNTYKHZhMQ", "KMTQWZN-Y" );
test( "YyJHFGfgTh", "J---T----" );
test( "NRWPLBZAOpC", "LBWONZRAC" );
test( "IORiTMXHUCF", "MCTFOURXH" );
test( "AEeHGBEJUNZn", "AZGEUB-HJ" );
test( "GgKGSOsZTLYS", "K-OYZTSGL" );
test( "VZvPOpWPMzHGF", "MGO-W-HFP" );
test( "CMmcUuLTWADFQ", "LFA-TQW-D" );
test( "HUGZMLzlNgTLDd", "H-N-U-MTL" );
test( "CFKEkHeJShUDTf", "C-UTSJ--D" );
test( "QJjGPMAICHKqWcY", "GIMHWKPYA" );
test( "HhIiQCIBiUMZcVv", "--B-QZU-M" );
test( "VMvEmFOPANIBUiVb", "F-PUONAEV" );
test( "EDCJUINdLPVnFpGe", "-VCFUJGLI" );
test( "FGQINTEnLMAlBbPpV", "FMITQAVGE" );
test( "WSVCORUMXsvNBuTtT", "CXBTWRNOM" );
test( "HJTjRVIQAXqDGxCtUh", "-AVCUGRDI" );
test( "ZzHXIEKQYUuBTxLlCq", "HTEYC-KIB" );
test( "RGDCAEBVrgFbTJUePjc", "-T-FUVADP" );
test( "WBIRSALCVvsbwalYBJP", "B-R-YPCIJ" );
test( "HKFZGEPAIphLRarAOaHo", "LHFIZ-GKE" );
test( "WFNwBfbSAXCZzMDJUcKx", "AM-JSUNDK" );
補足:
(s == '-') * ((l == '-') + 1 + (r == '-'))
は
(s == '-') and ((l == '-') + 1 + (r == '-'))
でもいいです。こうすることによって sが'-'でなかったときに右側が計算されずに済んで効率的です。
valuate を辞書にしていますが、値だけのリストにして処理することもできます。リストの方が処理速度が速くなるでしょう。