ABC374参加記録 by Python

リアルタイムに解けた問題

A - Takahashi san 2

問題文

キーエンスでは、役割や年齢、立場の違いに関係なく「さん」付けして呼ぶという文化があります。
英小文字のみからなる文字列$S$が与えられます。
$S$がsanで終わっているならばYesを、終わっていないならばNoを出力してください。

制約

• $S$は英小文字のみからなる長さ4以上30以下の文字列

アルゴリズム

受け取った文字列の末尾3文字をスライシングでチェックする。

ソースコード

S = input()

if S[-3:] == "san":
  print("Yes")
else:
  print('No')

B - Unvarnished Report

問題文

キーエンスでは良いことも悪いこともありのままに報告するという文化があります。
そこで、報告内容が元の文章のありのままであるかを確認したいです。

英小文字のみからなる文字列$S,T$が与えられます。
$S$と$T$が等しいならば0を、そうでないならば異なっている文字のうち先頭のものが何文字目かを出力してください。
ただし、$S,T$の一方のみ$i$文字目が存在するときも、$i$文字目は異なっているとみなすものとする。

より厳密には、$S$と$T$Tが等しくないならば次の条件のうちいずれかを満たす最小の整数$i$を出力してください。

• $1 \leq i \leq |S|$かつ$1 \leq i \leq |T|$かつ$S_{i} \neq T_{i}$
• $|S| < i \leq |T|$
• $|T| < i \leq |S|$

ただし、$|S|,|T|$でそれぞれ$S,T$の長さを、$S_{i},T_{i}$でそれぞれ$S,T$の$i$文字目を表します。

制約

• $S,T$は英小文字のみからなる長さ1以上100以下の文字列

アルゴリズム

$S,T$の長さが等しいか等しくないかで条件分岐。
等しい場合は、$S,T$が同じ文字列であるかないかで条件分岐。
等しくない場合は、$S,T$どちらが長いかで条件分岐。その中で、短い方の長さでループを回し、異なる文字が見つけられなければ、短いほうの文字列の長さ+1の数値を出力（$S,T$の一方のみ$i$文字目が存在するときも、$i$文字目は異なっているとみなすものとするため）

ソースコード

S = input()
T = input()

if len(S) == len(T):
  if S == T:
    print(0)
  else:
    for i in range(len(S)):
      if S[i] != T[i]:
        print(i+1)
        exit()
else:
  if len(S) < len(T):
    for i in range(len(S)):
      if S[i] != T[i]:
        print(i+1)
        exit()
      
    print(len(S)+1)
  else:
    for i in range(len(T)):
      if S[i] != T[i]:
        print(i+1)
        exit()
      
    print(len(T)+1)

C - Separated Lunch

問題文

キーエンス本社に勤務する人数が増えてきたので、本社に存在する部署を2つのグループに分け、昼休みの時間帯をわけることにしました。

キーエンス本社には$N$個の部署が存在し、$i$番目($1 \leq i \leq N)の部署に所属する人数は$K_{i}$人です。

それぞれの部署グループ$A,B$のいずれか一方に割り当て、グループごとに同時に昼休みをとり、かつグループ$A,B$の昼休みの時間が重ならないようにしたとき、同時に昼休みをとる最大人数としてあり得る最小の値を求めてください。
すなわち、グループ$A$に割り当てられた部署に所属する人数の合計とグループ$B$に割り当てられた部署に所属する人数の合計のうち大きい方の値としてあり得る最小の値を求めてください。

制約

• $2 \leq N \leq 20$
• $1 \leq K_{i} \leq 10^{8}$
• 入力はすべて整数

アルゴリズム

「半分全列挙」アルゴリズムを使用。
まず、部署人数のリスト$K$を半分に分ける。次に、itertoolsのcombinationsを使用し、分割したそれぞれの配列ですべての部分和を求め、その集合を変数に格納する。（first_sumsとsecond_sums）。ここから、$K$の合計輪の半分の値を目標値とし、二分探索を行う。ループを回し、
first_sumsとsecond_sumsの各値の差が最小となるものを探す。（差が最小ー＞同時に昼休みをとる最大人数としてありえる最小値）

ソースコード

N = int(input())
K = list(map(int, input().split()))

from itertools import combinations

def divide_min_max(N, K):

  first_half = K[:N//2]
  second_half = K[N//2:]

  def calc_subset_sums(arr):
    sums = set()
    for i in range(len(arr) + 1):
      for comb in combinations(arr, i):
        sums.add(sum(comb))
    return sums

  first_sums = calc_subset_sums(first_half)
  second_sums = calc_subset_sums(second_half)

  total_sum = sum(K)
  target = total_sum // 2

  second_sums = sorted(second_sums)

  best = float('inf')
  for s1 in first_sums:
    lo, hi = 0, len(second_sums) - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      s2 = second_sums[mid]
      current_sum = s1 + s2
            
      if current_sum <= target:
        best = min(best, max(current_sum, total_sum - current_sum))
        lo = mid + 1
      else:
        hi = mid - 1

  return best
  
print(divide_min_max(N, K))