結果
問題 |
No.3219 Ruler to Maximize
|
ユーザー |
![]() |
提出日時 | 2025-08-01 22:49:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,399 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 82,828 KB |
実行使用メモリ | 62,376 KB |
最終ジャッジ日時 | 2025-08-01 22:49:27 |
合計ジャッジ時間 | 2,856 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
from collections import deque N = int(input()) A = list(map(int, input().split())) sets = deque() def check(target_idx): for i in range(len(sets)): st2 = sets.popleft() for idx in st2: if idx == target_idx: # st2をstにmerge return True, st2 sets.append(st2) return False, None bit = 1 for bi in range(12): st = set() for i in range(N): if bit & A[i]: # 1. 既存のsetsにi番目が使われてないかcheck has_i, st2 = check(i) if has_i: st |= st2 else: # 2. 既存になかったら自分で追加 st.add(i) if st: sets.append(st) bit <<= 1 # print(sets) M = len(sets) ans = 0 ans_s = ['W'] * N for s in range(1 << M): w = 0 b = 0 for i in range(M): if s >> i & 1: for idx in sets[i]: w |= A[idx] else: for idx in sets[i]: b |= A[idx] cand = w * b # print(w, b, cand) if ans < cand: ans = cand # 文字列作成 for i in range(M): if s >> i & 1: for idx in sets[i]: ans_s[idx] = "W" else: for idx in sets[i]: ans_s[idx] = "B" print(ans) print(''.join(ans_s))