結果

問題 No.3363 Two Closest Numbers
コンテスト
ユーザー rurun
提出日時 2025-10-27 23:51:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 117 ms / 2,000 ms
コード長 3,616 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 101,124 KB
最終ジャッジ日時 2025-11-17 20:33:51
合計ジャッジ時間 7,726 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from typing import List # <--- 修正点: typingからListをインポート

# input = sys.stdin.readline

MOD = 998244353
INF = 1 << 60

# cntの情報を元に、前or後ろからk桁を決める
# sで下からk+1桁目を設定する
def make_num(cnt: List[int], k: int, reversed: bool = False, s: int = 0) -> int: # <--- 修正点: list[int] を List[int] に変更
  res = s
  digit = 0
  
  if not reversed:
    # 小さい順 (1 -> 9)
    for i in range(1, 10):
      if digit >= k:
        break
      for j in range(cnt[i]):
        if digit >= k:
          break
        res = res * 10 + i
        digit += 1
        res %= MOD
  else:
    # 大きい順 (9 -> 1)
    for i in range(9, 0, -1):
      if digit >= k:
        break
      for j in range(cnt[i]):
        if digit >= k:
          break
        res = res * 10 + i
        digit += 1
        res %= MOD
        
  return res

def main():
  try:
    N_line = input()
    if not N_line:
      return
    N = int(N_line)
    
    # Nが0の場合など、入力がないケースに対応
    if N == 0:
      print(0) # N=0の時の挙動は元コードでは未定義だが、偶数扱いで0と想定
      return
      
    c_line = input()
    if not c_line:
      return
      
    c = list(map(int, c_line.split()))

  except EOFError:
    return
    
  cnt = [0] * 10
  for x in c:
    if 0 <= x <= 9:
      cnt[x] += 1

  if N % 2 == 0:
    # Nが偶数の場合
    ans = INF
    cnt_subset = [0] * 10
    sum_odd_counts = 0
    for i in range(1, 10):
      cnt_subset[i] = cnt[i] % 2
      sum_odd_counts += cnt_subset[i]

    # すべての数字が偶数個あるとき
    if sum_odd_counts == 0:
      ans = 0

    # 下から(k+1)桁目が変わらず一定のとき
    for i in range(1, 10):
      for j in range(i + 1, 10):
        if cnt_subset[i] == 0 or cnt_subset[j] == 0:
          continue
        cnt_subset[i] -= 1
        cnt_subset[j] -= 1
        # k = sum_odd_counts // 2 - 1
        x = make_num(cnt_subset, sum_odd_counts // 2 - 1, True, i)
        y = make_num(cnt_subset, sum_odd_counts // 2 - 1, False, j)
        ans = min(ans, abs(x - y))
        cnt_subset[i] += 1
        cnt_subset[j] += 1

    # 下から(k+1)桁目が変わるとき
    sum_odd_counts_new = sum_odd_counts + 2
    for i in range(1, 10): # 2個加えるやつ
      if cnt[i] < cnt_subset[i] + 2:
        continue
      cnt_subset[i] += 2
      for j in range(1, 9): # k+1桁目 (j と j+1)
        if cnt_subset[j] == 0 or cnt_subset[j + 1] == 0:
          continue
        cnt_subset[j] -= 1
        cnt_subset[j + 1] -= 1
        x = make_num(cnt_subset, sum_odd_counts_new // 2 - 1, True, j)
        y = make_num(cnt_subset, sum_odd_counts_new // 2 - 1, False, j + 1)
        ans = min(ans, abs(x - y))
        cnt_subset[j] += 1
        cnt_subset[j + 1] += 1
      cnt_subset[i] -= 2

    # ansがINFのまま（＝すべてのパターンが試行できなかった）場合、
    # C++ではINF % MOD (非常に大きな値) が出力される可能性があるが、
    # Pythonのabs(x-y)はMODを取らないため、ansは単に差の最小値。
    # 元コードの N=偶数 の最後 (cout << ans%MOD << endl;) は、
    # 差がMODを超えることを想定していないか、
    # もしくはans=0の場合を処理するためのもの。
    # ここではC++の挙動をそのまま模倣する。
    print(ans % MOD)
    
  else:
    # Nが奇数の場合
    x = make_num(cnt, (N + 1) // 2)
    y = make_num(cnt, N // 2, True)
    print((x - y + MOD) % MOD)

if __name__ == "__main__":
  main()
0